Medián počtu

Mediánový graf je graf reprezentující hrany sousednosti uvnitř ploch daného rovinného grafu .

Formální definice

Vzhledem k připojenému rovinnému grafu obsahuje jeho střední graf : $G$ $M(G)$

vrchol pro každou hranu , $G$
hrana mezi dvěma vrcholy pro každou plochu , pokud jsou hrany grafu na ní v řadě. $G$ $G$

Mediánový graf nespojeného grafu je nesouvislý svazek mediánových grafů spojených komponent.

Vlastnosti

Protože mediánový graf závisí na metodě vkládání, není mediánový graf jedinečný v tom smyslu, že stejný rovinný graf může mít několik neizomorfních mediánových grafů. Naopak neizomorfní grafy mohou mít stejný střední graf. Zejména rovinný graf a jeho duální graf mají jeden střední graf.

Mediánové grafy jsou 4 pravidelné grafy . Navíc každý 4-pravidelný rovinný graf je středním grafem nějakého rovinného grafu. Pro souvislý 4-pravidelný rovinný graf lze rovinný graf , pro který je prostředním grafem, sestrojit následovně: plochy jsou obarveny dvěma barvami (což je možné, protože se jedná o Euler, a protože duál grafu je bipartitní ); vrcholy v odpovídají plochám stejné barvy v . Tyto vrcholy jsou spojeny hranou pro každý společný (pro dvě plochy) vrchol v . Všimněte si, že provedením této konstrukce s plochami jiné barvy získáme duální graf. $H$ $G$ $H$ $G$ $H$ $H$ $G$ $H$ $H$ $G$

Pokud mají dva grafy stejný střední graf, jsou duální [1] .

Orientovaný mediánový graf

Do prostředního grafu lze zavést orientaci : k tomu je prostřední graf obarven dvěma barvami v závislosti na tom, zda strana prostředního grafu obsahuje vrcholy původního grafu či nikoli, a orientace je zavedena tak. že plochy kterékoli z barev jsou nalevo od okrajů .

Rovinný graf a jeho duál mají různé orientované mediánové grafy, které jsou vzájemně inverzní .

Tattův polynom

Pro rovinný graf je dvojnásobná hodnota Tatta polynomu v bodě (3,3) rovna součtu přes vážené Eulerovy orientace v prostředním grafu , kde váha orientace je ( je počet sedlové vrcholy orientace, tj. počet vrcholů, jejichž dopadající oblouky jsou seřazeny podle cyklu "příchozí - odchozí - příchozí - odchozí") [2] . Protože Tuttův polynom je invariant vkládání, výsledek ukazuje, že pro daný graf má jakýkoli mediánový graf stejný vážený součet Eulerových orientací. $G$ $G$ ${\displaystyle 2^{s))$ $s$

Pomocí orientovaného mediánového grafu lze efektivně zobecnit výsledek výpočtu Tatta polynomu v bodě (3,3). Pro rovinný graf se vynásobený hodnotou Tuttova polynomu v bodě rovná váženému součtu všech zabarvení oblouků na barvy v orientovaném mediánovém grafu grafu , takže každá (možná prázdná) sada oblouků stejná barva tvoří orientovaný Eulerův graf, kde váha Eulerovy orientace je ( je počet monochromatických vrcholů, tj. vrcholů, ke kterým mají všechny čtyři hrany stejnou barvu) [3] [4] . $G$ $n$ $(n+1, n+1)$ $n$ $G$ ${\displaystyle 2^{s))$ $s$

Poznámky

↑ Příručka teorie grafů / Jonathan L. Gross, Jay Yellen. - CRC Press, 2003. - S. 724. - ISBN 978-1584880905 .
↑ Michel Las Vergnas. O hodnocení na (3, 3) Tutteho polynomu grafu // Journal of Combinatorial Theory, Series B. - 1988. - Vol. 35 , no. 3 . — S. 367–372 . — ISSN 0095-8956 . - doi : 10.1016/0095-8956(88)90079-2 .
↑ Joanna A. Ellis-Monaghan. Identity pro polynomy rozdělení obvodů s aplikacemi na Tutteho polynom // Pokroky v aplikované matematice. - 2004. - T. 32 , no. 1-2 . - S. 188-197 . — ISSN 0196-8858 . - doi : 10.1016/S0196-8858(03)00079-4 .
↑ Michael Korn, Igor Pak. Kombinatorická hodnocení Tutteho polyno. — 2003, předtisk. — S. 4, Barvení hran mediálního grafu .

Literatura

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