Mediální graf - Medial graph
V matematický disciplína teorie grafů, mediální graf z rovinný graf G je další graf M (G) , který představuje sousedství mezi hranami v plochách G. Mediální grafy představil v roce 1922 Ernst Steinitz studovat kombinatorické vlastnosti konvexní mnohostěn,[1] Ačkoliv inverzní konstrukce byl již používán uživatelem Peter Tait v roce 1877 ve své základní studii o uzly a odkazy.[2][3]
Formální definice
Vzhledem k připojenému rovinný graf G, jeho mediální graf M (G) má
- vrchol pro každou hranu G a
- okraj mezi dvěma vrcholy pro každou stranu G ve kterém se jejich odpovídající hrany vyskytují postupně.
Mediální graf odpojeného grafu je disjunktní sjednocení mediálních grafů každé připojené komponenty. Definice mediálního grafu se také rozšiřuje beze změny na vkládání grafů na površích vyššího rodu.
Vlastnosti
- Mediální graf libovolného rovinného grafu je 4pravidelný rovinný graf.
- Pro jakýkoli rovinný graf G, mediální graf G a mediální graf duální graf z G jsou izomorfní. Naopak pro libovolný 4-pravidelný rovinný graf H, jediné dva rovinné grafy se středním grafem H jsou navzájem dvojí.[4]
- Protože mediální graf závisí na konkrétním vložení, mediální graf rovinného grafu není jedinečný; stejný rovinný graf může mítizomorfní mediální grafy. Na obrázku nejsou červené grafy izomorfní, protože dva vrcholy se samostatnými smyčkami sdílejí hranu v jednom grafu, ale ne v druhém.
- Každý 4-pravidelný rovinný graf je mediálním grafem nějakého rovinného grafu. Pro připojený graf 4 pravidelných rovin H, rovinný graf G s H protože jeho mediální graf může být sestaven následovně. Barvy tváří H pouze se dvěma barvami, což je od té doby možné H je Eulerian (a tedy dvojí graf H je bipartitní). Vrcholy dovnitř G odpovídají plochám jedné barvy v H. Tyto vrcholy jsou spojeny hranou pro každý vrchol sdílený jejich odpovídajícími plochami v H. Všimněte si, že provedení této konstrukce pomocí ploch druhé barvy jako vrcholů vytvoří duální graf G.
- Mediální graf 3-pravidelného rovinného grafu se shoduje s jeho hranový graf. To však neplatí pro mediální grafy rovinných grafů, které mají vrcholy stupňů větší než tři.
Aplikace
Pro rovinný graf G, dvojnásobné hodnocení Tutteův polynom v bodě (3,3) se rovná váženému součtu Euleriánské orientace ve středním grafu G, kde váha orientace je 2 k počtu sedlových vrcholů orientace (tj. počet vrcholů s dopadajícími hranami cyklicky seřazených „dovnitř, ven, dovnitř“).[5] Vzhledem k tomu, že polynom Tutte je pod vložením neměnný, ukazuje tento výsledek, že každý mediální graf má stejný součet těchto vážených Eulerianových orientací.
Usměrněný mediální graf
Definici mediálního grafu lze rozšířit o orientaci. Nejprve jsou plochy mediálního grafu zbarveny černě, pokud obsahují vrchol původního grafu a jinak bílou. Toto zbarvení způsobí, že každý okraj mediálního grafu bude ohraničen jednou černou tváří a jednou bílou tváří. Pak je každá hrana orientována tak, aby byl černý obličej nalevo.
Rovinný graf a jeho duální nemají stejný směrovaný střední graf; jejich směrované mediální grafy jsou přemístit navzájem.
Pomocí směrovaného mediálního grafu lze efektivně zobecnit výsledek na vyhodnocení Tutteova polynomu v (3,3). Pro rovinný graf G, n krát hodnocení Tutteův polynom na místě (n+1,n+1) se rovná váženému součtu přes všechna barvení hran pomocí n barvy v orientovaném mediálním grafu G takže každá (možná prázdná) sada jednobarevných okrajů tvoří směrovaný Eulerianův graf, kde váha směrované Eulerianské orientace je 2 k počtu monochromatických vrcholů.[6]
Viz také
- Uzly a grafy
- Tait graf
- Oprava (geometrie) - Ekvivalentní operace na mnohostěnů
Reference
- ^ Steinitz, Ernst (1922), „Polyeder und Raumeinteilungen“, Encyclopädie der mathematischen Wissenschaften, Band 3 (Geometries), s. 1–139
- ^ Tait, Peter G. (1876–1877). "Na uzlech I". Sborník Královské společnosti z Edinburghu. 28: 145–190. doi:10.1017 / S0080456800090633.
Revidováno 11. května 1877.
- ^ Tait, Peter G. (1876–1877). „Na odkazech (abstrakt)“. Sborník Královské společnosti z Edinburghu. 9 (98): 321–332. doi:10.1017 / S0370164600032363.
- ^ Gross, Jonathan L .; Yellen, Jay, eds. (2003). Příručka teorie grafů. CRC Press. str. 724. ISBN 978-1584880905.
- ^ Las Vergnas, Michel (1988), „O vyhodnocení (3, 3) Tutteova polynomu grafu“, Journal of Combinatorial Theory, Series B, 35 (3): 367–372, doi:10.1016/0095-8956(88)90079-2, ISSN 0095-8956
- ^ Ellis-Monaghan, Joanna A. (2004). Msgstr "Identity pro polynomy dělení obvodů s aplikacemi na Tutteův polynom." Pokroky v aplikované matematice. 32 (1–2): 188–197. doi:10.1016 / S0196-8858 (03) 00079-4. ISSN 0196-8858.
Další čtení
- Brylawski, Thomas; Oxley, James (1992). "Tutteův polynom a jeho aplikace" (PDF). In White, Neil (ed.). Maticové aplikace. Cambridge University Press. str. 123–225.