29. Укладка графа на плоскости. Планарность графа. Примеры.

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

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

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

Ровно одну из граней произвольно можно выбрать внешней.

Множество граничных точек грани называется ее краем.

Каждое ребро принадлежит не более, чем 2 краям грани, каждая вершина принадлежит хотя бы одной грани.

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

1). Любой граф, не являющийся деревом, можно представить матрицей циклов и матрицей разрезов.

Матрица разрезов получается из матрицы инцидентности заменой петель на 0 и элементарными преобразованиями матриц так, чтобы первые столбцы представляли собой единичную матрицу. По строкам оставшейся части матрицы располагаются простые разрезы.

Из матрицы разрезов можно получить матрицу циклов: ЕСCC/E(C^T)E. В такой матрице по строкам располагаются простые циклы графа.

Пример:

2). Граф G^*(V^*,E^*) называется двойственным к G(V,E), если между их ребрами можно установить взаимно-однозначное соответствие, при котором некоторая матрица разрезов графа G в то же время оказалась матрицей циклов графа G^* И наоборот: некоторая матрица разрезов графа G* в то же время оказалась матрицей циклов графа G.

Отношение двойственности симметрично. Два графа, двойственные одному и тому же графу могут быть и не изоморфными.

Существуют графы, не имеющие двойственных, например, "3 дома и 3 колодца".

У графа, имеющего двойственный, каждая часть имеет двойственную часть в двойственном графе.

Граф максимально планарен, если он планарен, но утрачивает это свойство после операции добавления ребра.

Граф внешнепланарен, если он предполагает такую укладку, при которой все вершины лежат на краю одной (внешней) грани.

3). Дополнительные операции с элементами графа:

а) разбиение ребра вершиной

в) стягивание ребра

с) расщепление вершины

операция а) позволяет задать отношение гомеоморфности графов.

30. Критерии планарности графов.

КРИТЕРИИ ПЛАНАРНОСТИ ГРАФОВ.

1. Мак-Лейна. Пусть граф G(V,E) –произвольный, а G_c- его часть, полученная удалением петель, мостов и голых вершин. Граф G планарен, если часть G_c – пуста или множество ее ребер можно разбить на линейно независимую систему разрезов длины хроматического числа æ(G_с), в которых каждое ребро лежит ровно в двух разрезах.

Упрощенная формулировка была дана Эйлером: (Характеристика Эйлера).

В связном планарном графе |V|-|E|+i=2, где i – количество граней.

2. Уитни. Граф планарен, если у него есть двойственный.

3. Понтрягина – Куратовского. Граф планарен, если он не содержит частей, гомеоморфных полному графу на 5 вершинах или двудольному на 6 вершинах.

4. Харрари – Татта. Является обобщением Понтрягина-Куратовского. Планарный граф невозможно превратить в граф, гомеоморфный полному графу на 5 вершинах или двудольному на 6 вершинах ("3 дома и 3 колодца").