Презентации лекций / Презентация лекции 12 нов
.pdf
|
|
1 |
|
|
|
2 |
|
Задача составления расписания |
3 |
||
|
|
|
4 |
|
|
Математическаяпостановка |
|
|
|
|
|
|
Нужнопрочесть несколько лекций за кратчайшее |
Построим граф, множествовершинкоторого – множество лекций, и |
|
|
время. Чтение каждой лекции в отдельности |
двевершины смежнытогда и только тогда,когда соответствующие |
|
|
занимаетодин час, но некоторые лекциине могут |
лекции нельзя читать одновременно. Любая правильнаяраскраска |
|
|
читатьсяодновременно. Составитьрасписание, |
определяет допустимое расписание(лекции «одного цвета»читаются |
|
|
при котором все лекциибудут прочитаны за |
одновременно). Оптимальное расписаниесоответствуют |
|
|
минимальное время (оптимальное расписание). |
минимальным раскраскам(а хроматическое число графа– числу |
|
|
|
часов,необходимому на прочтение всех лекций). |
|
|
|
|
|
Задача распределения оборудования |
|
|
|
Заданымножества = { , ,…, } и S = { , ,…, } работ и механизмов одновременно. Для выполнения каждой из работ требуетсянекоторое время, одинаковое для всех работ, и некоторые механизмы. При этом никакой из механизмов не может быть одновременнозанят в несколькихработах.Нужно распределить механизмы так,чтобыобщее время выполнения всех работ было минимальным.
Математическаяпостановка Построим графс множеством вершин и объявим
вершины и ( ≠ ) смежными тогда и только тогда, когда для выполнения работ и требуется хотя бы один общий механизм. При правильнойраскраске графаработы,соответствующиевершинамодного цвета,можно выполнять одновременно, а наименьшее время выполнения всех работ
достигается при минимальной раскраске.
21
План лекции
1.Эйлеров цикл и эйлерова цепь
2.Гамильтонов цикл и гамильтонова цепь
3.Раскраска вершин графов
4.Раскраска граней плоских графов
22
Проблема четырехкрасок
Достаточно ли четырех красок для такой раскраски произвольной географической карты, при которой любые две соседние страны окрашены в различные цвета?
Рассматриваются лишь те карты, в которых граница любой страны состоитиз одной замкнутой линии, а соседними считаются страны, имеющие общую границу ненулевой длины.
1
2
Гипотезачетырехкрасок 3 4
Всякая карта раскрашиваема в четыре цвета
В 1976 году заявлено о получении доказательствагипотезы.
Связный плоский |
Грани карты, имеющие |
Функция: → 1,2,…, , такая,что для |
||||||||
граф без мостов |
общее ребро, |
смежныхграней( ) ≠ |
|
( ≠ ), |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
карта |
смежные грани |
−раскраска |
|
|
||||||
23
1
2
3
Для плоского графа построим новый плоский граф 4
который назовем геометрическидвойственным к
Для этого внутри каждой грани графа выберем по одной точке .Эти точки – вершины графа . Каждому ребру
( ) поставим в соответствие кривую , которая пересекает лишь одно ребро и соединяет вершины, лежащие в гранях, границы которых содержат (таких граней может быть две или одна). Кривые – ребра графа .
|
|
Вершины геометрически |
|
Карта |
раскрашиваема |
двойственногографа можно |
|
|
|
раскрасить в |
цветов |
24