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

Определение 1. Граф G(X,T) называется плоским, если его можно изобразить на плоскости так, чтобы никакие два его ребра не имели других общих точек, кроме их общей вершины. Чертеж графа, на котором никакие два ребра не пересекаются, называют плоским представлением графа.

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

Пример 1. Дан граф

Его плоским представлением является граф

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

Примером неплоского графа может служить полный граф с пятью вершинами.

Любые попытки начертить его плоское представление обречены на неудачу.

Определение 2. Гранью в плоском представлении графа G(X,T) называется часть плоскости, ограниченная простым циклом и не содержащая внутри других циклов.

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

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

Пример 2.

Данный граф имеет четыре обычные грани, ограниченные циклами (x ₁, x ₂, x ₆, x ₁), (x ₅, x ₆, x ₇, x ₅), (x ₂, x ₃, x ₄, x ₅, x ₂), (x ₂, x ₅, x ₇, x ₆, x ₂), и одну бесконечную грань, ограниченную циклом (x ₁, x ₂, x ₃, x ₄, x ₅, x ₆, x ₁). Грани (x ₁, x ₂, x ₆, x ₁) и (x ₂, x ₅, x ₇, x ₆, x ₂) являются соседними, а грани (x ₁, x ₂, x ₆, x ₁) и (x ₂, x ₃, x ₄, x ₅, x ₂) соседними не являются. Часть плоскости, ограниченная простым циклом (x ₂, x ₅, x ₆, x ₂), не является гранью, так как содержит внутри себя цикл (x ₅, x ₆, x ₇, x ₅).

Пример 3.

В данном графе часть плоскости, ограниченная простым циклом (x ₁, x ₂, x ₃, x ₄, x ₁), является гранью, так как ребро (x ₁, x ₅), расположенное внутри грани, не является циклом.

Пример 4.

Часть плоскости, заключенная между циклами (x ₁, x ₂, x ₃, x ₄, x ₅, x ₁) и (x ₆, x ₇, x ₈, x ₆), не является гранью, так как она содержит внутри себя цикл и к тому же она не ограничена циклом. Ребро (x ₁, x ₆) является мостом, соединяющим два цикла.

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

Пример 5.

Данный граф не имеет бесконечной грани, так как она не ограничена изнутри простым циклом. Мост (x ₁, x ₂) является перегородкой.

В плоском представлении дерева за грань принимают всю плоскость чертежа.

Для всякого плоского графа без перегородок число вершин n, число ребер m и число граней с учетом бесконечной g связаны соотношением n - m + g = 2, которое называется формулой Эйлера.

Определение 6. Плоский граф G(X,T) называется максимально плоским, или триангулированным, если к нему невозможно добавить ни одного ребра так, чтобы полученный граф был плоским.

Пример 6. Рассмотрим граф

Данный граф можно сделать максимально плоским:

Каждая грань в плоском представлении максимально плоского графа имеет три вершины.

Определение 7. Операция добавления новых ребер, в результате которой в плоском представлении графа каждая грань имеет ровно три вершины, называется триангуляцией графа.

Теорема. Для любого плоского графа G(X,T) существует плоское представление, в котором все ребра - прямолинейные отрезки.