Планарные графы

Сентябрь 13, 2022

Главная
Математика
Планарные графы

Содержание

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. Скачать презентацию

Слайд 2

ОПРЕДЕЛЕНИЕ ПЛАНАРНОГО ГРАФА
Граф, изображенный на плоскости или на шаре, называется плоским

или планарным графом, если его ребра (дуги) не пересекаются в точках, отличных от вершин графа.

Слайд 3

ПРИМЕРЫ
1
1
3
5
2
4
4
3
5
2

Слайд 4

ЧТО ТАКОЕ «ГРАНЬ»
Гранью (страной) в плоском представлении графа называется часть

плоскости, ограниченная простым циклом и не содержащая внутри других циклов.

Слайд 5

ПРИМЕР

Слайд 6

ЭКСКУРС В ИСТОРИЮ
Интерес к планарным графам возник в эпоху великих географических

открытий: высоко ценились точные и четкие карты, но чем больше красок использовались на карте, тем она дороже. Отсюда задача: сколько красок нужно, чтобы все страны на ней, имеющие общую границу, были окрашены в разный цвет, а число этих красок было минимально?

Слайд 7

ТЕОРЕМА О 4-Х КРАСКАХ
Любую плоскую карту или карту на сфере можно

раскрасить 4-я красками так, что страны, имеющие общую границу, будут разного цвета.
Раскрасить минимальным
числом красок

Слайд 8

САМОСТОЯТЕЛЬНО РАСКРАСИТЬ МИНИМАЛЬНЫМ ЧИСЛОМ КРАСОК

Слайд 9

САМОСТОЯТЕЛЬНО
Для каких из этих тел справедлива теорема о четырех красках?

Слайд 10

ТЕОРЕМА ЭЙЛЕРА
Пусть В - количество вершин в графе, Г - количество

граней в плоском представлении графа, Р - количество рёбер в графе. Тогда получаем формулу Эйлера для связного планарного графа:
В + Г - Р = 2

Слайд 11

ПРИМЕРЫ
G1(X,U) G2(X,U)
2
5
3
1
2
4
4
3
1

Слайд 12

ФОРМУЛА ЭЙЛЕРА ДЛЯ НЕСВЯЗНОГО ГРАФА
Для несвязного планарного графа с K

компонентами связности формула Эйлера имеет вид:
В + Г - Р = K + 1.

Слайд 13

ПРИМЕР
Несвязный планарный граф с К = 3 компонентами:
1
4
2
3
8
9
7
5
6
В +

Г - Р = К + 1

Слайд 14

ТЕОРЕМА КУРАТОВСКОГО - ПОНТРЯГИНА
Граф планарен тогда и только тогда, когда он

не содержит подграфов типов, приведённых ниже:

Слайд 15

САМОСТОЯТЕЛЬНО ПРОВЕРИТЬ ПЛАНАРНОСТЬ ГРАФА
2
6
1
5
4
3
7

Слайд 16

САМОСТОЯТЕЛЬНО
Проверить планарность графов, приведенных ниже в персональных заданиях.

Слайд 17

ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ 1- 6
№ 1 № 2 № 3
№

4 № 5 № 6

26

Слайд 18

ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ 7 - 12
№ 7 № 8 № 9

№ 10 № 11 № 12

27

Слайд 19

ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ 13 - 18
№ 13 № 14 № 15

№ 16 № 17 № 18

28