Medianräkning

En mediangraf är en graf som representerar närliggande kanter innanför ytorna på en given plan graf .

Formell definition

Givet en sammankopplad plan graf innehåller dess mittdiagram : $G$ $M(G)$

vertex för varje kant , $G$
en kant mellan två hörn för varje yta om kanterna på grafen är i en rad på den. $G$ $G$

Mediangrafen för en frånkopplad graf är en frånkopplad förening av mediangraferna för anslutna komponenter.

Egenskaper

Eftersom mediangrafen beror på inbäddningsmetoden är mediangrafen inte unik i den meningen att samma plana graf kan ha flera icke- isomorfa mediangrafer. Omvänt kan icke-isomorfa grafer ha samma mittdiagram. I synnerhet har en plan graf och dess dubbla graf en mittengraf.

Mediangrafer är 4- vanliga grafer . Dessutom är vilken 4-regelbunden plan graf som helst en mittgraf av någon plan graf. För en sammankopplad 4-regelbunden plan graf kan den plana grafen för vilken är en mittgraf konstrueras enligt följande: ytorna är färgade i två färger (vilket är möjligt eftersom det är Euler, och eftersom grafens dual är tvådelad ); hörn i motsvarar ytor av samma färg i . Dessa hörn är förbundna med en kant för varje gemensam (för två ytor) vertex i . Observera att om vi gör denna konstruktion med ytor av en annan färg får vi en dubbel graf. $H$ $G$ $H$ $G$ $H$ $H$ $G$ $H$ $H$ $G$

Om två grafer har samma mittdiagram är de dubbla [1] .

Riktad mediangraf

En orientering kan införas i den mellersta grafen : för detta färgas den mittersta grafen i två färger, beroende på om ytan på den mellersta grafen innehåller hörn på den ursprungliga grafen eller inte, och orienteringen introduceras på ett sådant sätt att ytorna på någon av färgerna är till vänster om kanterna.

Den plana grafen och dess dubbla har olika riktade mediangrafer som är omvända mot varandra.

Tatta-polynomet

För en plan graf är det dubbla värdet av Tatta-polynomet vid punkten (3,3) lika med summan över de viktade Euler-orienteringarna i mittengrafen , där vikten av orienteringen är ( är antalet av sadelpunkten för orienteringen, det vill säga antalet hörn vars infallande bågar är ordnade efter cykeln "inkommande - utgående - inkommande - utgående") [2] . Eftersom Tuttas polynom är en inbäddningsinvariant, visar resultatet att för en given graf har vilken mediangraf som helst samma viktade summa av Euler-orienteringarna. $G$ $G$ ${\displaystyle 2^{s))$ $s$

Med hjälp av en riktad mediangraf kan man effektivt generalisera resultatet av beräkningen av Tatta-polynomet vid punkten (3,3). För en plan graf , multiplicerad med värdet av Tutts polynom vid punkten är lika med den viktade summan av alla färgningar av bågarna till färger i den orienterade mediangrafen för grafen , så att varje (eventuellt tom) uppsättning av bågar av samma färg bildar en orienterad Euler-graf, där vikten av Euler-orienteringen är ( är antalet monokromatiska hörn, d.v.s. hörn, alla fyra kanter som faller in på vilka har samma färg) [3] [4] . $G$ $n$ $(n+1,n+1)$ $n$ $G$ ${\displaystyle 2^{s))$ $s$

Anteckningar

↑ Handbook of Graph Theory / Jonathan L. Gross, Jay Yellen. - CRC Press, 2003. - P. 724. - ISBN 978-1584880905 .
↑ Michel Las Vergnas. Om utvärderingen vid (3, 3) av Tutte-polynomet av en graf // Journal of Combinatorial Theory, Series B. - 1988. - Vol. 35 , nr. 3 . — S. 367–372 . — ISSN 0095-8956 . - doi : 10.1016/0095-8956(88)90079-2 .
↑ Joanna A. Ellis-Monaghan. Identiteter för kretspartitionspolynom, med tillämpningar till Tutte-polynomet // Advances in Applied Mathematics. - 2004. - T. 32 , nr. 1-2 . - S. 188-197 . — ISSN 0196-8858 . - doi : 10.1016/S0196-8858(03)00079-4 .
↑ Michael Korn, Igor Pak. Kombinatoriska utvärderingar av Tutte polyno. — 2003, förtryck. — S. 4, Färgläggning av den mediala grafens kanter .

Litteratur

Thomas Brylawski, James Oxley. Matriod Applications / Neil White. - Cambridge University Press, 1992. - S. 123-225.