Graf dualny

Mając graf planarny G można zdefiniować dla niego pojęcie grafu dualnego G*. Termin dualny (ang. dual) jest użyty ponieważ dualność jest symetryczna, jeśli graf X jest dualnym grafem grafu Y, to graf Y jest dualnym grafem grafu X; w efekcie grafy takie są podawane jako pary.

G* i G** są grafami dualnymi G, ale nie są izomorficzne.

Konstrukcja geometryczna

Mając graf planarny G tworzenie dla niego grafu dualnego G* można opisać następującymi krokami:

• Dla każdej ściany/obszaru spójnego (włącznie z obszarem zewnętrznym/okalającym - ścianą zewnętrzną) grafu G stworzyć wierzchołek.
• Jeśli dwie ściany mają wspólną krawędź x, połączyć wierzchołki utworzone w poprzednim kroku odpowiednie dla sąsiadujących ścianek krawędzią przecinającą tylko krawędź x.

Graf zbudowany z takich wierzchołków i krawędzi jest zawsze pseudografem planarnym.

Właściwości

• Graf dualny grafu planarnego jest zawsze grafem planarnym.
• Jeśli G* jest grafem dualnym grafu G, wtedy G jest grafem dualnym grafu G*, gdyż dualizacja grafu przyporządkowuje regionom wierzchołki, wierzchołkom regiony, a krawędziom krawędzie.
• Grafy dualne nie są określone jednoznacznie — ten sam graf może mieć nieizomorficzne grafy dualne. Jest to spowodowane tym, iż postać grafu dualnego zależy od postaci grafu źródłowego na płaszczyźnie (graf źródłowy może mieć topologicznie nierównoważne postaci, por. topologia). Na rysunku G* i G** nie są izomorficzne, gdyż G** zawiera wierzchołek stopnia 5, a G* takiego wierzchołka nie posiada.

Bibliografia

• Eric W.E.W. Weisstein Eric W.E.W., Dual Graph, [w:] MathWorld, Wolfram Research [dostęp 2020-12-14] (ang.).