Презентации лекций / Презентация лекции 12 нов
.pdf
Теорема обэйлеровыхциклах
|
|
О |
|
1 |
1 |
б |
|
о |
|||
|
|||
|
|
с |
|
|
|
н |
|
|
|
о |
|
|
|
в |
|
|
|
а |
|
|
|
н |
|
|
|
и |
|
|
|
я |
3 |
3 |
2 |
2 |
11
|
|
О |
|
|
б |
|
|
о |
|
|
с |
|
|
н |
|
|
о |
|
|
в |
|
|
а |
|
|
н |
|
|
и |
Граф содержит эйлерову |
Граф имеет не болеедвух |
я |
цепь |
вершин нечетной степени |
|
12
План лекции
1.Эйлеров цикл и эйлерова цепь
2.Гамильтонов цикл и гамильтонова цепь
3.Раскраска вершин графов
4.Раскраска граней плоских графов
13
1
2
3
4
В 1859годуирландскимматематиком У. Гамильтономбыла предложенаигра «Кругосветноепутешествие»:
«Каждомуиз двадцативершиндодекаэдра приписаноназвание одногоиз крупныхгородов мира.Требуется переходяотодногогородак другомупо ребрамдодекаэдра,посетитькаждый городв точности один раз и вернуться в исходныйгород.»
Задача сводится к отысканию на графе простого цикла, проходящего через каждую вершину этого графа
14
Простойциклнаграфе,
Гамильтоновцикл
содержащийвсевершиныграфа
Граф,на котороместьгамильтоновцикл,называют гамильтоновымграфом
На этих графах есть гамильтонов цикл |
Эти графы не имеют гамильтоновых циклов |
|
|
|
|
|
|
|
|
, |
|
, |
|
|
|
|
|
1
2
3
4
15
1
2
3
4
, |
|
|
16
Задача коммивояжера
Коммивояжер должен посетить каждый из заданных городов по одному разу, выехав из некоторого из этих городов и вернувшись в него же. Требуется найти кратчайший маршрут, зная расстояния между каждой парой городов.
Пример производственной задачи
|
4 |
|
|
||
|
|
|
3 |
6 |
5 |
|
||
|
|
|
|
4 |
|
|
7
1
2
3
4
Математическая постановка
Вполном взвешенном графе найти гамильтонов цикл минимального веса.
Имеется машина (станок, компьютер) и заданий, каждое из которых она способна выполнить после соответствующей настройки. При этом необходимо затратить на переналадкуединиц временидля того, чтобы после выполнения –го задания выполнить -е. В предположении, что = , требуется найти последовательность выполнения заданий, при которой время каждой переналадки не превосходит величины .
Математическая постановка
Построим граф, множество вершин которого – множество номеров заданий, вершины с номерами и соединены ребрами, если ≤ .
Задача свелась к отысканию гамильтоновой цепи на графе.
17
План лекции
1.Эйлеров цикл и эйлерова цепь
2.Гамильтонов цикл и гамильтонова цепь
3.Раскраска вершин графов
4.Раскраска граней плоских графов
18
{ , ,…, }–
множествокрасок
Раскраска в 4 цвета
|
|
|
|
|
|
|
|
|
|
, |
|
|
|
|
|
|
|
|
1 |
|
|
|
|
длясмежныхвершин |
2 |
|
|
|
|
||
: → { , ,…, } |
|
|
|
3 |
|
|
|
|
|||
|
|
|
( ) ≠ ( ) |
||
|
|
|
4 |
||
|
|
|
|
||
|
|
|
|
|
Раскраска (правильная)вершин графа в
цветов
Раскраска в 3 цвета |
|
Раскраска в 2 цвета |
|
|
||||
|
|
|
|
|
|
|
|
В один цвет |
|
|
|
|
|||||
|
|
|
|
|
|
|
|
этот граф |
|
|
|
|
|
|
не раскрасить |
||
|
|
|
|
|
|
|
– у него есть ребра |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
, |
|
|
|
, |
|
= 2 |
|
|
|
|
|
|
|
, |
- бихроматический |
Графможнораскраситьв |
|
|
|
Графнельзяраскрасить |
|
|
|
|
|
||
цветов |
|
|
|
в − цвет |
Если χ = , |
|
|
|
|||
– хроматическое число графа ( ) |
то граф- |
||||
-хроматический |
|||||
19
Критерий |
|
|
О |
|
|
|
б |
||
бихроматичности |
1 |
1 |
||
о |
||||
|
||||
|
|
|||
|
|
|
с |
|
|
|
|
н |
|
|
|
|
о |
|
|
|
|
в |
|
|
|
|
а |
|
|
|
|
н |
|
|
|
|
и |
|
|
|
|
я |
3 |
3 |
2 |
2 |
20