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

Для многих целей безразлично, как именно изображен граф, т. е. изоморфные графы, доставляющие одну и ту же информацию, могут рассматриваться как один граф. Так будет, например, в том случае, с которого начато изложение, – когда граф играет роль своеобразного списка уже проведенных игр. Однако в других случаях существенно то обстоятельство, что граф может быть начерчен некоторым специальным образом. Сравним два изоморфных графа, изображенные на рис. 1 и 7. На первом из них ребра пересекаются в пяти точках, не являющихся вершинами графа, на втором все точки пересечения ребер графа служат его вершинами.

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

Плоский граф можно рассматривать как карту дорог, соединяющих между собой различные станции или деревни. Так, на карте, изображенной на рис. 13, мы видим 7 станций: А, В,..., G, причем некоторые из них соединены друг с другом дорогами: АG, ВС, FE и т. д., и обратно, каждую карту дорог можно рассматривать как плоский граф. План любого города тоже является плоским графом, где улицы служат ребрами, а площади и уличные перекрестки – вершинами.

Рис. 13. Граф, соответствующий карте дорог, соединяющих семь станций

Впрочем, современная техника изменила многие наши представления, и, чтобы не отстать от современных требований, необходимо признать, что и карта дорог в настоящее время уже не всегда представляетсяплоским графом. К сети дорог теперь часто добавляются линии, проходящие на разных уровнях (дорожные развязки), так что в месте пересечения двух дорог пассажир не может перейти с одной линии на другую (рис. 14).

Рис. 14. Фотография современной многоуровневой дорожной развязки, которую невозможно представить плоским графом

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

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

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