Деревья дерево покрытия графа примеры

Теория графов – деревья

Деревья – это графики, которые не содержат ни одного цикла. Они представляют иерархическую структуру в графической форме. Деревья относятся к простейшему классу графов. Несмотря на их простоту, они имеют богатую структуру.

Деревья предоставляют целый ряд полезных приложений, от простого семейного дерева до сложных в структурах данных компьютерной науки.

дерево

Связный ациклический граф называется деревом. Другими словами, связный граф без циклов называется деревом.

Края дерева известны как ветви . Элементы деревьев называются их узлами . Узлы без дочерних узлов называются листовыми узлами .

Дерево с ‘n’ вершинами имеет ‘n-1’ ребер. Если у него есть еще одно ребро, превышающее ‘n-1’, то это дополнительное ребро, очевидно, должно соединиться с двумя вершинами, что приводит к образованию цикла. Затем он становится циклическим графом, что является нарушением для графа дерева.

Пример 1

График, показанный здесь, является деревом, потому что у него нет циклов, и он связан. Он имеет четыре вершины и три ребра, т. Е. Для ‘n’ вершин ‘n-1’ ребер, как указано в определении.

Примечание. Каждое дерево имеет как минимум две вершины первой степени.

Пример 2

В приведенном выше примере вершины «a» и «d» имеют степень один. А две другие вершины ‘b’ и ‘c’ имеют второй уровень. Это возможно, потому что для того, чтобы не формировать цикл, в диаграмме должно быть как минимум два отдельных ребра. Это не что иное, как два ребра со степенью один.

лес

Несвязный ациклический граф называется лесом. Другими словами, непересекающаяся коллекция деревьев называется лесом.

пример

Следующий график выглядит как два подграфа; но это один несвязный граф. На этом графике нет циклов. Отсюда ясно, что это лес.

Охватывающие деревья

Пусть G – связный граф, тогда подграф H в G называется остовным деревом в G, если –

Остовное дерево T неориентированного графа G является подграфом, который включает в себя все вершины G.

пример

В приведенном выше примере G является связным графом, а H является подграфом G.

Ясно, что граф H не имеет циклов, это дерево с шестью ребрами, которое на единицу меньше общего числа вершин. Следовательно, H – остовное дерево группы G.

Circuit Rank

Пусть «G» связный граф с «n» вершинами и «m» ребрами. Остовное дерево ‘T’ группы G содержит (n-1) ребер.

Следовательно, количество ребер, которые нужно удалить из ‘G’, чтобы получить остовное дерево = m- (n-1), которое называется рангом схемы G.

Эта формула верна, потому что в остовном дереве вам нужно иметь ребра n-1. Из «m» ребер вам нужно сохранить «n – 1» ребер в графе.

Следовательно, удаление ребер n – 1 из m дает ребра, которые нужно удалить из графа, чтобы получить остовное дерево, которое не должно образовывать цикл.

пример

Посмотрите на следующий график –

Для графика, приведенного в примере выше, у вас есть m = 7 ребер и n = 5 вершин.

пример

Пусть ‘G’ – связный граф с шестью вершинами, а степень каждой вершины равна трем. Найдите звание цепи «G».

По сумме теоремы о степени вершин

Теорема Кирхгофа

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

пример

Матрица «А» заполняется так, как если между двумя вершинами есть ребро, то она должна быть задана как «1», иначе «0».

Источник

3 Покрывающие деревья (остовы)

Цикломатическим числом неориентированного графа G называется величина γ(G) = т — п + k, где т — число ребер, п — число вершин, k — число связных компонент. Для дерева и леса γ (G) = 0, для других графов γ (G) > 0.

Остовом, или покрывающим деревом, связного графа G=(V, E) называется часть G, которая содержит все его вершины и является деревом. Хордой остова графа G называется ребро G, не принадлежащее остову.

Очевидно, что любой связный граф имеет хотя бы один остов, а любой несвязный граф остова не имеет.

В последующем алгоритме части исходного графа G, которые возникают в процессе построения покрывающего дерева, будем называть букетами.

Алгоритм построения покрывающего дерева для произвольного невзвешенного графа g

1. Выбрать любое ребро G, не являющееся петлей. Пометить его меткой α и объявить букетом это ребро вместе с его концевыми вершинами.

2. Выбрать любое непомеченное ребро G, не являющееся петлей:

а) если один из концов выбранного ребра принадлежит построенному ранее букету В, а другой конец свободен (не принадлежит ни одному букету), пометить выбранное ребро меткой α, включить его вместе со свободным концом в букет В и перейти к шагу 3;

б) если оба конца выбранного ребра свободны, поме­тить его меткой а, объявить это ребро вместе с его конце­выми вершинами новым букетом и перейти к шагу 3;

в) если концы выбранного ребра принадлежат разным построенным ранее букетам В и С, пометить выбранное ребро меткой α, включить его и букет С в букет В и перейти к шагу 3;

г) если оба конца выбранного ребра принадлежат одному букету, пометить его меткой β и перейти к шагу 3;

д) если непомеченных ребер нет, закончить алгоритм.

3. Если все вершины графа G вошли в один букет, закончить алгоритм. Если нет, перейти к шагу 2.

Алгоритм выделения минимального остовного дерева в неориентированном взвешенном графе g

1. Выберем в графе G ребро минимальной длины. Вместе с инцидентными ему двумя вершинами оно образует подграф G₂ графа G. Положим i:=2.
2. Если i=n(G), то задача решена и G_i – искомое минимальное остовное дерево графа G. Иначе переходим к шагу 3).
3. Строим граф G_i+1. Для этого добавим к графу G_i новое ребро минимальной длины из оставшихся, которое инцидентно какой-либо вершине графа G_i и одновременно вершине, не содержащейся в G_i. Вместе с этим ребром включаем в G_i+1 и эту инцидентную ему вершину. Присваиваем i:=i+1 и переходим к шагу 2.

Лекция 12 Двудольные и планарные графы

1 Двудольные графы

Двудольным графом G=(X, Y, Е) называется неориентированный граф, вершины которого можно разбить на два класса X и Y так, что концы каждого ребра принадлежат разным классам. Двудольный граф называется полным, если каждая вершина одной доли соединена с каждой вершиной другой доли, полный двудольный граф принято обозначать символом гдет = |Х|, n = . Введенные понятия допускают естественное обобще-ие. Неориентированный граф называется k-дольным, если его вершины можно разбить на k классов так, что концы каждого ребра принадлежат разным классам. Полный k-дольный граф — это k-дольный граф, в котором каждая вершина одной доли соединена с каждой вершиной всех остальных долей. Пример. На рисунке 24 представлены двудольный граф G=(X, Y, Е), полный двудольный граф К_3,3 и трехдольный граф G=(X, Y, Z, Е), где X = 1 x₂>, Y = 1 y₂, y₃>, Z = 1 z₂>. G=(X, Y, Е) G=(X, Y, Z, Е) Рисунок 24 – Двудольные графы Теорема. Граф является двудольным, если и только если длины всех его простых циклов четны. Паросочетанием в неориентированном графе называется множество попарно несмежных ребер. Задача о максимальном паросочетании заключается в нахождении паросочетания максимальной мощности. Для двудольного графа одной из наиболее известных интерпретаций задачи о максимальном паросочетании является задача о назначениях, которая заключается в следующем. Имеется т работников и п работ. Каждый работник способен выполнять несколько работ; каждую работу могут выполнять несколько работников. Требуется определить назначения по принципу «один работник — одна работа» так, чтобы загрузить максимальное число работников. Условия этой задачи представляются в виде двудольного графа, в котором вершины класса X соответствуют работникам, вершины класса Y- работам, а наличие ребра (x_i, y_j) означает, что i-й работник может выполнять j-ю работу. Решением этой задачи будет максимальное паросочетание, которое находится путем сведения к задаче о потоках.

Источник

2. Экстремальное дерево графа

Определение 12.2. Конечный связный неориентированный граф без циклов называется деревом.

Примеры. На рисунке 12.7 представлены примеры деревьев:

Дерево, имеющее n вершин, включает в себя n–1 ребро. При составлении дерева используется минимальное число ребер, чтобы граф был связным. При включении в дерево любого дополнительного ребра возникнет цикл. Дерево может быть частью неориентированного графа. Любая совокупность ребер графа попарно связанных отношением смежности и инцидентности и соответствующие им вершины образует дерево графа. Если такое дерево графа содержит все вершины графа, то оно называется покрывающим деревом или остовом графа.

Алгоритм построения экстремального дерева предполагает соединение всех вершин графа с помощью путей наименьшей (наибольшей) длины. Типичной задачей, для решения которой необходим такой алгоритм, является проектирование дорог с твердым покрытием, соединяющих населенные пункты в сельской местности, проведение линии связи, водо- или газопровода с наименьшей суммарной длиной.

1) Составить план n вершин дерева.

2) Составить таблицу весов всех возможных связей между вершинами.

3) Выбрать ребро с наименьшим (наибольшим) весом и включить в дерево.

4) На следующем шаге рассмотреть минимальное по весу ребро из оставшихся и, если оно не образует цикл с ранее включенными ребрами, то добавить к дереву. Если имеется несколько таких ребер, то выбирается любое, при этом задача имеет альтернативное решение.

5) Построение заканчивается после разбора n–1 ребра.

Задача. Телевизионная компания планирует подключение к своей кабельной сети пяти новых районов. На рисунке 12.8 показана структура планируемой сети и расстояния (в км) между районами и телецентром. Необходимо спланировать наиболее экономичную кабельную сеть.

Решение задачи сводится к построению экстремального дерева графа.

Занесем данные задачи в следующую таблицу:

Источник

Деревья покрытия. Остовы

1. Пусть – связный граф. Деревом покрытия графа называется подграф, который является деревом, и множество вершин которого совпадает с множеством вершин графа .

Заметим, что связный граф может иметь много различных деревьев покрытия. (Пример)

1. Каждый связный граф содержит в себе дерево покрытия.

1. Пусть – связный граф. Если не содержит циклов, то доказывать ничего не надо, ибо – сам по себе – дерево покрытия.

Предположим, что содержит цикл. Удаление любого ребра из цикла дает граф, который еще остается связным. Если новый граф еще содержит цикл, то опять удалим ребро этого цикла. Продолжим процесс до тех пор, пока результирующий граф не будет содержать ни одного цикла. Мы не удалили ни одной вершины из , и связность графа не нарушилась при удалении ребер. итак, – связный и является деревом покрытия .

1. Пусть – несвязный граф. Остовом (или каркасом) графа называется объединение деревьев покрытия всех его компонент связности.

Очевидно, что в каждом графе существует остов: разрушая в каждой компоненте связности циклы, т.е. удаляя лишние ребра, придем к остову.

1. Число ребер произвольного графа , которые необходимо удалить для получения остова, не зависит от последовательности их удаления и равно .

1. Если – граф является одной из компонент связности графа , то для превращения его в остовное дерево нужно удалить подходящих ребер, т.к. в дереве число ребер . Суммируя по всем компонентам, получим требуемое.

1. Число называется цикломатическим числом графа .

1. Раскраска графов

1. Пусть — некоторый граф, натуральное число. Произвольная функция вида называется раскраской графа .
2. Раскраска называется правильной, если любых смежных вершин и
3. Граф, для которого правильная раскраска, называется раскрашиваемым (или просто раскрашиваемым цветами).

Правильную раскраску графа можно трактовать как окрашивание каждой его вершины в одни из цветов, при этом смежные вершины должны получить различные цвета.

1. Минимальное число , при котором граф является раскрашиваемым, называется хроматическим числом этого графа и обозначается . Если , то граф называется хроматическим. Правильная раскраска при называется минимальной раскраской.

1. Одна из правильных 4-раскрасок.

Меньшим числом цветов этот граф раскрасить правильно нельзя. Очевидно, что граф является хроматическим, т.и.т.т., когда он пустой, а хроматическим, когда он двудольный. Задачи определения хроматического числа и построения минимальной раскраски произвольного графа является очень сложными, эффективные алгоритмы их решения неизвестны. Рассмотрим простой алгоритм построения правильной раскраски, в ряде случаев приводящий к раскраскам, близким к минимальным.

Алгоритм правильной раскраски

• произвольной вершины графа применим цвет 1.
• Если вершины раскрашены цветами , , то новой произвольно взятой вершине припишем цвет, не использованный при раскраске вершин из её окружения (т.е. инцидентных ей вершин).

Раскраска, к которой приводит данный алгоритм, называется последовательной. Для некоторых графов (напр., для полных двудольных) последовательная раскраска является минимальной. В общем случае это не так.

Источник