Планарные графы презентация

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

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

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

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

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

В + Г - Р = 2

G2(X,U)

2

5

3

1

2

4

4

3

1

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

Несвязный планарный граф с К = 3 компонентами:

1

4

2

3

8

9

7

5

6

В + Г - Р = К + 1

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

№ 2 № 3

№ 4 № 5 № 6

26

№ 8 № 9

№ 10 № 11 № 12

27

№ 14 № 15

№ 16 № 17 № 18

28

№ 20 № 21

№ 22 № 23 № 24

29