Теоретическая часть. 
Выделение минимального остовного дерева

Рассмотрим чертеж вида.

Обозначения и определения.

V — множество точек — вершины;

X — множество линий — ребра;

Графом называется совокупность множеств вершин и ребер.

v — номер вершины;

{v, w} - обозначение ребра;

{v, v} - петли;

Одинаковые пары — параллельные или кратные ребра;

Кратностью ребер называют количество одинаковых пар.

Пример: кратность = 3.

Если в графе есть петли и/или кратные ребра, то такой граф называют псевдографом.

Псевдограф без петель называется мультиграфом.

Мультиграф в котором ни одна пара не встречается более одного раза называется графом.

Если пары (v, w) являются упорядоченными, граф называется ориентированным (орграфом).

Ребра ориентированного графа называются дугами.

В неориентированном графе ребра обозначаются неупорядоченной парой — {v, w}.

В ориентированном графе дуги обозначаются упорядоченной парой — (v, w).

G, G₀ — неориентированный граф, D, D₀ — ориентированный.

Обозначают v, w — вершины, x, y, z — дуги и ребра.

Пример

1) V={v₁, v₂, v₃, v₄},.

X={x₁=(v₁, v₂), x₂=(v₁, v₂), x₃=(v₂, v₂), x₄=(v₂, v₃)}.

2) V={v₁, v₂, v₃, v₄, v₅},.

X={x₁={v₁, v₂}, x₂={v₂, v₃}, x₃={v₂, v₄}, x₄={v₃, v₄}}.

Подграфом графа G называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G. (Для орграфа то же).

Подграф наз. собственным, если он отличен от самого графа.

Говорят, что вершина w орграфа D (графа G) достижима из верш. v, если либо w=v, либо существует путь (маршрут) из v в w.

Граф (орграф) наз связным (сильно связным), если для любых двух его вершин v, w существует маршрут (путь), соединяющий v и w.

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

Псевдографом, ассоциированным с ориентированным псевдографом D=(V, X) наз. псевдограф G=(V, X₀), в котором X₀ получается из X заменой всех упорядоченных пар (v, w) на неупорядоченные {v, w}.

Орграф наз слабо связным, если связным является ассоциированный с ним псевдограф.

Если граф (орграф) не является связным (слабо связным), то он наз. несвязным.

Компонентой связности графа G (сильной связности орграфа D) наз. его связный (сильно связный) подграф, не являющийся собственным подграфом никакого другого связного (сильно связного) подграфа графа G (орграфа D).

Примеры.

опр || назовем орграф D=(V, X) нагруженным, если на множестве дуг X определена некоторая функция, которую называют весовой функцией.

Числа — вес дуги, (цена дуги).

Для любого пути П нагруженного орграфа D обозначим через l(П) сумму длин дуг, входящих в путь П. (Каждая дуга считается столько раз, сколько она входит в путь П).

Величина l называется длиной пути. Если выбрать веса равными 1, то придем к ненагруженному графу.

Деревья и циклы.

Граф G называется деревом, если он является связным и не имеет циклов. Граф G называется лесом, если все его компоненты связности — деревья.

Деревья обладают следующими свойствами:

• 1) Граф G есть дерево.
• 2) Граф G является связным и не имеет простых циклов.
• 3) Граф G является связным и число его ребер ровно на 1 меньше числа вершин.
• 4) две различные вершины графа G можно соединить единственной (и при этом простой) цепью.
• 5) Граф G не содержит циклов, но, добавляя к нему любое новое ребро, получаем ровно один и притом простой цикл.

Если у дерева G имеется, по крайней мере, 1 ребро, то у него найдется висячая вершина.

Предположим, что в графе G нет висячей вершины, тогда найдется цикл (в начале лекции это было доказано), тогда граф — не дерево.

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

Пусть G — дерево с n-вершинами и m-ребрами. Тогда m (G)=n (G)-1.

Если m.

Если m>n-1, и висячих вершин в графе нет, то можно выделить цикл, а следовательно, это — не дерево. В противном случае удалим висячую вершину вместе с инцидентным ей ребром. Повторяя эту операцию n-2 раза, придем к графу с двумя вершинами и более чем одним ребром это не дерево.

Пусть G — дерево. Тогда любая цепь в G будет простой.

Если цепь — не простая, то в G есть циклы G — не дерево.

Цепь единственна по той же причине.

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

Пусть G — связный граф. Тогда остовное дерево графа G должно содержать n (G)-1 ребер. Значит, для получения остовного дерева из графа G нужно удалить ребер. Число называется цикломатическим числом графа G.