Остов – минимальное множество ребер, которые связывают все вершины связного графа.
Остов это дерево. Часть G ' графа G называется остовом (каркасом, скелетом), если V ’ = V и все они связаны без циклов. Остов обычно обозначают буквой T. Для орграфов остов – часть G, которая является остовом в неорграфе, полученном из G удалением ориентации дуг.
Остов получается из графа разрушением циклов. Число удаляемых при этом ребер: (G) = m – n + 1 – называется цикломатическим числом или цикломатическим рангом графа (или просто рангом графа).
Если граф состоит из нескольких компонент, то его остов лес, а число удаляемых при определении остова ребер будет равно:
(G) = m – n + ρ,
где ρ – количество компонент связности графа.
Количеств ребер в остове графа:
*(G) = n – ρ
называется коциклическим рангом.
(У связного графа *(G) = n – 1.)
Для дерева цикломатическое число равно 0.
Нахождение остова минимальной длины
Имеется связный граф G (V, E):
1) Строим начальный остов Ti, который состоит из всех вершин и одного ребра с минимальным весом.
|
|
2) Имеем Ti, среди всех ребер находим ребро с минимальным весом такое, которое смежно с одним из ребер из Ti и которое не образует циклов. Добавляем его к Ti.
3) Повторяем п. 2, пока находятся нужные ребра.
Фундаментальным циклом графа G (V, E) с остовным деревом T (V, E ') называется простой цикл, получаемый в результате добавления к T одного из ребер G, не принадлежащего E '. Количество фундаментальных циклов графа G = (V, E) при любом остовном дереве T равно цикломатическому числу (G).
Пусть G (V, E) связный неорграф с n вершинами и m ребрами, T – остов графа, имеющий n – 1 ребро, которые называются ветвями T (ведь остов – это дерево) и обозначаются bj.
Не входящие в остов (G) = m – n + 1 ребер называются хордами и обозначаются hi.
Если к дереву T добавить произвольную хорду hi, то образуется точно один цикл Ci. Этот цикл состоит из хорды hi и некоторых ветвей остова, образующих простую цепь и соединяющих вершины хорды hi.
Цикл Ci называется фундаментальным циклом графа G относительно хорды hi остова T (в общем случае остовов в графе может быть много). Таким образом, фундаментальный цикл содержит точно одну хорду остова графа.
Множество всех фундаментальных циклов { C 1, C 2, …, C i, …, Cm – n +1} относительно хорд остова T называется фундаментальным множеством циклов графа G. Мощность этого множества равна цикломатическому числу (G) = m – n +1 или рангу графа G.
фундаментальное множество циклов графа можно задать с помощью матрицы, строки которой имеют вид
h 1, h 2, …, hm – n +1, b 1, b 2, …, bn –1,
где hi, bj – хорды и ветви соответственно.
В каждом цикле имеется одна хорда hi и некоторое множество ветвей остова T. Этой хорде hi и ветвям, входящим в цикл Ci, присвоим значение 1, остальным ребрам графа присвоим значение 0. Повторяя процедуру для всех хорд, получим матрицу строк из 0 и 1.
|
|
Разрезом неорграфа G (V, E) по разбиению множества вершин V на два подмножества V 1 и V 2 называется множество ребер, соединяющих вершины из подмножества V 1 с вершинами подмножества V 2. В связном графе любой разрез не пуст.
Непустой разрез K неорграфа G называется простым или коциклом, если множество ребер K не содержит разрезов G ни по какому разбиению (любой разрез разбивает граф на две части – увеличивает число компонент связности).
В связном неорграфе остов T имеет, по крайней мере, одно общее ребро с любым разрезом графа.
В связном неорграфе любой цикл имеет с любым разрезом, проходящим через ребра цикла, четное число ребер.
Пусть имеем связный неорграф G с остовом T. И пусть b 1, b 2, …, bi,…, bn –1 – ветви остова T.
Удаляя произвольную ветвь bi из T, получаем лес с двумя компонентами, т. е. каждое ребро bi есть разрез T по некоторому разбиению вершин V 1, V 2.
В графе могут найтись еще какие–то ребра hi 1, hi 2,…, hij, которые соединяют V 1 и V 2.
Множество ребер Ki = { bi, hi 1, …, hij } образует разрез G относительно ветви bi, который называют фундаментальным разрезом относительно bi остова T. Таким образом, фундаментальный разрез содержит точно одну ветвь остова графа.
Множество { K 1, K 2, …, Kn –1} всех фундаментальных разрезов графа G называется фундаментальным множеством разрезов графа G относительно остова T.
Мощность этого множества равна *(G) = n –1. (В общем случае n – , где число компонент связности графа.)
По аналогии с фундаментальными циклами, каждому фундаментальному разрезу можно поставить в соответствие вектор
(ai 1, ai 2, …, aim),
где
Из этих векторов можно составить матрицу фундаментальных разрезов.
Поскольку каждый фундаментальный разрез содержит точно одну ветвь T, то матрица K имеет вид:
hi,j – хорды | bi – ветви T | ||||||||
K 1 | h 1,1 | . | h 1,V* | . | |||||
K = | . | h 2,1 | . | h 2,V* | . | ||||
. | . | . | . | . | . | . | . | . | |
K V* | h V*,1 | . | h V*,V* | . |
где v* это *(G) = n – 1.
Таким образом , где H – матрица хорд графа, E – единичная матрица порядка *(G).
Матрицы фундаментальных циклов C и фундаментальных разрезов K взаимосвязаны.
Если , то ,
где – транспонированная матрица B.
Следовательно, для анализа графа достаточно найти одну матрицу (C или K), а другую можно определить транспонированием.
Планарные графы
Планарный граф – это граф, допускающий укладку на плоскости, т.е. он может быть изображен на плоскости так, что никакие ребра не имеют общих точек, кроме своих вершин. Изображение графа на плоскости с соблюдением этого условия называется плоским графом.
Планарность нужна, например, для реализации печатного монтажа, в процессе разработки которого схема устройства представляется в виде графа: элементы – вершины, связи между выводами элементов – ребра.
Если граф не планарен, то приходится удалять (переносить на другой слой, на другую плоскость) отдельные ребра. Минимальное число ребер, которое надо удалить для получения плоского изображения, называется числом планарности графа и обозначается (G). Для полных графов с
(Kn) = (n –3)(n –4)/2.
Из формулы следует, что при n = 4 (K 4) = 0. Для K 5 (K 5) = 1, следовательно, чтобы граф K 5 стал плоским, из него надо удалить одно ребро.
При перенесении на вторую плоскость, перенесенная часть может опять оказаться не плоской. Тогда отдельные ребра переносят на новую плоскость и т.д. Минимальное число плоскостей, при котором граф разбивается на плоские части, называется толщиной графа и обозначается t (G).
Толщина произвольного графа удовлетворяет неравенству
|
|
t (G) .
Здесь [ x ] – целая часть x.
Толщина полных графов удовлетворяет неравенству
t (Kn) .
Например, для K 5 t (K 5) = 2.
Ответ на первый вопрос: – Граф планарен? – можно получить, если воспользоваться условиями планарности.
У связного плоского графа с n 3 число ребер m удовлетворяет условию
У связного плоского двудольного графа
У плоского графа кроме вершин и ребер можно выделить еще один геометрический образ – грань. Область плоскости, ограниченная ребрами связного плоского графа и не содержащая внутри себя ни ребер, ни вершин, называется его гранью. Внешняя неограниченная грань называется бесконечной гранью. У графа без циклов ровно одна грань – бесконечная. Не следует думать, что она какая–то исключительная. При укладке графа на сферу эта грань ничем не будет отличаться от других.
Число граней f в связном плоском графе определяется из соотношения:
f = m – n + 2,
где n – число вершин, m – число ребер.
Пусть задана часть G 1 = (V 1, E 1) графа G = (V, E).
Будем называть кускомграфа G относительно G 1:
1) ребро вместе с его концами,которые принадлежат V 1,
2) а также компоненту связности G’i = (V’i, E’i) подграфа, порожденного подмножеством вершин V \ V l, дополненную всеми ребрами, инцидентными вершинам из V'i, и всеми вершинами этих ребер, принадлежащими V 1, которые называются «контактными точками»;
Алгоритм использует последовательный процесс присоединения к некоторому плоскому подграфу цепи , оба конца которой (и только они) – вершины . Эта цепь разобьет одну из граней на две.
В качестве начального плоского графа выбирают некоторый цикл графа G. Чтобы перейти от подграфа к , предварительно рассматривают все куски Pj графа G относительно .Грань fk графа и кусок Рj совместимы, если все его контактные точки принадлежат множеству вершин этой грани.
Для каждого куска определяем грани, которые с ним совместимы. Возможны три случая:
1) Некоторый кусок не совместим ни с какой гранью графа . Тогда граф не плоский.
2) Какой–либо кусок совместим с единственной гранью fk графа . Тогда выберем в этом куске цепь такую, что оба ее конца (и только они) принадлежат . Дополняя ребрами и вершинами этой цепи, получаем , проводя внутри грани fk.
|
|
3) Если каждый из кусков Рj совместим, по крайней мере, с двумя гранями графа , то можно выбрать цепь в любом из кусков и действовать как в случае 2.