Medianantal

En mediangraf er en graf, der repræsenterer tilstødende kanter inden for flader af en given plan graf .

Formel definition

Givet en forbundet plan graf indeholder dens midterste graf : $G$ $M(G)$

toppunkt for hver kant , $G$
en kant mellem to spidser for hver flade , hvis kanterne af grafen er i en række på den. $G$ $G$

Mediangrafen for en frakoblet graf er en afbrudt forening af mediangraferne for tilsluttede komponenter.

Egenskaber

Da mediangrafen afhænger af indlejringsmetoden, er mediangrafen ikke unik i den forstand, at den samme plane graf kan have flere ikke -isomorfe mediangrafer. Omvendt kan ikke-isomorfe grafer have den samme midterste graf. Især en plan graf og dens dobbelte graf har én midterste graf.

Mediangrafer er 4 -regulære grafer . Desuden er enhver 4-regulær plan graf en midtergraf af en plan graf. For en forbundet 4-regulær plan graf , kan den plane graf, for hvilken er en midtergraf, konstrueres som følger: fladerne er farvet i to farver (hvilket er muligt, da det er Euler, og da grafens dual er todelt ); hjørner i svarer til flader af samme farve i . Disse toppunkter er forbundet med en kant for hver fælles (for to flader) toppunkt i . Bemærk, at ved at udføre denne konstruktion med flader af en anden farve, får vi en dobbelt graf. $H$ $G$ $H$ $G$ $H$ $H$ $G$ $H$ $H$ $G$

Hvis to grafer har den samme midterste graf, er de dobbelte [1] .

Direkte mediangraf

En orientering kan indføres i den midterste graf : til dette er den midterste graf farvet i to farver, afhængigt af om forsiden af den midterste graf indeholder hjørnerne på den originale graf eller ej, og orienteringen er indført på en sådan måde at overfladerne af enhver af farverne er til venstre for kanterne.

Den plane graf og dens dual har forskellige rettede mediangrafer, der er inverse i forhold til hinanden.

Tatta-polynomiet

For en plan graf er den dobbelte værdi af Tatta-polynomiet i punktet (3,3) lig med summen over de vægtede Euler-orienteringer i den midterste graf , hvor vægten af orienteringen er ( er antallet af sadelspidser af orienteringen, det vil sige antallet af knudepunkter, hvis indfaldende buer er ordnet efter cyklus "indgående - udgående - indgående - udgående") [2] . Da Tuttas polynomium er en indlejringsinvariant, viser resultatet, at for en given graf har enhver mediangraf den samme vægtede sum af Euler-orienteringer. $G$ $G$ ${\displaystyle 2^{s))$ $s$

Ved hjælp af en rettet mediangraf kan man effektivt generalisere resultatet af beregningen af Tatta-polynomiet i punktet (3,3). For en plan graf , ganget med værdien af Tutts polynomium i punktet er lig med den vægtede sum af alle farvelægninger af buerne til farver i grafens orienterede mediangraf , således at hvert (muligvis tomme) sæt buer af samme farve danner en orienteret Euler-graf, hvor vægten af Euler-orienteringen er ( er antallet af monokromatiske hjørner, dvs. knudepunkter, hvor alle fire kanter, der falder ind på, har samme farve) [3] [4] . $G$ $n$ $(n+1,n+1)$ $n$ $G$ ${\displaystyle 2^{s))$ $s$

Noter

↑ Handbook of Graph Theory / Jonathan L. Gross, Jay Yellen. - CRC Press, 2003. - S. 724. - ISBN 978-1584880905 .
↑ Michel Las Vergnas. Om evalueringen ved (3, 3) af Tutte-polynomiet af 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 for kredsløbsopdelingspolynomier med applikationer til Tutte-polynomiet // Advances in Applied Mathematics. - 2004. - T. 32 , no. 1-2 . - S. 188-197 . — ISSN 0196-8858 . - doi : 10.1016/S0196-8858(03)00079-4 .
↑ Michael Korn, Igor Pak. Kombinatoriske evalueringer af Tutte-polynoen. - 2003, fortryk. — S. 4, Farvelægningskanter af den mediale graf .

Litteratur

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