Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






  • Как продвинуть сайт на первые места?
    Вы создали или только планируете создать свой сайт, но не знаете, как продвигать? Продвижение сайта – это не просто процесс, а целый комплекс мероприятий, направленных на увеличение его посещаемости и повышение его позиций в поисковых системах.
    Ускорение продвижения
    Если вам трудно попасть на первые места в поиске самостоятельно, попробуйте технологию Буст, она ускоряет продвижение в десятки раз, а первые результаты появляются уже в течение первых 7 дней. Если ни один запрос у вас не продвинется в Топ10 за месяц, то в SeoHammer за бустер вернут деньги.
    Начать продвижение сайта
  • Доказательство. Покажем, что это дерево.






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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Вес

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

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

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

    _______________________________ Орграфы _________________________________

    Вопросы.

    ________________________________ Орграфы _________________________________

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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






    © 2023 :: MyLektsii.ru :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.