Способы задания графов

Совокупность множества М с заданным на нем бинарным отношением ТМ2 [9] называется графом
G=<M,T>,
где М – носитель графа – множество вершин, изображаемых точками, Т – сигнатура графа – множество линий, обозначающих отношения и называемых ребрами.
Между элементами М и Т определено отношение инцидентности, т.е. связи между двумя элементами множества М через один элемент множе-ства Т. Примеры графов: отношения отцовства и материнства на множестве людей, отношения подчиненности, карты дорог местности, электрические схемы соединений приборов и т.д.

Рис. 12. Пример графа «звезда»

М={1,2,3,4,5},
Т={(1,3),(1,4),(2,4),(2,5),(3,1),(3,5),(4,2),(4,1),(5,3),(5,2}).
Множество линий-ребер в Т задается обозначением пары (i,j), где i,j – инцидентные вершины, отношение Т – «быть связанным».
Теорию графов начали разрабатывать для решения некоторых задач о геометрических конфигурациях, состоящих из точек и линий. В этих задачах несущественно, соединены ли точки конфигурации отрезками прямых или они криволинейны, какова длина линий и другие геометрические характеристики конфигурации. Важно лишь, что каждая линия соединяет какие-либо две из заданных точек [24].
Первые серьезные результаты теории графов связаны с решением задач построения электрических цепей (Г. Кирхгоф) и подсчета числа химических соединений с различными типами молекулярных связей (А. Кэли). Изобразите в виде графа молекулу 
В 30-е годы ХХ века благодаря трудам Д. Кенига [19] теория графов стала развиваться как самостоятельный раздел математики.
Широкое развитие теория графов получила с 50-х годов ХХ века в связи с появлением такой науки, как кибернетика. Графы применяют при анализе функционирования систем. С отдельными компонентами изучае-мой системы удобно связывать вершины графа, а с парами взаимодейст-вующих компонент – его ребра. Такой граф называют структурным гра-фом системы.
В некоторых задачах существенно направление ребер графа. Направленные ребра называют дугами, а содержащий их граф – ориентированным (орграфом). Таковым графом может быть изображена диаграмма Хассе. Соответственно граф с неориентированными ребрами называется неориентированным.
Множество ребер может быть пусто. Если же множество вершин пус-то, то пусто и множество ребер. Такой граф называется пустым. Линии, изображающие ребра, могут пересекаться на изображении графа, но точки их пересечений не являются вершинами. Различные ребра могут быть инцидентны одной и той же паре вершин, в этом случае они называются кратными. Граф, содержащий кратные ребра, называют мультиграфом (псевдографом). Ребро (дуга) может соединять некоторую вершину саму с собой, такое ребро (дуга) называется петлей. Будем рассматривать конечные графы, содержащие конечные множества вершин и ребер (дуг).
Рассмотрим предложенную фон Нейманом архитектуру ЭВМ, которая состоит из множества устройств М={а,b,c,d,e}, где а – устройство ввода, b – арифметическое устройство (процессор), с – устройство управления, d – запоминающее устройство, е – устройство вывода [9-10].
Информационный обмен между этими устройствами задается графом (рис. 13).

Рис. 13. Граф, описывающий архитектуру
фон Неймановской ЭВМ

Вершины графа на рис. 13 для удобства изображены кружками, а не точками, как на рис. 11.
Граф можно задать так называемой матрицей смежности, каждой i-ой строке (j-му столбцу) которой однозначно сопоставляют элемент множе-ства М, между которыми выполняется отношение смежности. Две вершины, инцидентные одному ребру, смежны. Два ребра, инцидентные одной вершине, тоже смежны. Тогда каждая клетка bij взаимно однозначно соответствует элементам множества ММ=М2. Клетку bij, которая соответствует элементу, принадлежащему бинарному отношению ТМ2, отмечают, например, единицей, а в остальные клетки записывают нули.
Рассмотрим матрицу смежности В для графа, изображенного на рис. 13. Устройства i,j находятся в отношении Т, если из устройства i инфор-мация поступает в устройство j.

Граф можно задать и с использованием перечисления его дуг, как это сделано на рис. 13:
М={а,b,с,d,е},
Т={(а,b),(а,с),(а,d),(b,с),(b,е),(b,d),(с,а),(с,b),(с,d),(с,е),(d,с),(d,b),(d,е),(е,с)}.
Граф можно задать в виде так называемого фактор-множества, пред-ставленного парами «элемент множества М – подмножество М, представляющее собой окрестность единичного радиуса этого эле-мента»:
[<a,{b,c,d}>,<b,{c,d,е}>,<c,{a,b,d,e}>,<d,{b,c,e}>,<e,{c}>].
Ориентированный граф может быть задан и матрицей инцидентности А размерностью nm: A=aij, где n=|M|, m=|Т|, у которой
если вершина ai является концом дуги tj;
если вершина ai является началом дуги tj;
если вершина ai не инцидентна дуге tj,
,  .

Так, для ориентированного графа (рис. 14) матрица инцидентности имеет вид:

Рис. 14. Некоторый ориентированный граф

В описанном виде матрицы инцидентности применимы только к гра-фам без петель, в случае наличия которых матрицу надо разбить на две полуматрицы: положительную и отрицательную. Ориентированный граф также может быть задан матрицей смежности.
Для графов с кратными ребрами в матрице смежности указывают кратность ребер, например, для графа, изображенного на рис. 15, матрица смежности представляется в виде:

Такой граф называют мультиграфом.

Рис. 15. Некоторый ориентированный мультиграф

Граф называется нагруженным, если каждому ребру (дуге) поставлено в соответствие некоторое действительное число (длина дуги, вес дуги, стоимость дуги и т.д.).
Представим в виде графа некоторые бинарные отношения [9]. Отно-шение Т в множестве М рефлексивно, как мы уже знаем, если для каждого элемента mМ справедливо (m,m)Т. На графе это изображается петлей (рис. 16а). На матрице смежности графа с рефлексивным отношением все элементы, лежащие на главной диагонали отмечены единицами.
Отношение во множестве М называется симметричным, если из (mi,mj)Т следует (mi,mj)М, mimj (рис. 16б). Матрица смежности сим-метричного отношения симметрична относительно главной диагонали.
Отношение Т в множестве М называется транзитивным, если из (mi,mj)Т, (mi,mk)Т следует (mi,mk)Т mi, mj,mkМ, mimj, mimk, mjmk (рис. 16в).
В графе, задающем транзитивное отношение Т, для всякой пары дуг таких, что конец первой совпадает с началом второй, существует транзи-тивно замыкающая дуга, имеющая общее начало с первой и общий конец со второй.

Рис. 16. Изображения бинарных отношений в виде графа
а) рефлексивное отношение, б) симметричное отношение,
в) транзитивное отношение