Двоїстий граф

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Граф G' двоїстий до G

Двоїстий граф G' до планарного графа G — це граф, у якому вершини відповідають граням графа G; ці вершини з'єднані ребром, тільки якщо відповідні їм грані графа G мають спільне ребро. Наприклад, двоїсті один до одного графи куба й октаедра.

Двоїстий граф є псевдографом: у ньому можуть бути петлі й кратні ребра.

Залежно від укладки, до одного графа можуть існувати декілька двоїстих.

Самодвоїстим називають граф, що ізоморфний своєму двоїстому графу. Наприклад, самодвоїстим є граф тетраедра.

Посилання[ред.ред. код]