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

ГЕОГРАФИЧЕСКИЕ КАРТЫ

Политическая Физическая
карта карта

Толчком, ускорившим развитие теории графов, явилась эпоха

ТЕОРЕМА О ЧЕТЫРЕХ КРАСКАХ.

Теорема (доказана программистами IBM): Любую карту, нарисованную на

ТОР

Теорема 2: Любую карту, нарисованную на торе, можно раскрасить пятью красками

КРЕНДЕЛЬ

Теорема 3: Любую карту, нарисованную на поверхности кренделя, можно раскрасить шестью

ТОПОЛОГИЯ

В топологии считается, что все тела сделаны из эластичного материала, и

ОПРЕДЕЛЕНИЕ ПЛАНАРНОГО ГРАФА

Граф, изображенный на плоскости или на шаре, называется плоским

ПРИМЕРЫ

1

1

3

5

2

4

4

3

5

2

ЧТО ТАКОЕ «ГРАНЬ»

Гранью (страной) в плоском представлении графа называется часть

ПРИМЕР

САМОСТОЯТЕЛЬНО

Определить (занумеровать) все грани на планарном графе G(X,U):

1

5

3

6

2

4

ТЕОРЕМА ЭЙЛЕРА

Пусть В - количество вершин в графе, Г - количество

ПРИМЕРЫ

G1(X,U) G2(X,U)

2

5

3

1

2

4

4

3

1

2

1

4

3

Цифрами в зеленых кружках
обозначены грани.

Выделить грани самостоятельно

ФОРМУЛА ЭЙЛЕРА ДЛЯ НЕСВЯЗНОГО ГРАФА

Для несвязного планарного графа с K

ПРИМЕР

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

1

4

2

3

8

9

7

5

6

В +

ТЕОРЕМА КУРАТОВСКОГО - ПОНТРЯГИНА

Граф планарен тогда и только тогда, когда он

САМОСТОЯТЕЛЬНО

Проверить планарность графа G(X,U), изображенного ниже.

ДВОЙСТВЕННЫЕ ГРАФЫ

Правила построения двойственного графа:
1. Каждая грань исходного графа заменяется вершиной

ПРАВИЛО ПРАВОЙ РУКИ

Построение двойственной дуги: 4 пальца указывают направление дуги исходного

ПРИМЕР

Исходный орграф Двойственный орграф

2

4

3

1

1

2

3

1

2

3

Грани исходного графа

СВОЙСТВА ДВОЙСТВЕННЫХ ГРАФОВ

Простому контуру исходного графа, «закрученному» по часовой стрелке, соответствует

СЛЕДСТВИЕ ТЕОРЕМЫ 1

Вершины любого планарного графа можно раскрасить четырьмя красками так,

САМОСТОЯТЕЛЬНО

Раскрасить вершины графа G(X,U) четырьмя красками так, чтобы цвет вершин, принадлежащих

САМОСТОЯТЕЛЬНО

Построить граф, двойственный заданному ниже смешанному графу G(X,U):

1

4

5

6

3

2

САМОСТОЯТЕЛЬНО

Определить вес дуг и ребер графа, двойственного заданному ниже взвешенному смешанному