Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Доказательство. Покажем, что это дерево.
Покажем, что это дерево. – произвольные вершины. Тогда, в сети существует цепь, соединяющая . Каждое ребро или окрашивается, или не окрашивается. Если окрашивается, то все вершины входят в одну компоненту, если не окрашивается, то уже принадлежат компоненте, то есть существует путь, который связывает вершины и . Тогда – связный граф, осталось доказать, что он без циклов. От противного: пусть в есть цикл. Рассмотрим ребро . Существует путь, который связывает и , но ребро не должно окрашиваться. Цикла по неокрашенным ребрам быть не может, значит, – это покрывающее дерево. Покажем, что – минимальное покрывающее дерево. Возьмем произвольное покрывающее дерево сети . и – разные деревья, то есть найдется ребро, которое есть в , и нет в . Пусть это ребро . и соединяются единственной цепью . Найдется ребро в цепи , которого нет в , пусть это . По дереву построим дерево . Если вершины в соединены цепью, то и вершины в соединены цепью, то есть – связный граф. Покажем, что – покрывающее дерево. От противного: в есть цикл . Тогда должен содержать ребро , то этот цикл будет в и ребро , иначе, этот цикл будет в . – связный граф без циклов. – покрывающее дерево. Покажем, что – минимальное покрывающее дерево. Обозначим – вес дерева. , – минимальное покрывающее дерево. Вес просматривается раньше, чем . Поскольку отсутствует в , то есть в существует цепь. Это неверно, просматривается раньше , тогда – минимальное покрывающее дерево, значит, – минимальное покрывающее дерево. имеет на одно ребро с больше, чем . Если , то теорема доказана. _______________________________ Орграфы _________________________________ Вопросы. ________________________________ Орграфы _________________________________ Маршрут – последовательность смежных дуг. ( В маршруте дуги могут повторяться. Циклический маршрут – маршрут, в котором начальная вершина совпадает с конечной. Длина маршрута – количество дуг, входящих в состав маршрута. Путь – маршрут, в котором каждая дуга встречается не более одного раза. Простой путь – путь, в котором каждая вершина принадлежит не более чем 2 дугам. Контур – простой циклический путь. Бесконтурный путь (ориентированная цепь) – простой не циклический путь. Вершина достижима из вершины , если существует путь из в . Если вершина достижима из вершины , то расстоянием от до называется длина кратчайшего пути из в . По определению считаем, что каждая вершина достижима сама из себя и удалена от себя на 0. 2 вершины взаимно достижимы, если они достижимы друг из друга. Отношение взаимной достижимости обладает свойствами: рефлексивность, симметричность. Отношение эквивалентности. То можно говорить о классах отношения эквивалентности. Слои орграфа (сильные компоненты) – классы отношения взаимной достижимости. Сильно связный орграф – орграф с универсальным отношением взаимной достижимости. Не одноэлементные сильные компоненты – сильно связные подграфы. Источник – вершина орграфа, недостижимая из любой другой вершины. Сток – вершина орграф, из которой недостижима любая другая вершина. Изолированная вершина является и источником, и стоком. База орграфа – подмножество , если любая вершина орграфа достижима из вершины базы, а любые 2 различные вершины базы не взаимно достижимы. Фактор-граф – орграф , где – отношение взаимной достижимости. Если . Теорема о базе. Подмножество является базой орграфа ó, когда оно образовано вершинами, взятыми по одной из каждого источника фактор-графа.
|