Остовы графов

 

тема ∶" Элементы теории графов. Виды и способы задания графов"

 

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

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

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

 

Остовы графов

ТеоремаДля неорграфа G без петель, содержащего n вершин, следующие условия эквиваленты: 1) G-дерево; 2) G-связный граф, содержащий n-1 ребро;

Рис. 4.33

Из теоремы, выше изложенной, вытекает

Следствие.Число ребер произвольного неорграфа G, которые необходимо удалить для получения остова, не зависит от последовательности их удаления и равно т‐n +c, где m-число ребер, n-число вершин, c-число компонент связности графа G.

Д о к а з а т е л ь с т в о. Действительно если i-я компонента связности графа G содержит вершин, то по теореме соответствующие дерево остова содержит -1 ребро. Следовательно, для получения из компоненты нужно удалить ребер, где число ребер в . Суммируя удаляемые ребра по всем компонентам связности и замечая, что , , получаем, что необходимо удалить ребер .

Число v(G) называется цикломатическим числом или циклическим рангом графа G. Число v*( G)= называется коциклическим рангом или корангом. Таким образом, v*( G) есть число ребер, входящих в любой остов графа G, и v(G) v*(G)=m.

Очевидны следующие два следствия.

Следствиеэ.Неорграф G является лесом тогда и только тогда, когда v(G)=0.

Следствие 4.8.4.Неорграф G имеет единственный цикл тогда и только тогда, когда v(G)=1.

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

Алгоритм, решающий задачу нахождения остова минимального веса во взвешенном графе , заключается в следующем.

1. Строим граф T₁, состоящий из множества вершин M и единственного ребра u₁, которое имеет минимальный вес.

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

Приведенный алгоритм, в частности, позволяет находить остов в невзвешенном графе, положив для всех ребер R.

П р и м е р 4.8.2. На рис. 4.34 показан остов минимального веса взвешенного графа. Вес остова графа равен 9.

 

2 1

3 3 5

 

4 3

2 1 3

 

Рис. 4.34

 

Обходы графа по глубине и ширине.

Решение задачи коммивояжера

Пусть связный неориентированный граф T некоторый остов графа G, a некоторая фиксированная вершина, называемая корнем дерева T. Разместим…    

Рис. 4.35

 

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

На рис. 4.36 показана очередность обхода вершин по глубине графа, изображенного на рис. 4.35.

 

1

2 12

8 19

3 7 9 13 14 16

4 10 11 15

17 18

5 6

 

Рис. 4.36

При обходе графа по ширине просмотр вершин дерева ведется по этажам, переход к вершинам следующего этажа производится только после просмотра всех вершин данного этажа. На рис. 4.37 показан порядок обхода по ширине графа, изображенного на рис. 4.35.

 

1

2 4

3 10

5 6 7 8 9 15

11 12 13 14

18 19

16 17

Рис. 4.37

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

Отметим, что при компьютерной реализации обходов по глубине и ширине целесообразно использовать задание дерева структурой смежности вершин.

Часто при решении задач их разбивают на несколько более простых задач, которые, в свою очередь, разбиваются на более простые подзадачи и так до тех пор, пока не появляются подзадачи, поддающиеся непосредственному решению. Такое разбиение задач можно представить в виде дерева следующим образом. Если задача A разбивается на подзадачи A(1,1),A(1,2), … … ,A(1,n₁), подзадача A(1,i) на подзадачи A(2,i,1), …, … , A и т.д., то получается дерево, изображенное на рис. 4.38.

А

 

 

 

А(1,1) А(1,2) . . . А(1,n₁)

 

 

. . .

А(2,1,1) . . . А(2,1,n₂₁) А(2,n₁,1) . . .

 

 

. . . . . . . . . . . .

 

Рис. 4.38

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

Пусть матрица весов графов не имеющего петель, где . Для простоты будем считать, что все веса неотрицательны. Найдем нижнюю оценку весов гамильтоновых циклов. Для этого в матрице весов найдем минимальные числа каждой строки: , , … , . Очевидно, что вес произвольного гамильтонова цикла не меньше . Преобразуем матрицу весов, вычитая из каждой строки соответствующее число . Получаем матрицу , где . В ней найдем минимальные числа каждого столбца: , , , , и преобразуем ее, вычитая из каждого столбца соответсвующее число : , где . Для любого гамильтонова цикла X справедлива оценка веса цикла X : h, где h .

Обозначим через множество гамильтоновых циклов, в которых первые k вершин a₁,a₂, … , , a(k+1)-я вершина не принадлежит множеству . Используя введенные обозначения, можем разбить нашу задачу на две подзадачи, поделив множество гамильтоновых циклов на множества (рис. 4.39).

При рассмотрении множества отождествим в графе G вершины 1 и (обозначим новую вершину через x) и получим граф G̕ с множеством вершин и матрицей весов

 

 

.

Для графа G̕ найдем нижнюю оценку h̕ весов гамильтоновых циклов аналогично тому, как найдены оценки h. Тогда нижняя оценка h₁ весов гамильтоновых циклов множества равна h+h̕.

 

H

 

h₁

h₂

 

h₁₁

h₁₂

h₂₂

h₂₁

 

h₁₁₁

 

. . . . . . . . . . . . . . . . . . . . .

 

Рис. 4.39

При рассмотрении множества (1) {k₁} в матрице весов W* элемент заменяется на и по полученной матрице W находится нижняя оценка h˝ весов гамильтоновых циклов графа с матрицей весов W˝. Тогда нижняя оценка h₂ весов гамильтоновых циклов множества (1) {k₁} равна h .

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

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

П р и м е р 4.9.1. рассмотрим граф с матрицей весов

.

Найдем минимальные числа строк: , где 2= .

Вычитая соответствующие числа из каждой строки, получим матрицу

.

После нахождения наименьших значений по столбцам (4,0,0,1,0,0) и вычитания из каждого столбца матрицы соответствующего числа образуется матрица

.

Суммируя элементы и получаем нижнюю оценку h=14. Так как , то множество гамильтоновых циклов разобьем на два множества (1,5) и (рис. 4.40).

 

 

H

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 4.40

При рассмотрении множества (1,5) получаем матрицу весов

 

.

графа G̕, образованного отождествлением вершин 1 и 5 графа G. Минимальные элементы строк матрицы W̕ образуют столбец

 

а минимальные элементы столбцов матрицы образуют нулевую строку, и значит, (W̕)*=(W̕)ˇ. Таким образом, оценка h₁ будет равна h+h̕=14+1=15.

Рассматривая множество (1) {5}, мы должны в матрице W* заменить элемент . Тогда оценка h₂ будет h+h̕=14+2=16.

Поскольку h₁<h₂, выбираем множество (1,5) и соответствующую матрицу весов (W̕)*. Теперь в силу того, что (w*)_x3=0, разобьем множество гамильтоновых циклов из множества (1,5) на множества (1,5,3) и (1,5) Рассматривая случай (1,5,3) , получаем матрицу весов

 

.

графа G˝, образованного отождествлением вершин x и 3 графа G̕. Оценка h₁₁ равна 15, а (W˝)* W˝. При рассмотрении множества (1,5) в матрице (W̕)* заменяем элемент (w̕)*₂₃=0 на и получаем оценку h₁₂=h₁+2=17.

Так как h₁₁< h₁₂, выберем множество (1,5,3) с матрицей весов (W˝)*=W˝. Поскольку (W˝)*_x4=0, рассмотрим множества циклов (1,5,3,4) и (1,5,3) . Для оценивания весов в множестве (1,5,3,4) отождествим вершины x и 4 в графе G˝ и получим граф G̕̕̕ с матрицей весов

 

.

Очевидно, что h₁₁₁= h₁₁=15, а (W˝̕)* элемент (w˝)*_x4=0 на и получаем оценку h₁₁₂= h₁₁+2=17.

Так как h₁₁₁ h₁₁₂, то переходим к рассмотрению множества (1,5,3,4) , состоящего из двух гамильтоновых циклов (1,5,3,4,2,6,1) и (1,5,3,4,6,2,1). Первый из этих циклов будет иметь вес , поскольку (W̕̕̕)₂₆= , а вес второго цикла 15, что соответствует оценке h₁₁₁=15. Поскольку оценки h₂, h₁₂ и h₁₁₂ больше h₁₁₁, соответствующие множества не содержат гамильтонова цикла веса, меньшего 15, и поэтому цикл (1,5,3,4,6,2,1) является гамильтоновым циклом минимального веса.

 

Упорядоченные и бинарные деревья

1) пустое множество и список (a), где a-некоторый элемент, является упорядоченным деревом; 2) если T₁,T₂, … ,Tn-непустые упорядоченные деревья, a-некоторый… 3) любое упорядоченное дерево строится в соответствии с пп. 1 и 2.

Рис. 4.41

Упорядоченное дерево может также интерпретироваться в виде так называемого уступчатого списка, который используется в оглавлениях. На рис. 4.42 представлен уступчатый список, соответствующий упорядоченному списку из примера 4.10.1.

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

 

Рис. 4.42

Тезис.Любая иерархическая классификационная схема интерпретируется некоторым упорядоченным деревом.

Например, в виде упорядоченного дерева представляется любой терм. На рис. 4.43 изображено упорядоченное дерево, соответствующее терму .

Частным случаем упорядоченного дерева является бинарное дерево. Определение бинарного дерева повторяет определение для упорядоченного дерева с ограничением в п. 2. При этом для бинарного дерева T= ((a), T₁,T₂), бинарное поддерево T₁ называется левым поддеревом, а T₂-правям поддеревом.

Бинарные деревья имеют более простое устройство, чем упорядоченные, и вместе с тем любой упорядоченный лес взаимно однозначно соответствует некоторому бинарному дереву.

Опишем алгоритм преобразования упорядоченного леса T=(T₁,T₂, … ,T_n) в бинарное дерево B(T).

1. Если

2. Если , то корнем бинарного дерева является корень упорядоченного дерева T₁ , левое поддерево дерева бинарное дерево B(T₁₁, T₁₂, … , T_1m), где T₁= ((a₁), T₁₁, T₁₂, … , T_1m), правое поддерево дерева бинарное дерево B(T₂, … , T_n).

 

 

 

 

 

 

 

Рис. 4.43

На рис. 4.44б представлено бинарное дерево, соответствующее упорядоченному лесу (T₁,T₂), изображенному на рис. 4.44а.

 

 

J

I

G

F

E

H

C

D

B

A

J

I

F

E

G

D

H

C

B

A

 

 

a б

Рис. 4.44

 

Фундаментальные циклы

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

Рис. 4.45

 

 

Разрезы

Пусть G= - неорграф = разбиение множества M. Разрезом графа G (по разбиению ) называется множество всех ребер, соединяющих вершины из M1 с… Непустой разрез K неорграфа G называется простым разрезом или коциклом, если…  

Рис. 4.46

Теорема 4.12.1. В конечном неорграфе G=, имеющем с компонент связности, множество ребер K тогда и только тогда является коциклом, когда граф имеет (c+1) компонент связности.

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

Следующие две почти очевидные теоремы дают информацию о связи остовов с разрезами, а также циклов с разрезами.

Теорема 4.12.2. В связном неорграфе остовное дерево имеет по крайней мере одно общее ребро с любым из разрезов графа.

Теорема 4.12.3. В связном неорграфе любой цикл имеет с любым разрезом четное число общих ребер.

В условиях, указанных в предыдущем параграфе, рассмотрим неорграф G с остовом T. Снова пусть ветви остова T. Удаляя из остова T произвольную ветвь , получаем лес c(c+1) компонентами связности, т.е. каждое ребро является разрезом остова T по некоторому разбиению ( рис. 4.47).

 

 

 

 

 

M₁ M₂

Рис. 4.47

В графе G могут найтись еще какие-то ребра ( являющиеся хордами T), которые соединяют вершины из и . Множество образует простой разрез, который называется фундаментальным разрезом графа G относительно ветви остова T. Множество всех фундаментальных разрезов графа G называется фундаментальным множеством коциклов графа G относительно остова T. Отметим, что мощность фундаментального множества коциклов не зависит от выбора остова T и равна корангу * .

Аналогично фундаментальным циклам каждому фундаментальному разрезу ставится в соответствие вектор _i , определяемый по правилу

 

Фундаментальное множество коциклов задается матрицей фундаментальных разрезов , строки которой являются векторами _{1, 2}, … , _v*(G):

.

Поскольку каждый фундаментальный разрез содержит ровно одну ветвь, а именно , матрица имеет вид

 

.

Таким образом, K= , где единичная матрица порядка . Отметим, что если C= соответствующая матрица фундаментальных циклов, то =C^T₂.

П р и м е р 4.12.1. Найдем матрицу фундаментальных разрезов графа G= , изображенного на рис. 4.45. Поскольку фундаментальных разрезов. Ребру 4 соответствует коцикл , так как при удалении ребра 4 из остова T множество вершин M разбивается на две части∶ и M , а ребра 1 и 4 образуют разрез по разбиению . Аналогично ребру 5 соответствует коцикл , ребру 6-коцикл , ребру 7-коцикл , ребру 8-коцикл . Следовательно, матрица фундаментальных разрезов имеет вид

 

 

.

§ 4.13. Векторные пространства,

Связанные с графами

Рассмотрим алгебраическую систему 2= с двухместными операциями кольцевого сложения ⊕ и умножения ⊙, задаваемыми следующими… Пусть G= связный неорграф, имеющий n вершин и m ребер . Произвольному…  

Раскраски графов

П р и м е р 4.14.1. Так как в полном графе Kn любые две различные вершины связаны ребром, то χ(Kn)=n. Многие практические задачи сводятся к построению раскрасок графов. П р и м е р 4.14.2 1. Рассмотрим задачу составления расписания. Предположим, что нужно прочесть несколько лекций за…

Планарные графы.

П р и м е р 4.15.1. Граф ( рис. 4.48а) планарен, поскольку может быть изображен, как показано на рис. 4.48б.  

Рис. 4.48

Граф, описанный в примере 4.14.2,п.2, является планарным. Также планарным является граф, вершины которого –отверстия печатной платы, а ребра-проводники печатной платы, соединяющие отверстия.

Рассмотрим операцию подразбиения ребра в графе G= . После подразбиения ребра получается граф G̕=, где =,R̕= т.е. ребро заменяется на - цепь длины два. Два графа называются гомеоморфными, если их можно получить из одного графа с помощью последовательности подразбиений ребер.

Не всякий неорграф является планарным. Критерий планарности описывает

Теорема 4.15.1 ( теорема Понтрягина-Куратовского).

Граф G планарен тогда и только тогда, когда G не содержит подграфа, гомеоморфного K₅ или K_3,3 ( рис. 4.49).

 

 

 

 

 

K₅ K₃,₃

Рис. 4.49

Эквивалентная форма критерия планарности описана в следующей теореме.

Теорема 4.15.2.Тогда и только тогда неорграф G планарен, когда G не содержит подграфов, стягиваемых (т.е. получаемых последовательностью отождествлений вершин, связанных ребрами) к графу K₅ или K_3,3 ( рис. 4.49).

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

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

Д о к а з а т е л ь с т в о. Пусть G= - граф, для которого . Расположим все точки графа G на некоторой прямой и каждой дуге из разнозначно сопоставим плоскость , содержащую прямую . Искомое изображение графа G получается после проведения всех дуг в соответствующих плоскостях.

Известна оценка хроматического числа планарных графов.

Теорема 4.15.4 (теорема о четырех красках). Если G- планарный граф, то χ(G) 4.

При исследовании принципиальной электрической схемы радиоэлектронного устройства с точки зрения возможности ее реализации с помощью печатного монтажа или монтажа на слоях микросхемы важно знать ответ на следующие вопросы: 1) является ли граф, соответствующий рассматриваемой принципиальной схеме, планарным? 2) если граф планарен, то как получить его изображение без пересечения ребер? На первый вопрос принципиальный ответ дает теорема Понтрягина-Куратовского, а методы получения плоских изображений планарных графов можно найти в книге Б.Н. Деньдобренко, А.С. Малика .

Если граф G непланарен, то для его геометрической реализации удаляют отдельные ребра ( переносят на другую плоскость). Минимальное число ребер, которое необходимо удалить из графа для получения его плоского изображения, называется числом планарности графа G. При вынесении этих ребер на вторую плоскость получают часть графа, которая также может оказаться неплоской. Тогда вновь решают задачу вынесения отдельных ребер на следующую плоскость и т.д. Минимальное число плоскостей m, при котором граф G разбивается на плоские части G₁, G₂, … , G_m (разбиение ведется по множеству ребер) , называется толщиной графа G.

Таким образом, толщина планарного графа равна 1.

П р и м е р 4.15.2. Каждый из графов K₅ и K_3,3 имеет толщину 2.

 

Задачи и упражнения

  2. Составить матрицу инцидентичности для мультиграфа, изображенного на рис…