Смежность, инцидентность, степени вершин.
Если х = {v, w} – ребро графа, то v, w называются концами ребра х, в этом случае говорят, что ребро х соединяет вершины v и w.
Если вершина v является концом ребра х, то говорят, что v и х инцидентны .
Вершины v, w графа G(V,X) называются смежными, если {v, w}ÎХ.
Два ребра называются смежными, если они имеют общую вершину.
Рассмотрим граф на рисунке 13.1.
Вершине v3 инцидентны ребра {v3, v3}, {v3, v1}, {v3, v2}, {v3, v4}.
Ребру {v2, v6} инцидентны вершины v2, v6.
Вершины v5, v6 – смежные, т.к. {v5, v6}- ребро. Вершины v5, v3 – не смежные, т.к. нет ребра их соединяющего.
Ребра {v3, v1}, {v3, v2}- смежные, т.к. имеют общую вершину v3.
Степень вершины v – это количество ребер графа, инцидентных этой вершине. Обозначение d (v).
Для графа 13.1:
d (v1) = 1 d (v5) = 2
d (v2) = 2 d (v6) = 3
d (v3) = 5 d (v7) = 0
d (v4) = 1
Заметим, что вклад каждой петли равен двум.
Если степень вершины равна единице, то такая вершина называется висячей.
Если степень вершины равна нулю, то такая вершина называется изолированной.
Значит, вершины v1 и v4 – висячие, а вершина v7 – изолированная.
Теорема о сумме степеней вершин графа: Для любого псевдографа G(V, X) выполняется равенство:
m – количество ребер графа. Действительно, каждое ребро графа инцидентно двум вершинам.
Проверим справедливость теоремы для графа 13.1:
m =7, 7× 2 =14 и 1+2+5+1+2+3+0 =14.
3. Способы задания графов
Один из способов задания графа уже рассмотрен – это геометрическое изображение, т.е. диаграмма.
Но при решении задач теории графов, осуществляемых на вычислительных машинах, такое задание не удобно. Граф должен быть представлен дискретным способом. Одно из направлений теории графов связано с их матричным представлением. Существуют различные виды матриц. Рассмотрим такие матричные формы, которые наиболее широко используются в алгоритмах на графах.
Матрица инцидентности графа.
Пусть задан граф G(V, X), где V ={v1, v2, …, vn}, X = {x1, x2,…, xm}.
Матрицей инцидентности графа G(V, X) называется матрица размера m´ n, элементы которой определяются следующим образом:
В любой строке матрицы инцидентности два или один элемент не равны нулю, т.к. каждое ребро соединяет две вершины, а если ребро – петля, то вершину саму с собой.
Матрица инцидентности однозначно определяет структуру графа, что позволяет читать всю необходимую информацию о графе. Например, выявлять изолированные и висячие вершины, петли; определять степени вершин. Информация о ребрах считывается по строкам, о вершинах – по столбцам.
Составим матрицу инцидентности для графа 13.1. Это матрица размера 7´ 7:
В первом и четвертом столбцах по одной единице, следовательно первая и четвертая вершины – висячие; в седьмом столбце все элементы равны нулю, значит седьмая вершина изолированная.
В третьей строке только один элемент не равен нулю, следовательно третье ребро- петля.
Суммируя элементы по столбцам с учетом того, что вклад петли равен двум, можно определить степень каждой вершины.
Матрица смежности
Пусть задан граф G(V, X), где V ={v1, v2, …, vn}, X = {x1, x2,…, xm}.
Матрицей смежности графа G(V, X) называется квадратная матрица n´ n, элементы которой определяются следующим образом:
k – количество ребер, соединяющих вершины vi и vj .
Составим матрицу смежности для графа 13.1. Это квадратная матрица размера 7´ 7:
Матрица смежности неориентированного графа симметрична относительно главной диагонали.
Если есть не равные нулю элементы главной диагонали, то это означает наличие петель в графе. Читать информацию о графе можно и по столбцам и по строкам.
Сумма элементов верхнего или нижнего треугольника вместе с главной диагональю равна количеству ребер в графе. Для нашего графа сумма равна (учитывая только элементы не равные нулю): 1+1+1+2+1+1=7.
Далее рассматривая некоторые задачи теории графов будем использовать именно такой способ задания графа.
4. Маршруты в неориентированном графе
Определение: Маршрутом , соединяющий вершины v1 и vk+1 , называется последовательность v1x1v2x2…vkxkvk+1 , где k³ 1, vi Î V, xiÎ X, ребро xi соединяет вершины vi с вершиной vi+1 . Вершина v1 (v нач)– начало маршрута (начальная вершина), vk+1 (v кон)– конец маршрута (конечная вершина).
Для графа 13.1 построим маршрут, соединяющий вершину v1 с вершиной v5 :
v1x1v3x3v3v2x5v6x7v5 .
Допускается краткая запись маршрута. В том случае, если в маршруте нет кратных ребер, то составляют последовательность только из вершин.
Если в маршруте есть кратные ребра, то в последовательность включают начальную вершину, ребра и конечную вершину. Или пользуются комбинированной записью: в последовательность включают все вершины и только кратные ребра.
Перепишем наш маршрут, использую комбинированную запись: v1v3v3v2v6x7v5 . В последовательность включено только кратное ребро x7 .
Длиной маршрута l называется количество ребер в нем.
В нашем маршруте 5 ребер, значит его длина l =5.
Познакомимся с видами маршрутов.
Если vнач = vкон , то маршрут называется замкнутым.
Если vнач ¹ vкон , то маршрут называется незамкнутым.
Виды незамкнутых маршрутов:
Незамкнутый маршрут, в котором все ребра попарно различны называется цепью.
Цепь, в которой все вершины попарно различны называется простой цепью.
Виды замкнутых маршрутов:
Замкнутый маршрут, в котором все ребра попарно различны называется циклом.
Цикл, в котором все вершины попарно различны называется простым циклом.
Заметим, что петля или кратное ребро являются простыми циклами.
Составим различные маршруты для приведенного ниже графа на рисунке 13.5.
Рис. 13.5.
Маршрут v1v2v3v4 – простая цепь.
Маршрут v2v4v5v6v6v4 – цепь, не являющаяся простой.
Маршрут v3v4v5v6v5 – замкнутый маршрут.
Маршрут v3v2v4v5v6v4v2v3 – цикл, не являющийся простым.
Маршрут v3v2v4v3 – простой цикл.
5. Операции над графами.
Так как граф G(V, X) задается двумя множествами V и X , то для него определены теоретико-множественные операции : объединение и пересечение.
Объединением графов G1(V1, X1), G2(V2, X2) называется граф G(V, X), где V = V1 ÈV2 , X = X1 ÈX2 .
Пересечением графов G1(V1, X1), G2(V2, X2) называется граф G(V, X), где V = V1 ÇV2 , X = X1 ÇX2 .
Кроме этих операций познакомимся с понятиями : подграф и сурграф.
Подграфом графа G(V, X) называется граф G’(V’, X’) , где G’Í G, X’Í X.
Подграф G’(V’, X’) графа G(V, X) называется собственным, если G’Ì G, X’Ì X.
Подграфом графа G(V, X) , порожденным множеством V1 Í V, где V1 ¹Æ, называется граф G1(V1, X1), где Х1 Í Х и соединяет вершины только из V1 .
Сурграфом графа G(V, X) называется граф G”(V, X”), где V=V, X” Ì X.
 |
Рис.13.6.
 |
Рис. 13.7.
 |
Рис.13.8.
На рисунке 13.6 представлен собственный подграф графа 13.5.
На рисунке 13.7 – подграф графа 13.5, порожденный множеством V1 ={v1, v2, v4, v6}.
На рисунке 13.8 – сурграф графа 13.5.
6. Связность. Компоненты связности
Пусть дан псевдограф G(V,X).
Две вершины v и w называются связанными (или вершина v достижима из w), если :
а) v = w;
б) существует маршрут, связывающий вершины v и w.
Определенное на множестве V отношение достижимости или связности является бинарным эквивалентным отношением (проверьте самостоятельно). А значит, множество V можно разбить на классы эквивалентности V1 V2 …Vk, где V1 ÈV2È …ÈVk=V и V1 ÇV2 Ç…ÇVk = Æ.
Все вершины, принадлежащие одному подмножеству Vi связанные, а вершины, принадлежащие разным подмножествам – несвязанные.
Каждое подмножество Vi называется компонентой связности графа G(V,X).
Согласно выше сказанному можно сформулировать определение компоненты связности следующим образом:
Компонента связности графа G(V,X) – это связный подграф, не являющийся собственным подграфом никакого другого связного подграфа графа G(V,X).
Количество компонент связности графа G(V,X) обозначается P(G).
На рисунке 13.9 представлен граф, у которого три компоненты связности, т.е. P(G) =3: G1, G2, G3
G1 G2 G3
Рис. 13.9.
Введем понятие связного графа.
Граф G(V,X) называется связным, если любые две его вершины достижимы (связанные).
Или: граф G(V,X) называется связным, если P(G) = 1.
Тогда, несвязный граф имеет P(G) >1.
С понятием компонента связности связаны понятия: разделительная вершина (точка сочленения) и мост.
Введем еще одну операцию над графом – удаление вершины.
Операцией удаления вершины называется удаление некоторой вершины вместе с инцидентными ей ребрами.
Если удаление вершины увеличивает количество компонент связности графа, то такая вершина называется точкой сочленения или разделительной вершиной.
Ребро, при удалении которого увеличивается количество компонент связности графа, называется мостом.
Для графа 13.5 найдем все разделительные вершины и мосты:
разделительные вершины: v2, v4,
мост : {v1, v2}.