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

Планарность графа

Определение

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

Определение

Граф называется планарным, если он изоморфен некоторому плоскому графу.

О планарных графах говорят, что они укладываются на плоскости.

Если мы говорим об ориентированном графе, то он будет планарным, если планарен соответствующий ему неориентированный граф.

Пример

Граф изоморфен графам

1 2 a b A

D

3 4 c d B C

Зачем нужна планарность?

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

Аналогичная задача возникает при проектировании железных дорог, где нежелательны переезды.

Откуда возникла задача планарности?

Решалась простая на первый взгляд задача: можно ли проложить дороги от домов к каждому колодцу, чтобы они не пересекались?

Позднее эта задача получила название задача о трех колодцах.

Определение

Грань – это область, ограниченная непрерывной самонепересекающейся кривой, Такая кривая называется кривой Жордана.

В графе всегда есть одна неограниченная грань и может быть сколько внутренних ограниченных граней.

Пример

4 1 – внешняя грань

1 2 – 2, 3, 4, 5 – внутренние области

2 3

Каждая грань ограничена, по крайней мере, тремя ребрами.