Пример.

Пример.

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

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

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

Саму диаграмму называют плоским графом.

Замечание.Одни графы можно нарисовать на плоскости так, чтобы их ребра не имели общих точек, кроме вершин им принадлежащим; другие так рисовать нельзя.В силу этого отдельные графы могут рассматриваться как географические карты, нанесенные на плоскость или сферу.

Определение 30. Если планарный граф односвязен, то его плоский граф называется картой.

На рис.а) изображен не плоский граф. На рис. b) изображен тот же граф, только плоский.

На рис. с) изображен не планарный граф, на рис. d) – изоморфный ему плоский граф – карта. В отличие от географических карт плоский односвязный граф может иметь висячие вершины.

Рассмотрим карту некоторого графа.

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

На рис. а) (1,2,4,1) – не грань, так как она содержит внутри себя (1,2,3,1). Всего в графе четыре грани: (1,7.4,1), (1,4,2,3,1), (1,2,3,1), (2.6,5,4,2).

На рис.b) (1,2,3,4,1) – грань, так как ребро (4,5) не образует цикла.

Определение 32. Цикл, охватывающий все внутренние грани, называется внешней границей карты. Множество точек плоскости, лежащих вне этого цикла, называется границей внешней грани.

Замечание. Любому выпуклому трехмерному многограннику можно поставить в соответствие некоторую карту, ребра и грани которой, включая внешнюю, соответствуют ребрам и граням многогранника.

Теорема 6.Для любой карты число вершин (В), число ребер (Р) и число граней карты (Г), включая внешнюю, связаны равенством: В + Г – Р = 2

Теорема 7.Полный двудольный граф U_3,3 и полный граф U₅ непланарны.

Теорема 8.Для того, чтобы граф G был планарным, необходимо и достаточно, чтобы он не содержал подграф, который можно было бы сузить до U_3,3 или U₅ .

Пример (задача о трех домах и трех колодцах)

В одной деревне недалеко от трех домов расположены три колодца. В разное время года доступным оказывается то один, то другой колодец (в жару один из колодцев пересыхает, в мороз какой-то из них замерзает и т. д.). Поэтому каждый дом должен быть соединен тропинкой с каждым колодцем, причем, тропинки пересекаются между собой. С этим хозяева домов легко мирились, пока жили в дружбе. Но вот они поссорились, и каждый захотел иметь свои собственные тропинки к колодцам, не пересекающиеся с тропинками соседей. Можно ли проложить такие тропинки?