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