Medial graf
Inom den matematiska disciplinen grafteori är den mediala grafen för plan graf G en annan graf M(G) som representerar närheterna mellan kanterna i ytorna på G . Mediala grafer introducerades 1922 av Ernst Steinitz för att studera kombinatoriska egenskaper hos konvexa polyedrar , även om den omvända konstruktionen redan användes av Peter Tait 1877 i hans grundläggande studie av knutar och länkar .
Formell definition
Givet en sammankopplad plan graf G har dess mediala graf M(G).
- en vertex för varje kant av G och
- en kant mellan två hörn för varje yta av G där deras motsvarande kanter förekommer i följd.
Den mediala grafen för en frånkopplad graf är den disjunkta föreningen av de mediala graferna för varje ansluten komponent. Definitionen av medial graf sträcker sig också utan modifiering till grafinbäddningar på ytor av högre släkte.
Egenskaper
- Den mediala grafen för varje plan graf är en 4- regelbunden plan graf.
- För varje plan graf G är den mediala grafen för G och den mediala grafen för den dubbla grafen för G isomorfa. Omvänt, för varje 4-reguljär plan graf H , är de enda två plana graferna med mediala grafen H dubbla i förhållande till varandra.
- Eftersom den mediala grafen beror på en viss inbäddning är den mediala grafen för en plan graf inte unik; samma plana graf kan ha icke- isomorfa mediala grafer. På bilden är de röda graferna inte isomorfa eftersom de två hörnen med självslingor delar en kant i en graf men inte i den andra.
- Varje 4-regelbunden plan graf är den mediala grafen för någon plan graf. För en sammankopplad 4-reguljär plan graf H kan en plan graf G med H som sin mediala graf konstrueras enligt följande. Färglägg ytorna på H med bara två färger, vilket är möjligt eftersom H är Eulerian (och därmed den dubbla grafen för H är tvådelad). Topparna i G motsvarar ytorna av en enda färg i H . Dessa hörn är förbundna med en kant för varje vertex som delas av deras motsvarande ytor i H . Observera att om du utför denna konstruktion med hjälp av ytorna på den andra färgen som hörn, produceras den dubbla grafen för G .
- Den mediala grafen för en graf med tre reguljära plan sammanfaller med dess linjediagram . Detta är dock inte sant för mediala grafer av plana grafer som har hörn av grad som är större än tre.
Ansökningar
För en plan graf G , är två gånger utvärderingen av Tutte-polynomet vid punkten (3,3) lika med summan över viktade Euleriska orienteringar i den mediala grafen för G , där vikten av en orientering är 2 till antalet sadelhörn av orienteringen (det vill säga antalet hörn med infallande kanter cykliskt ordnade "in, ut, in ut"). Eftersom Tutte-polynomet är invariant under inbäddningar, visar detta resultat att varje mediall graf har samma summa av dessa viktade Euleriska orienteringar.
Riktad medial graf
Den mediala grafdefinitionen kan utökas till att omfatta en orientering. För det första färgas ytorna på den mediala grafen svarta om de innehåller en spets på den ursprungliga grafen och vitt annars. Denna färgning gör att varje kant av den mediala grafen kantas av ett svart ansikte och ett vitt ansikte. Sedan är varje kant orienterad så att det svarta ansiktet är till vänster.
En plan graf och dess dubbla har inte samma riktade mediala graf; deras riktade mediala grafer är transponeringen av varandra.
Med hjälp av den riktade mediala grafen kan man effektivt generalisera resultatet på utvärderingar av Tutte-polynomet vid (3,3). För en plan graf G , n gånger utvärderingen av Tutte-polynomet vid punkten ( n +1, n +1) är lika med den viktade summan över alla kantfärger med användning av n färger i den riktade mediala grafen för G så att varje (eventuellt tom) ) uppsättning monokromatiska kanter bildar en riktad Eulerisk graf, där vikten av en riktad Eulerisk orientering är 2 till antalet monokromatiska hörn.
Se även
- Knutar och grafer
- Tait graf
- Rectification (geometri) - Motsvarande operation på polyedrar
Vidare läsning
- Brylawski, Thomas ; Oxley, James (1992). "Tuttepolynomet och dess tillämpningar" (PDF) . I White, Neil (red.). Matriod-applikationer . Cambridge University Press. s. 123–225.