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

Матеріал з testwiki
Версія від 12:52, 17 серпня 2024, створена imported>Lxlalexlxl
(різн.) ← Попередня версія | Поточна версія (різн.) | Новіша версія → (різн.)
Перейти до навігації Перейти до пошуку
Граф G' двоїстий до G
Non-iso dual graphs

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

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

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

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

Посилання

Шаблон:Math-stub