Плоские графы.

Два графа называются изоморфными, если у них:

a. Совпадает число вершин

b. Совпадает число рёбер.

c. Две вершины первого графа соединены ребром тогда и только тогда, когда две соответствующие вершины второго графа соединены ребром.

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

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

Примеры:

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

Пример:

(1,2,6,1), (6,2,5,7,6), (6,7,5,6) и т.д. являются гранями плоского представления графа.

(6,2,5,6) – не является.

(1,2,3,4,5,6,1) с внешней стороны является бесконечной гранью плоского графа.

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

Как особый случай вводится бесконечная грань в плоском представлении дерева и леса. В этом случае за грань принимают всю плоскость рисунка.

Мост в графе, соединяющий циклы называется перегородкой.

Простой цикл, ограничивающий грань называется границей этой грани.

Грани называются соседними, если их границы имеют общее ребро.

Теорема 8 (Эйлера):

Для любого плоского представления связного плоского графа без перегородок справедлива формула:

В – р + г = 2,

где в, р, г – число вершин, рёбер, граней в плоском представлении графа.

Доказательство:

Преобразуем граф в дерево с теми же вершинами, разрывая некоторые рёбра.

Удалим AK, число рёбер уменьшилось на единицу, число граней уменьшится на единицу, но р – г = const.

После того, как мы получим дерево будет по-прежнему справедливо равенство: p – r = р_д – г_д.

В дереве г_д=1, а значит р–г=р_д–1 (*)

По теореме о деревьях в_д–р_д=1, но количество вершин не изменилось, т.е. в=в_д, а значит в–р_д=1 или р_д=в–1 (**)

подставим (**) в (*): р-г=в-1-1

Отсюда получаем доказываемую формулу: в–р+г=2

Графом типа 1 называется граф вида:

			У этих графо имеются вершины и на рёбрах

 

 

2. Графом типа 2 называется граф вида:

 

 

Теорема 9. Понтрягина – Куратовского:

Граф является плоским тогда и только тогда, когда он не имеет подграфом графа типа 1 и графа типа 2. (без доказательства).

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

Свойства максимально плоского графа:

1. все грани максимально плоского графа – треугольники.

2. У максимально плоского графа имеются три внешних ребра. (AB, BC, CA)