Доказательство. Покажем, что это дерево.

Покажем, что это дерево.

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

От противного: пусть в есть цикл.

Рассмотрим ребро . Существует путь, который связывает и , но ребро не должно окрашиваться.

Цикла по неокрашенным ребрам быть не может, значит, – это покрывающее дерево.

Покажем, что – минимальное покрывающее дерево.

Возьмем произвольное покрывающее дерево сети .

и – разные деревья, то есть найдется ребро, которое есть в , и нет в . Пусть это ребро .

и соединяются единственной цепью . Найдется ребро в цепи , которого нет в , пусть это .

По дереву построим дерево .

Если вершины в соединены цепью, то и вершины в соединены цепью, то есть

– связный граф.

Покажем, что – покрывающее дерево.

От противного: в есть цикл .

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

Покажем, что – минимальное покрывающее дерево.

Обозначим – вес дерева.

, – минимальное покрывающее дерево.

Вес

просматривается раньше, чем . Поскольку отсутствует в , то есть в существует цепь. Это неверно, просматривается раньше , тогда

– минимальное покрывающее дерево, значит, – минимальное покрывающее дерево. имеет на одно ребро с больше, чем .

Если , то теорема доказана.

_______________________________ Орграфы _________________________________

Вопросы.

________________________________ Орграфы _________________________________

Маршрут – последовательность смежных дуг. (

В маршруте дуги могут повторяться.

Циклический маршрут – маршрут, в котором начальная вершина совпадает с конечной.

Длина маршрута – количество дуг, входящих в состав маршрута.

Путь – маршрут, в котором каждая дуга встречается не более одного раза.

Простой путь – путь, в котором каждая вершина принадлежит не более чем 2 дугам.

Контур – простой циклический путь.

Бесконтурный путь (ориентированная цепь) – простой не циклический путь.

Вершина достижима из вершины , если существует путь из в .

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

По определению считаем, что каждая вершина достижима сама из себя и удалена от себя на 0.

2 вершины взаимно достижимы, если они достижимы друг из друга.

Отношение взаимной достижимости обладает свойствами: рефлексивность, симметричность.

Отношение эквивалентности.

То можно говорить о классах отношения эквивалентности.

Слои орграфа (сильные компоненты) – классы отношения взаимной достижимости.

Сильно связный орграф – орграф с универсальным отношением взаимной достижимости.

Не одноэлементные сильные компоненты – сильно связные подграфы.

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

Сток – вершина орграф, из которой недостижима любая другая вершина. Изолированная вершина является и источником, и стоком.

База орграфа – подмножество , если любая вершина орграфа достижима из вершины базы, а любые 2 различные вершины базы не взаимно достижимы.

Фактор-граф – орграф , где – отношение взаимной достижимости. Если .

Теорема о базе. Подмножество является базой орграфа ó, когда оно образовано вершинами, взятыми по одной из каждого источника фактор-графа.