�ݺ�ߣ

1. Дискретные структуры МФТИ, осень 2013 Александр Дайняк www.dainiak.com

2. Задача о раскраске карт Исторически первая задача о раскраске: • Сколько цветов достаточно использовать в типографии, чтобы можно было напечатать любую географическую карту (так, чтобы граничащие друг с другом страны не сливались на карте)?

3. Задача о раскраске планарных графов Задачу о раскраске карт можно переформулировать на языке раскрасок, рассмотрев планарный граф, двойственный карте: • Сколькими цветами можно правильно раскрасить любой планарный граф?

4. Задача о раскраске планарных графов Задачу о раскраске карт можно переформулировать на языке раскрасок, рассмотрев планарный граф, двойственный карте: • Сколькими цветами можно правильно раскрасить любой планарный граф?

5. Хроматическое число планарного графа

7. Доказательство теоремы о пяти красках

15. Соседи

16. Паросочетания Паросочетание в графе — это подмножество рёбер без общих концов.

17. Паросочетания в двудольных графах

18. Условия Холла

19. Теорема Холла

20. Доказательство теоремы Холла

25. Следствия теоремы Холла

26. Следствия теоремы Холла

27. Хроматический индекс двудольных графов

�ݺ�ߣ

Теорема о 5 красках. Теорема Холла.

Recommended

More Related Content

Viewers also liked (13)

More from Alex Dainiak (19)

Теорема о 5 красках. Теорема Холла.