Студопедия

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

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

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






Гамильтонов граф. Достаточное условие гамильтоновости графа.






Гамильтонов цикл – простой путь длины .

Цепь (не циклический простой путь) может иметь ребер.

Гамильтонов граф – граф, содержащий гамильтонов цикл.



Теорема. Достаточное условие Гамильтоновости графа.

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

Следствие.

Если в связном графе с числом вершин степень любой вершины , то граф гамильтонов.

Доказательство. Без доказательства.

Алгоритм построения минимального покрывающего дерева сети. Теорема о корректности алгоритма.

Сеть – связный граф , с положительными весами на ребрах.

Покрывающее дерево - , где .

Весом сети называется сумма весов всех ребер.

Минимальное покрывающее дерево сети – покрывающее дерево сети, имеющее наименьший вес среди всех покрывающих сетей.






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