Алгоритм: задача построения минимального каркаса.

2) Достаточность. Предположим, что граф G(x) связен, проверим нет ли у него такого ребра, удаление которого нарушит связность. Согласно теореме 1 сам граф G(x) будет деревом, если таких рёбер нет. Если такое ребро есть, то удалим его и проверим, нет ли подобных рёбер в оставшемся частном графе и так далее. Очевидно, что через конечное число шагов мы получим граф без таких рёбер, то есть получим дерево.

Алгоритм: задача построения минимального каркаса.

1) В графе G(x) выбирается ребро, имеющее наименьшую меру. Ребро Е₁ , то есть это ребро образец частичного подграфа графа

G(x) А₁ (Е₁ А₁).

Рассмотрим первый шаг. На этом шаге к уже построенному частному графу А_i-1 добавляем ребро Е_i , имеющее минимальную меру среди всех неисследованных рёбер.

Ограничение: добавление ребра Е_i к А_i-1 не должно приводить к образованию цикла, иначе нужно брать другое ребро. Если имеется несколько рёбер с одинаковыми мерами и удовлетворяющими данному условию, то можно выбирать любое из них.

В соответствии с теоремой 1, на n-1 шаге мы построим частный подграф А_n-1 являющийся каркасом для графа G(x).

Введём доказательство от противного.

Предположим, что покрывающее дерево А_n-1 не я вляется минимальным каркасом, то есть µ(T) < µ(А_n-1). Сравним T и А_n-1 по ходу построения. Пусть Е_i первое по ходу построения ребро графа Е_i , которое не принадлежит дереву Т, присоединим это ребро к дереву Т, в результате получим объединенный граф Т Е_i . По построению граф А_n-1 также является деревом и не содержит циклов, соответственно в этом цикле должно быть хотя бы одно ребро Е’ не принадлежащее

А_n-1.

Отвергнуть Е’ мы не можем, так как он принадлежит Т. Удали ребро Е’ из графа А_n-1 , получим граф Т₁ = (Т Е_i)\Е’. После удаления ребра граф разрушится, но оставшийся граф Т₁ – покрывающий, с каркасом определяющим меру µ(T₁). Наверняка µ(T₁) µ(T), так как это минимальная мера.

2) Рассмотрим меру µ(Е_i) µ(Е’). ②

Рассмотрим в этом неравенстве случай с равенством µ(Е_i) µ(Е’). Если бы в графе была мера Е_i Е₁ , то возвращаемся на шаг 1 и выполняем соответствующие действие. Фактически имеет место равенство

µ(Е_i) = µ(Е’), соответсвенно мерой графа µ(Т₁) = µ(Т) и получим минимальное значение графа, аналогичная операция производится с графами А_n-1 и Т₁ , то есть получим решение:

Т₂ = (Т₁ Е_j)\Е”, через конечное число шагов получим каркас совпадающий с А_n-1 , являющийся минимальной мерой, то есть Т и есть минимальный каркас.

Циклический ранг

Циклический ранг (цикломатическое число) – замечательные числа графа.

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

_i = m_i – n_i + 1 (где m_i – число использованных рёбер, n_i – вершины).

1: m₁ = 1, n₁ = 2 => ₁ = 0.

Если на каждом шаге число не уменьшается, а увеличивается на единицу, то , если граф имеет m рёбер и n вершин, то _n = (G) = m – n +1 0 – это число называется цикломатическим числом графа.