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

Физическая
карта карта

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

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

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

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

потому их можно сжимать и растягивать и они не порвутся. Такие деформации зовутся гомеоморфизмом.




Т.о. топология изучает свойства гомеоморфных тел.

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

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

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

В + Г - Р = 2

G2(X,U)

2

5

3

1

2

4

4

3

1

2

1

4

3

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

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

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

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

1

4

2

3

8

9

7

5

6

В + Г - Р = К + 1

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

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

двойственного.
Если граф неориентированный, то каждое ребро исходного графа заменяется пересекающим его ребром двойственного.
Если исходный граф ориентированный, то каждая дуга исходного графа заменяется пересекающей ее дугой двойственного графа по «правилу правой руки».
Если исходный граф является взвешенным, то вес каждого ребра (дуги) двойственного графа равен весу ребра (дуги), которую оно (она) пересекает.

графа, а большой палец – двойственного.

вершина-источник двойственного графа.
Простому контуру исходного графа, «закрученному» против часовой стрелки, соответствует вершина-сток двойственного графа.
Грани исходного графа, образованной встречно ориентированными дугами, соответствует вершина двойственного графа, которой инцидентны, как заходящие, так и исходящие дуги.

что цвет вершин, принадлежащих любому ребру, будет различным.

1

6

5

4

3

2

любому ребру, был различным.

2

1

3

4

5

графу G(X,U):

1

4

5

6

3

2

5 7


4 1 3 2 6 9





8 2