Федоров В.Н. - Введение в теорию графов, страница 9

Если к дереву T добавить произвольную хорду h_i, то образуется точно один цикл C_i. Этот цикл состоит из хорды h_i и некоторых ветвей остова, образующих простую цепь и соединяющих вершины хорды h_i.

Цикл C_i называется фундаментальным циклом графа G относительно хорды h_i остова T (в общем случае остовов в графе может быть много). Таким образом, фундаментальный цикл содержит точно одну хорду остова графа.

Множество всех фундаментальных циклов {C₁, C₂, …, C_i, …, C_m–n+1} относительно хорд остова T называется фундаментальным множеством циклов графа G. Мощность этого множества равна цикломатическому числу (G) = m – n +1 или рангу графа G.

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

h₁, h₂, …, h_m–n+1, b₁, b₂, …, b_n–1,

где h_i, b_j – хорды и ветви соответственно.

В каждом цикле имеется одна хорда h_i и некоторое множество ветвей остова T. Этой хорде h_i и ветвям, входящим в цикл C_i, присвоим значение 1, остальным ребрам графа присвоим значение 0. Повторяя процедуру для всех хорд, получим матрицу строк из 0 и 1.

Пример. для графа G и его остова T, показанных на рис. 10.1, матрица фундаментальных циклов будет такой

,

где 1, 2, 3 – хорды, 4, 5, 6, 7, 8 – ветви остова T, E – единичная матрица порядка (G) = m – n + 1, B – матрица остова T.

Р
исунок 10.1

10.4. Фундаментальные разрезы

Разрезом неорграфа G(V,E) по разбиению множества вершин V на два подмножества V₁ и V₂ называется множество ребер, соединяющих вершины из подмножества V₁ с вершинами подмножества V₂. В связном графе любой разрез не пуст.

Непустой разрез K неорграфа G называется простым или коциклом, если множество ребер K не содержит разрезов G ни по какому разбиению (любой разрез разбивает граф на две части – увеличивает число компонент связности).

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

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

Пусть имеем связный неорграф G с остовом T. И пусть b₁, b₂, …, b_i,…, b_n–1 – ветви остова T.

Удаляя произвольную ветвь b_i из T, получаем лес с двумя компонентами, т. е. каждое ребро b_i есть разрез T по некоторому разбиению вершин V₁, V₂.

В графе могут найтись еще какие–то ребра h_i1, h_i2,…, h_ij, которые соединяют V₁ и V₂.

Множество ребер K_i = {b_i, h_i1, …, h_ij} образует разрез G относительно ветви b_i, который называют фундаментальным разрезом относительно b_i остова T. Таким образом, фундаментальный разрез содержит точно одну ветвь остова графа.

Множество {K₁, K₂, …, K_n–1} всех фундаментальных разрезов графа G называется фундаментальным множеством разрезов графа G относительно остова T.

Мощность этого множества равна *(G) = n–1. (В общем случае n– , где число компонент связности графа.)

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

(a_i1, a_i2, …, a_im),

где

Из этих векторов можно составить матрицу фундаментальных разрезов.

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

где v* это *(G) = n – 1.

Таким образом ,

где H – матрица хорд графа, E – единичная матрица порядка *(G).

Матрицы фундаментальных циклов C и фундаментальных разрезов K взаимосвязаны.

Если , то ,

где – транспонированная матрица B.

Следовательно, для анализа графа достаточно найти одну матрицу (C или K), а другую можно определить транспонированием.

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

.

Р
исунок 10.2

10.5. Контрольные вопросы

1. Что такое остов графа? Приведите алгоритм построения остова минимальной длины.

2. Что такое фундаментальный цикл? Сколько таких циклов в графе? Как называется их количество?

3. Что такое фундаментальный разрез? Сколько таких разрезов в графе? Как называется их количество?

4. Что такое ранг графа? А коранг? Как их определить?

5. Какая связь существует между матрицами фундаментальных циклов и фундаментальных разрезов в графе?

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

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

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

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

• граф планарен?

• Как получить планарное изображение графа?

Если граф не планарен, то приходится удалять (переносить на другой слой, на другую плоскость) отдельные ребра.

Минимальное число ребер, которое надо удалить для получения плоского изображения, называется числом планарности графа и обозначается (G). Для полных графов с

(K_n) = (n–3)(n–4)/2.

Из формулы следует, что при n = 4 (K₄) = 0. Для K₅ (K₅) = 1, следовательно, чтобы граф K₅ стал плоским, из него надо удалить одно ребро.

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

Минимальное число плоскостей, при котором граф разбивается на плоские части, называется толщиной графа и обозначается t(G).

Толщина произвольного графа удовлетворяет неравенству

t(G) .

Здесь [x] – целая часть x.

Толщина полных графов удовлетворяет неравенству

t(K_n) .

Например, для K₅ t(K₅) = 2.

11.1. Условия планарности

Ответ на первый вопрос: – Граф планарен? – можно получить, если воспользоваться условиями планарности.

У связного плоского графа с n 3 число ребер m удовлетворяет условию

У связного плоского двудольного графа

П
ример. Полный граф K₄ (рис. 11.1, а) – планарен?

В этом графе n = 4, m = 6.

Рисунок 11.1

Подставим эти значения в условие планарности

Условие выполняется. Следовательно, граф планарен. Действительно, граф K₄ можно представить так, как показано на рис. 11.1, б.

Из рисунка ясно, что граф K₄ планарен.

Пример. Полный граф K₅ (рис. 11.1, в) – планарен?

В этом графе n = 5, m = 10.

Подставим эти значения в условие планарности

Условие не выполняется. Следовательно, граф не планарен.

Пример. Двудольный полный граф К_3,3 (рис. 11.1, г) – планарен?

В этом графе n = 6, m = 9.

Подставим эти значения в условие планарности

Условие не выполняется. Следовательно, граф не планарен.

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

Доказательство простое.

Расположим все вершины на одной прямой рис. 11.2.

Р
исунок 11.2

Построим m плоскостей на этой прямой, т. е. для каждого ребра свою плоскость.

Проведем ребра на своих плоскостях. Ребра не пересекаются (кроме как на своих вершинах).

Непланарность графов K₅ и К_3,3 используется для оценки планарности “больших графов”: граф не планарен, если он содержит подграфы вида K₅ или К_3,3, или сводимые к ним.

11.2. Грани плоского графа

У плоского графа кроме вершин и ребер можно выделить еще один геометрический образ – грань.

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

Внешняя неограниченная грань называется бесконечной гранью.

Например, граф на рис. 11.1, б обладает четырьмя гранями: f₁, f₂, f₃, f₄, где f₄ бесконечная грань.

У графа без циклов ровно одна грань – бесконечная. Не следует думать, что она какая–то исключительная. При укладке графа на сферу эта грань ничем не будет отличаться от других.

Число граней f в связном плоском графе определяется из соотношения