Содержание
- 2. ОПРЕДЕЛЕНИЕ ПЛАНАРНОГО ГРАФА Граф, изображенный на плоскости или на шаре, называется плоским или планарным графом, если
- 3. ПРИМЕРЫ 1 1 3 5 2 4 4 3 5 2
- 4. ЧТО ТАКОЕ «ГРАНЬ» Гранью (страной) в плоском представлении графа называется часть плоскости, ограниченная простым циклом и
- 5. ПРИМЕР
- 6. ЭКСКУРС В ИСТОРИЮ Интерес к планарным графам возник в эпоху великих географических открытий: высоко ценились точные
- 7. ТЕОРЕМА О 4-Х КРАСКАХ Любую плоскую карту или карту на сфере можно раскрасить 4-я красками так,
- 8. САМОСТОЯТЕЛЬНО РАСКРАСИТЬ МИНИМАЛЬНЫМ ЧИСЛОМ КРАСОК
- 9. САМОСТОЯТЕЛЬНО Для каких из этих тел справедлива теорема о четырех красках?
- 10. ТЕОРЕМА ЭЙЛЕРА Пусть В - количество вершин в графе, Г - количество граней в плоском представлении
- 11. ПРИМЕРЫ G1(X,U) G2(X,U) 2 5 3 1 2 4 4 3 1
- 12. ФОРМУЛА ЭЙЛЕРА ДЛЯ НЕСВЯЗНОГО ГРАФА Для несвязного планарного графа с K компонентами связности формула Эйлера имеет
- 13. ПРИМЕР Несвязный планарный граф с К = 3 компонентами: 1 4 2 3 8 9 7
- 14. ТЕОРЕМА КУРАТОВСКОГО - ПОНТРЯГИНА Граф планарен тогда и только тогда, когда он не содержит подграфов типов,
- 15. САМОСТОЯТЕЛЬНО ПРОВЕРИТЬ ПЛАНАРНОСТЬ ГРАФА 2 6 1 5 4 3 7
- 16. САМОСТОЯТЕЛЬНО Проверить планарность графов, приведенных ниже в персональных заданиях.
- 17. ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ 1- 6 № 1 № 2 № 3 № 4 № 5 № 6
- 18. ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ 7 - 12 № 7 № 8 № 9 № 10 № 11 №
- 19. ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ 13 - 18 № 13 № 14 № 15 № 16 № 17 №
- 21. Скачать презентацию