Грани плоского графа

Рассмотрим конечный связный плоский граф, и пусть G (V, E) — одна из его геометрических реализаций на плоскости (т.е. G (V, E) — правильное изображение плоского графа). Гранью называется область плоскости, ограниченная ребрами графа G (V, E) и не содержащая внутри себя ни вершин, ни ребер⁷. Одна из граней плоского графа является внешней. Будем обозначать множество граней плоского графа через F, а для самого графа ;

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

использовать обозначение G (V, E, F). Так, например, плоский граф на рис. 77 имеет 7 граней, и грань fj является внешней. В этом примере грань// ограничена всего одним ребром, грани/б и/7 — двумя,/2 и/5 — тремя,// - четырьмя, а внешняя грань f₃ ограничена 12 ребрами.

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

Пусть сфера S касается плоскости Я в точке Q (см. рис. 78). Обозначим через Р точку сферы, диаметрально противоположную точке касания Q. Каждой точке А плоскости Я поставим в соответствие точку А'сферы S по следующему закону: точка А' является точкой пересечения прямой АР и сферы S. Описанное соответствие / является отображением плоскости Я на сферу S. При этом отображении любой точке сферы, кроме точки Р, соответствует единственная точка плоскости. Точка Р не имеет прообраза. Таким образом, отображение /: Я —> S/P плоскости Я на сферу S без точки Р является взаимно однозначным отображением и называется стереографической проекцией из полюса Р.

Предположим, что на плоскости Я реализован некоторый плоский граф G. Его образом при стереографической проекции /• Я —> S/Р будет являться геометрический граф G', лежащий на сфере S и изоморфный графу G. Заметим, что ребрами графа G' будут служить простые кривые на сфере, пересекающиеся только в вершинах. Для сферического графа G', по аналогии с плоским случаем, можно определить понятие грани. Сферический граф G' имеет столько же граней, сколько и плоский граф G, но, в отличие от последнего, все его грани равноправны^[1]. Легко видеть, что при стереографической проекции внешняя грань графа G перейдет в грань сферического графа G содержащую полюс Р. Очевидно также, что при помощи обратного отображения любой сферический граф перейдет в изоморфный ему плоский граф, а грань сферического графа, содержащая полюс, перейдет во внешнюю грань плоского графа.

Опишем процесс построения отображения изоморфизма, при котором внешняя грань плоского геометрического графа G перейдет во внутреннюю грань плоского графа G'. Для этого рассмотрим плоскость Я графа G, и пусть g — его внешняя грань.

• 1. Рассмотрим стереографическую проекцию f плоскости Я на сферу S из полюса Р. Обозначим через G/ сферический граф, являющийся образом графа G при отображении /_;. При этом отображении внешняя грань g графа G перейдет в грань сферического графа, содержащую полюс Р.
• 2. Повернем сферу S вокруг своего центра так, чтобы ее новый полюс Р' не попал внутрь грани gj. Обозначим этот поворот через /г. После поворота f сферический граф Gi перейдет в граф G/ (это, по существу, тот же самый граф, но по-другому расположенный на сфере), а грань gi перейдет в грань g/, которая не будет содержать нового полюса Р'.
• 3. Рассмотрим стереографическую проекцию _/) плоскости Я на сферу S из полюса Р и пусть f/¹ — отображение, обратное для /j.

При этом отображении сферический граф G/ перейдет в некоторый плоский граф, который мы обозначим через G'. Образом грани g/ будет являться внутренняя грань g' графа G' (это следует из того, что грань gi' не содержит полюса Р' стереографической проекции /j).

4. Теперь рассмотрим отображение /• Я —> Я, являющееся композицией отображений //, /г и fi¹ (см. диаграмму на рис. 79).

Рис. 79.

Образом плоского графа G при отображении / является плоский граф G', а само / является отображением изоморфизма этих графов. Так как при этом изоморфизме внешняя грань g графа G переходит во внутреннюю грань g' графа G', то/- искомое отображение.

Упражнение. Постройте отображение изоморфизма, при котором граф G с пятиугольной внешней гранью перейдет в граф G', у которого внешняя грань четырехугольная (см. рис. 80).

Рис. 80.

Замечание. Если плоский граф не является связным, то он может иметь более сложное строение граней^[2]. Так, например, внутренняя грань g в графе, представленном на рис. 81, имеет форму кольца.

• [1] Внутренность каждой грани связного сферического графагомеоморфна внутренности круга.
• [2] Для несвязного графа внутренность грани (даже внутренней) может быть не гомеоморфна внутренности круга.