Помощничек
Главная | Обратная связь


Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

Теория графов как инструмент анализа сетей



Теория графов предоставляет словарь для обозначения многих особенностей социальных структур, а также набор простых концепций, с помощью которых можно эти особенности оха­рактеризовать качественно и оценить количественно. Используя теоремы о свойствах графов, можно определять свойства социальных структур

Отношения между акторами могут быть как ненаправленными (например, «жить по со­седству»), так и направленными (например, импорт товара из одной страны в другую). Соот­ветственно для анализа первых применяются ненаправленные, или неориентированные, гра­фы, а для анализа последних — направленные, или ориентированные.

Неориентированные графы: основные понятия

Граф 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, которая равна числу ребер, исходящих из вершины.

Плотность ориентированного графа характеризуется коэффициентом плотности Δ:




©2015 studopedya.ru Все права принадлежат авторам размещенных материалов.