Студопедия

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

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

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






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






    Необходимость. Граф является деревом.

    1)От противного: найдутся 2 вершины, соединенные 2-мя цепями: одна цепь. Тогда существует цикл – противоречие.

    2)По индукции: для и справедливо.

    Предположим, что формула справедлива для дерева с вершинами.

    При удалении любого ребра, получим 2 компоненты связности.

    вершин в одной компоненте связности, вершин в другой.

    Число ребер в первой компоненте связности: .

    Число ребер во второй компоненте связности: .

    Тогда число ребер в исходном дереве:

    , где крайняя единица в начале равенства – удаленное ребро.

    3)Доказано через 2-е.

    Достаточность.

    1)Любые 2 вершины соединены единственной цепью, значит граф связный.

    От противного: 2 вершины, соединены 2-мя цепями, существует цикл – противоречие.

    2)Граф связный и число вершин n=m+1.

    От противного: предположим, что в есть циклы, удалим все висячие вершины (со степенью 1)

    , удалим все висячие вершины: получим граф

    Так до тех пор, пока не останется висячих вершин.

    (! – штрих) степень каждой вершины .

    По лемме о рукопожатии:

    – противоречие, так как .

    3) не содержит циклов, . Надо доказать, что – дерево.

    От противного: - не связный граф. Пусть он состоит из компонентов связности, тогда граф:

    , где , , …, .

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

    , , …, .

     

    – противоречие, так как , значит – дерево.

    Покажем, что в каждом дереве, содержащем более чем 1 вершину, имеется хотя-бы 2 висячие вершины.

    От противного:

    Возможны 2 случая:

    1)Нет висячих вершин.

    2)Одна висячая вершина.

    В дереве .

    По лемме о рукопожатии, сумма степеней вершин:

    Рассмотрим 1-й случай:

    - противоречие.

    Рассмотрим 2-й случай:

    - противоречие.






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