- Главная
- Математика
- Эйлеровы графы. Гамильтоновы графы
Содержание
Слайд 2
Слайд 3
Слайд 4
G
G
Слайд 5
Слайд 6
Слайд 7
Уи́льям Ро́уэн Га́мильтон –
(4 августа 1805 — 2 сентября 1865) — выдающийся ирландский
Уи́льям Ро́уэн Га́мильтон –
(4 августа 1805 — 2 сентября 1865) — выдающийся ирландский
математик, механик и физик .
Задача «кругосветного путешествия» по додекаэдру, узловые вершины которого символизировали крупнейшие города Земли
Слайд 8
Достаточные условия гамильтоновости графа
Теорема Дирака. Пусть G - неориентированный граф порядка n
Достаточные условия гамильтоновости графа
Теорема Дирака. Пусть G - неориентированный граф порядка n
и
m - минимальная степень его вершин. Если n≥3 и m ≥n/2, то G - гамильтонов граф.
m - минимальная степень его вершин. Если n≥3 и m ≥n/2, то G - гамильтонов граф.
Теорема Оре. Пусть G - неориентированный граф порядка n. Если n≥3 и deg(u)+deg(v) ≥ n для любых двух различных несмежных вершин u и v , то G - гамильтонов граф.
Если неориентированный граф G содержит гамильтонов цикл, тогда в нём не существует ни одной вершины u со степенью u < 2.
Необходимое условие гамильтоновости графа
- Предыдущая
The Great Patriotic War