Теория графов предоставляет словарь для обозначения многих особенностей социальных структур, а также набор простых концепций, с помощью которых можно эти особенности охарактеризовать качественно и оценить количественно. Используя теоремы о свойствах графов, можно определять свойства социальных структур
Отношения между акторами могут быть как ненаправленными (например, «жить по соседству»), так и направленными (например, импорт товара из одной страны в другую). Соответственно для анализа первых применяются ненаправленные, или неориентированные, графы, а для анализа последних — направленные, или ориентированные.
Неориентированные графы: основные понятия
Граф G= (N,Z) — это совокупность двух конечных множеств: множества точек N= {n ,, ...,ng}, которые называются вершинами, и множества пар вершин Z= {l1,...,lz}, которые называются ребрами.
Граф изображается точками на плоскости и линиями 1к= {пр п), соединяющими эти точки. На рис. 3.6а показан граф, который имеет пять вершин и шесть ребер, а на рис. 3.6b — граф, который имеет четыре вершины и четыре ребра.
Ребра, имеющие одинаковые концевые вершины, называются параллельными. Ребро, концевые вершины которого совпадают, называется петлей. На рис. 3.6а /4 и /5 — параллельные ребра, а /2 — петля. Вершина и ребро называются инцидентными друг другу, если вершина является для этого ребра концевой точкой. На рис. 3.6а вершина п3и ребро 1Линцидентны друг другу.
Примеры графа
Две вершины, являющиеся концевыми для некоторого ребра, называются смежными вершинами. Два ребра, инцидентные одной и той же вершине, называются смежными ребрами. На рис. 3.6а n1, п2 — смежные вершины, а l1,, l4 — смежные ребра.
Степень вершины
Под степенью п-й вершины d(n) понимается число ребер, инцидентных этой вершине. Вершина степени 1 называется висячей. Вершина степени 0 называется изолированной. На рис. 3.6а степень «,-й вершины d(nt) = 3, «4 — висячая вершина, п5— изолированная.
В некоторых случаях важно определить среднюю степень вершин d для совокупности всех вершин графа. Для этого используют статистику:
где L — общее число ребер графа,
g — общее число вершин графа
Граф G называется полным, если любые две его вершины соединены ребром и он не содержит параллельных ребер
Дополнением графа G называется граф с теми же вершинами, что и граф G, и содержащий только те ребра, которые нужно добавить к графу G, чтобы получился полный граф.
Циклом называется путь, начальная и конечная вершины которого совпадают. На рис. 3.6а ребра (l1, l3, l4) образуют цикл.
Маршрутом между вершинами пi и пjграфе называется последовательность ребер, ведущая от некоторой начальной вершины п1к конечной вершине п. Путем называется маршрут, не содержащий циклов. Дистанцией между двумя ребрами называется кратчайший путь между ними.
Связность графа
Граф G называется связным, если для любых двух его вершин существует путь, их соединяющий. В противном случае граф G называется несвязным. На рис. 3.8 представлен несвязный граф
Несвязный граф
Любой несвязный граф является совокупностью таких связных графов, которые обладают следующим свойством: никакая вершина одного из них не связана путем ни с какой вершиной другого. Каждый из этих графов называется компонентой графа G. В данном примере граф состоит из двух связных компонентов.
Ребро а называется мостом графа G, если граф, получившийся из G после удаления ребра а (такой граф обозначается G\ а), содержит больше компонент, чем граф G. Ребро а графа G является мостом тогда и только тогда, когда а не принадлежит ни одному циклу.
Плотность графа характеризуется коэффициентом плотности А — отношением числа ребер (L) в анализируемом графе к числу ребер в полном графе с тем же числом вершин (g):
Коэффициент плотности варьируется в промежутке от 0 до 1, 0 ≤ Δ ≤ 1. Единичная плотность соответствует полному графу, нулевая — графу, в котором все вершины изолированные.
Частным случаем графов являются деревья. Они характеризуются тем, что содержат минимальное число ребер, необходимое для связности.
При этом
• любое ребро дерева представляет собой мост,
• l = g-1;
• существует только один путь между любыми двумя вершинами.
Ориентированные графы: основные понятия
Если рассматривается множество упорядоченных пар 1к= (ni, пj) из множества точек N={n1 ., пg}, и на каждом ребре из множества Z= { l1,...,lz } задается направление, то граф Gd = (N,Z) называется ориентированным.. Если же на каждом ребре из множества Z= {l1,...,lz } направление не задается, то граф G = (N, Z) называется неориентированным графом, или просто графом.
Примеры ориентированного графа
В ориентированном графе для каждой вершины различаются входящие и исходящие ребра. Поэтому для характеристики отношений, связанных с конкретной вершиной, используют два показателя:
• степень захода dm, которая равна числу ребер, входящих в вершину; и
• степень исхода doul, которая равна числу ребер, исходящих из вершины.
Плотность ориентированного графа характеризуется коэффициентом плотности Δ: