Kritérium rovinnosti Mac Lanes - Mac Lanes planarity criterion - Wikipedia

v teorie grafů, Kritérium rovinnosti Mac Lane je charakterizace rovinné grafy z hlediska jejich cyklostezky, pojmenoval podle Saunders Mac Lane, který ji publikoval v roce 1937. Uvádí se, že konečný neorientovaný graf je rovinný právě tehdy, má-li cyklický prostor grafu (vzatý modulo 2) a základ cyklu ve kterém se každá hrana grafu účastní nejvýše dvou základních vektorů.

Prohlášení

Pro jakýkoli cyklus $C$ v grafu $G$ , lze vytvořit $m$ -dimenzionální vektor 0-1, který má 1 v souřadnicových pozicích odpovídajících hranám v $C$ a 0 ve zbývajících souřadnicových pozicích. Prostor cyklu $C (G)$ grafu je vektorový prostor tvořený všemi možnými lineárními kombinacemi vektorů vytvořených tímto způsobem. V charakterizaci Mac Lane, $C (G)$ je vektorový prostor nad konečné pole $GF (2)$ se dvěma prvky; to znamená, že v tomto vektorovém prostoru jsou vektory přidány souřadnicově modulo dva. A 2-základ z $G$ je základem $C (G)$ s vlastností, že pro každou hranu $E$ v $G$ , nanejvýš dva základní vektory mají nenulové souřadnice v poloze odpovídající $E$ . Poté formálně řečeno, charakterizací Mac Lane je, že rovinné grafy jsou přesně grafy, které mají 2 základny.

Existence 2-základu pro rovinné grafy

Jeden směr charakterizace uvádí, že každý rovinný graf má 2 základny. Takový základ lze najít jako soubor hranic ohraničených ploch planárního vložení daného grafu $G$ .

Pokud je hrana mostem z $G$ , objeví se dvakrát na hranici jedné plochy, a proto má v odpovídajícím vektoru nulovou souřadnici. Jediné hrany, které mají nenulové souřadnice, jsou tedy ty, které oddělují dvě různé plochy; tyto hrany se objeví buď jednou (pokud je jednou z ploch neohraničená), nebo dvakrát ve sbírce hranic ohraničených ploch. Zbývá dokázat, že tyto cykly tvoří základ. Jeden způsob, jak to dokázat indukcí. Jako základní případ $G$ je strom, pak nemá ohraničené tváře a $C (G)$ je nulový rozměr a má prázdný základ. V opačném případě odstranění hrany z neomezeného obličeje $G$ zmenšuje jak rozměr prostoru cyklu, tak počet ohraničených ploch o jednu a následuje indukce.

Alternativně je možné použít Eulerův vzorec ukázat, že počet cyklů v této kolekci se rovná hodnost obvodu z $G$ , což je rozměr prostoru cyklu. Každá neprázdná podmnožina cyklů má vektorový součet, který představuje hranici sjednocení ohraničených ploch v podmnožině, která nemůže být prázdná (sjednocení zahrnuje alespoň jednu ohraničenou plochu a vylučuje neohraničenou plochu, takže musí existovat určité okraje oddělující jim). Proto neexistuje žádná podmnožina cyklů, jejichž vektory se sčítají k nule, což znamená, že všechny cykly jsou lineárně nezávislé. Jako lineárně nezávislá sada stejné velikosti jako rozměr prostoru musí tato kolekce cyklů tvořit základ.

Nutnost rovinnosti, pokud existuje 2 základna

O'Neil (1973) poskytl následující jednoduchý argument pro druhý směr charakterizace, založený na Wagnerova věta charakterizace rovinných grafů pomocí zakázané nezletilé. Jak O'Neill poznamenává, vlastnost mít 2-základnu je zachována pod nezletilí v grafu: pokud jeden zkrátí hranu, stejná kontrakce může být provedena v základních vektorech, pokud jeden odstraní hranu, která má nenulovou souřadnici v jednom základním vektoru, může být tento vektor odstraněn ze základny a pokud jeden odstraní hranu který má nenulovou souřadnici ve dvou bazických vektorech, pak tyto dva vektory mohou být nahrazeny jejich součtem (modulo dva). Navíc, pokud $C (G)$ je cyklický základ pro libovolný graf, pak musí překrýt některé hrany přesně jednou, protože jinak by jeho součet byl nulový (pro základ nemožné), a tak $C (G)$ lze rozšířit o jeden další cyklus skládající se z těchto jednotlivě zakrytých hran při zachování vlastnosti, že každá hrana je pokryta maximálně dvakrát. kompletní graf $K. 5$ nemá 2 základny: $C (G)$ je šestrozměrný, každý netriviální vektor $C (G)$ má nenulové souřadnice pro alespoň tři hrany, a tak by jakýkoli rozšířený základ měl alespoň 21 nenulových hodnot, což by překračovalo 20 nenulových hodnot, která by byla povolena, pokud by každá z deseti hran byla nenulová v maximálně dvou základních vektorech. Podobným uvažováním kompletní bipartitní graf $K. 3,3$ nemá 2 základny: $C (G)$ je čtyřrozměrný a každý netriviální vektor v $C (G)$ má nenulové souřadnice pro alespoň čtyři hrany, takže jakýkoli rozšířený základ by měl alespoň 20 nenulových, překračujících 18 nenulových, které by byly povoleny, pokud by každá z devíti hran byla nenulová v maximálně dvou základních vektorech. Vzhledem k tomu, že vlastnost mít 2-základnu je menší-uzavřená a neplatí pro dva menší-minimální neplanární grafy $K. 5$ a $K. 3,3$ , neplatí to ani pro žádný jiný neplanární graf.

Lefschetz (1965) poskytl další důkaz na základě algebraická topologie. Používá mírně odlišnou formulaci kritéria rovinnosti, podle něhož je graf rovinný právě tehdy, má-li soubor (ne nutně jednoduchých) cyklů pokrývajících každou hranu přesně dvakrát, takže jediný netriviální vztah mezi těmito cykly v $C (G)$ je, že jejich součet je nula. Pokud tomu tak je, pak ponechání kteréhokoli z cyklů mimo produkuje základ uspokojující formulaci kritéria Mac Lane. Pokud je planární graf vložen do koule, jeho cykly ploch jasně uspokojí Lefschetzovu vlastnost. Naopak, jak ukazuje Lefschetz, kdykoli graf G má sadu cyklů s touto vlastností, nutně tvoří cykly tváře vložení grafu do koule.

aplikace

Ja'Ja '& Simon (1982) použil kritérium lanárnosti Mac Lane jako součást a paralelní algoritmus pro testování rovinnosti grafů a hledání rovinných vložení. Jejich algoritmus rozděluje graf na tři propojené komponenty, po kterém dojde k jedinečnému plošnému vložení (až do výběru vnější plochy) a cykly ve 2-základně lze považovat za všechny periferní cykly grafu. Ja'Ja 'a Simon začínají základem základního cyklu grafu (základ cyklu generovaný z a kostra vytvořením cyklu pro každou možnou kombinaci cesty ve stromu a hrany mimo strom) a transformovat ji na 2-základnu periferních cyklů. Tyto cykly tvoří plochy rovinného vložení daného grafu.

Kritérium rovinnosti Mac Lane umožňuje snadné spočítání počtu cyklů ohraničených ploch v rovinném grafu, protože hodnost obvodu grafu. Tato vlastnost se používá při definování koeficient síťovosti grafu, normalizovaná varianta počtu cyklů ohraničené tváře, která se vypočítá vydělením pořadí obvodů $2 n - 5$ , maximální možný počet ohraničených ploch rovinného grafu se stejnou sadou vrcholů (Buhl a kol. 2004 ).

Reference

Buhl, J .; Gautrais, J .; Sole, R.V .; Kuntz, P .; Valverde, S .; Deneubourg, J.L .; Theraulaz, G. (2004), „Efektivita a robustnost v mravenčích sítích galerií“, Evropský fyzický deník B, Springer-Verlag, 42 (1): 123–129, doi:10.1140 / epjb / e2004-00364-9.
Ja'Ja ', Joseph; Simon, Janos (1982), „Paralelní algoritmy v teorii grafů: testování rovinnosti“, SIAM Journal on Computing, 11 (2): 314–328, doi:10.1137/0211024, PAN 0652905.
Lefschetz, Solomon (1965), "Rovinné grafy a související témata", Sborník Národní akademie věd Spojených států amerických, 54 (6): 1763–1765, doi:10.1073 / pnas.54.6.1763, JSTOR 72818, PAN 0189011, PMC 300546, PMID 16591326.
Mac Lane, S. (1937), „Kombinatorická podmínka pro planární grafy“ (PDF), Fundamenta Mathematicae, 28: 22–32.
O'Neil, P. V. (1973), „Krátký důkaz věty o rovinnosti Mac Lane“, Proceedings of the American Mathematical Society, 37 (2): 617–618, doi:10.1090 / S0002-9939-1973-0313098-X, hdl:2060/19720020939, JSTOR 2039496, PAN 0313098.