Двойственность плоских графов

Пусть на плоскости задан связный плоский граф G. Говорят, что грань h графа G инцидентна ребру а, если ребро а принадлежит границе грани h. Две грани графа называются смежными, если они инцидентны одному и тому же ребру.

Граф G' называется двойственным для плоского графа G, если выполняются два следующих условия:^[1]

• 1) Каждой грани h графа G соответствует единственная вершина Я’графа G'.
• 2) Если вершины Я/ и Я₂' в G' соответствуют граням h] и h₂ в G, то каждому ребру а графа G, инцидентному граням h/ и h₂, соответствует единственное ребро а’графа G', инцидентное вершинам Я/и Н₂.

Ясно, что двойственный граф G' существует для любого плоского графа G. Геометрически он может быть реализован следующим образом. В каждой грани графа G выберем по точке (см. примеры на рис. 58, 59 и 75, 76). Если ребро а в графе G инцидентно двум граням hi и h₂, то соответствующие точки Я/и Я/ в G’соединим ребром а пересекающим ребро о и не пересекающим другие ребра графа G.

Заметим, что если ребро а графа G не принадлежит никакому циклу (т.е. является перешейком), то в графе G' ему соответствует петля <�з'(см. рис. 82).

Из определения двойственного графа следует, что плоскому графу G двойственным будет граф G', который также является плоским. Более того, если построить двойственный граф для графа, двойственного графу G, то получится исходный граф G.

Пусть G (V, E, F) и G' (V'.E'F') — два взаимно двойственных плоских графа. Тогда имеют место следующие очевидные равенства:

Важно отметить, что два изоморфных плоских графа могут иметь неизоморфные двойственные графы. Так, на рис. 83 графы G; и G₂ изоморфны, но двойственные им графы G/и G₂'не изоморфны.

Рис. 83.

Действительно, граф G/ имеет две вершины степени 5 и две вершины степени 3, а граф G/ имеет две вершины степени 4, одну вершину степени 3 и одну вершину степени 5. Приведенный пример свидетельствует о том, что строение двойственного графа для заданного плоского абстрактного графа G существенно зависит от способа его геометрической реализации. Более того, можно пок’азать, что если граф G? получается из графа G; при помощи непрерывной деформации плоскости, то граф G/, двойственный G/, будет изоморфен графу G2',

двойственному G* Очевидно, что графы G/ и G2, приведенные на рис. 83, не переводятся один в другой при помощи непрерывной деформации плоскости, и поэтому им двойственные графы не изоморфны.

• [1] Многогранник называется простым, если его поверхностьгомеоморфна сфере (т.е. имеет нулевой род).