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.

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

G* i G** są grafami dualnymi G, ale nie są izomorficzne.
  • 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. Weisstein, Dual Graph, [w:] MathWorld [online], Wolfram Research [dostęp 2020-12-14] (ang.).

Media użyte na tej stronie