Неориентированные и ориентированные графы

Для эффективного выделения скоплений объектов существу­ют методы сетевого анализа. Сетевой анализ матрицы оценок сходства между объектами заключается в построении некоторых типов графов, т.е. диаграмм, где объекты изображены в виде то­чек (кружков) – вершин графа, которые соединяются или не со­единяются линиями, называемыми ребрами графа. Степень соот­ветствия между объектами отражается в графах или характером взаимного расположения точек, или длиной и другими особенно­стями линии, соединяющих точки.

При анализе матриц сходства обычно используются «неориен­тированные графы», в которых линии, соединяющие вершины графа, не имеют направления. Реже применяются «ориентированные графы», в которых вершины соединены стрелками.

Дендрит – один из типов неориентированного графа. Он может быть двух типов: минимальное древо (матрица включает оценки различий между объектами) или максимальное древо (использу­ются меры сходства).

Дендрит – это ломаная линия, которая может ветвиться, но не содержит циклов. Построение дендрита заключается в нахож­дении для каждого объекта наиболее сходного с ним объекта и со­единении их линией. В результате получается ряд отрезков, в том числе и разветвленных.

Построить дендрит (рис. 5.8.1) можно с помощью матрицы сход­ства выборочных совокупностей, например (A–Е), вычисленной на основе индекса сходства Жаккара (табл. 5.8.1). Для этого после­довательно соединяем две наиболее сходные выборки Г и Д (0,90) отрезком. Следующая по силе величина сходства 0,85 обнаружена между выборками Г и В. Поэтому выборку В можно присое­динить отрезком к уже построенной ветке Д – Г и т. д.

Таблица 5.8.1