Материал: Дискретная математика. учебное пособие. Собенина О.В

6) Всякая пара вершин соединена цепью и притом только одной.

Из теоремы 4.11.1 вытекает следствие.

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

Доказательство. Действительно, если i-я компонента связности С_i графа G содержит n_i вершин, то по теореме 4.11.1. соответствующее дерево К_i остова содержит n_i–1 ребро. Следовательно, для получения К_i из компоненты С_i нужно уда­лить m_i – (n_i – 1) ребер, где m_i – число ребер в C_i. Сумми­руя удаляемые ребра по всем компонентам связности и замечая, что получаем, что необходимо удалить ребер.

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

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

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

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

Введем определение ориентированного дерева. Ориентированное дерево (древовидность) представляет собой орграф без контуров, в котором полустепень захода каждой вершины, за исключением одной (например, r), равна 1, а полустепень захода вершины r равна 0. Вершина r называется корнем дерева.

На рис. 4.31 показан граф, который является ориентированным деревом с корнем в вершине x₁. Из приведенного определения следует, что ориентированное дерево с n вершинами содержит n – 1 дугу и связно.

Рис. 4.31. Ориентированное дерево

Следует отметить, что неориентированное дерево можно преображать в ориентированное: надо взять его произвольную вершину в качестве корня и ребрам приписать такую ориентацию, чтобы каждая вершина соединялась с корнем (только одной) простой цепью. Обратно, если T=(X,V) – ориентированное дерево, то T = (X, V), где V – множество дуг дерева Т без учета их ориентации, является неориентированным деревом.

Рассмотрим два остовных дерева T₁=(X,A₁) и Т₂=(Х,А₂) графа G. Преобразование дерева T₁ в дерево Т₂ называется элементарным преобразованием дерева, если дерево Т₂ можно получить из дерева T₁, удалив из T₁ дугу (ребро) а₁ и добавив дугу (ребро) a₂ (a₁А₁, a₂A₂). В этом случае считают что расстояние между T₁ и Т₂ d(Т₁,Т₂)=1. Если T₂ можно получить из T₁ с помощью k элементарных преобразований, то d(T₁,T₂)=k.

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

Кратчайший остов графа G – это остов, у которого сумма весов ребер наименьшая.

4.11.2. Алгоритм построения остова неорграфа

Замечание. Процедура основана на просмотре в произвольном порядке ребер исходного графа и может быть представлена как процесс окрашивания их. При этом синий цвет используется для окраски ребер, включаемых в остов, а красный – для окраски ребер, не включаемых в остов. При рассмотрении ребра осуществляется проверка того, не образует ли данное ребро в совокупности с ребрами, уже включенными в остов, цикл. Эта проверка осуществляется следующим образом. Ребра, включенные в остов, составляют граф, имеющий одну или несколько компонент связности. Вершины, принадлежащие отдельно взятой компоненте, объединяются в совокупность, которую будем называть «букетом». Некоторое ребро образует цикл с ребрами, уже включенными в остов, если обе его концевые вершины принадлежат одному и тому же букету.

Результаты работы алгоритма удобно записывать в таблицу:

Шаг 1. Выбрать любое ребро, не являющееся петлей. Окрасить его в синий цвет и сформировать букет, включив в него концевые вершины окрашенного ребра.

Шаг 2. Выбрать любое неокрашенное ребро, не являющееся петлей. Если в графе такого ребра нет, то останов. Исходный граф не содержит остова. Иначе перейти к шагу 3.

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

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

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

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

Шаг 4. Если все вершины графа вошли в один букет, то останов - синие ребра образуют остов. Иначе перейти к шагу 2.

Также существуют алгоритмы порождения всех остовных деревьев произвольного неориентированного графа. В некоторых ситуациях возникает необходимость в построении полного списка остовных деревьев графа G. Например, в том случае, когда надо отобрать «наилучшее» дерево, а критерий, позволяющий осуществить такой отбор, является очень сложным (или даже частично субъективным), так что непосредственное решение задачи оптимизации (не использующее перечисление всех остовных деревьев) оказывается невыполнимым.

П оскольку число остовых деревьев графа очень быстро растет с ростом числа его ребер, то, очевидно, нужен эффективный метод порождения исчерпывающего, но без повторений, списка остовых деревьев. Один из таких способов состоит в использовании элементарных преобразований деревьев для последовательного порождения остовов, начиная с некоторого начального остова Т₀. Методы, основанные на этом принципе, даны в работах Пауля, Чена и других. Однако процедурам, опирающимся на элементарные преобразования деревьев, присущ следующий недостаток: для порождения нового элемента дерева необходимо привлекать все найденные ранее деревья. Очевидно, что наилучшим будет такой алгоритм порождения всех остовов графа, когда список остовов строится без повторений и построенные остовы записываются во вспомогательную память, но в процессе работы алгоритма из этой памяти ничего не берется. В [2] описан такой алгоритм.

Пример. Для графа, изображенного на рис. 4.32, все остовные деревья приведены на рис. 4.33.

Рис. 4.32

Легко проверить, что у графа, изображенного на рис. 4.32, действительно 21 остов.

1 2 3 4 5 6 7

8 9 10 11 12 13 14

15 16 17 18 19 20 21

Рис. 4.33. Все остовы графа, изображенного на рис. 4.32

4.11.3. Кратчайшие остовы

Иногда дугам графа G сопоставляются (приписываются) чис­ла  дуге (х_i, х_j) ставится в соответствие некоторое число называемое весом, длиной или стоимостью (ценой) дуги. Тогда граф G называется графом со взвешенными дугами. Иногда веса (числа ) приписываются вершинам х_i графа, и тогда полу­чается граф со взвешенными вершинами. Если в графе веса при­писаны и дугам, и вершинам, то он называется просто взвешенным.

П ри рассмотрении пути , представленного последовательно­стью дуг (v₁, v₂,. . ., v_q), за его вес (длину, стоимость) принимается число l( ), равное сумме весов всех дуг, входящих в , т. е.

Таким образом, когда слова «длина», «стоимость», «цена» и «вес» применяются к дугам, то они эквивалентны по содержанию, и в каждом конкретном случае выбирается такое слово, которое ближе подходит по смыслу и совпадает с принятым в литературе. Длиной (или мощностью) пути называется число дуг, входя­щих в него.

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

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

Рассмотрим алгоритм Прима построения кратчайшего остова взвешенного графа.

Шаг 1. Рассмотрим граф с матрицей весов (матрица смежности, в которой элементы, индексы которых соответствуют смежным вершинам, равны не единице, а весу соответствующего ребра). Множество вершин остова положим , - произвольно выбранная вершина. А множество ребер 

Шаг 2. Для каждой вершины найти вершину , такую, что . И приписать вершине х_j пометку [ ]. Если такой вершины нет, т.е. то приписать вершине пометку [0, ]. Перейти к шагу 3.

Шаг 3. Выбрать вершину , такую, что , и положить множество и . Если , то останов – ребра в множестве образуют кратчайший остов, иначе перейти к шагу 4.

Шаг 4. Для всех вершин и таких, что обновить пометки следующим образом: если , то , . Перейти к шагу 3.