Самодвойственные графы. 
Геометрическая теория графов

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

Прежде всего заметим, что если граф G (V, E, F) изоморфен своему двойственному графу G'(V', E', F'), то количество граней этого графа равно количеству его вершин / = v. С учетом этого равенства формула Эйлера примет вид: v — е + v = 2. Следовательно, ё — 2(v -1), т. е. количество ребер самодвойственного графа всегда четно. Используя равенства / = v и е- 2(v -1), можно выделить следующие возможные значения для v, е и/.

Очевидно, что граф, соответствующий первой строке таблицы, является самодвойственным. Он представляет собой изолированную точку (см. рис. 84).

Существует всего два типа плоских связных графов, параметры которых соответствуют второй строке таблицы (см. рис. 85), и оба они являются самодвойственными.

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

Четыре графа, приведенные на рис. 87, являются примерами самодвойственных графов с 4 вершинами.

Среди графов с числом вершин v > 4

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

Рис. 86.

Рис. 87.

Рис. 88 °