Mac Lanes planaritetskriterium

I grafteorin är Mac Lanes planaritetskriterium en karakterisering av plana grafer i termer av deras cykelrum , uppkallad efter Saunders Mac Lane, som publicerade den 1937. Den anger att en finit oriktad graf är plan om och endast om cykelrymden av grafen (tagen modulo 2) har en cykelbas där varje kant av grafen deltar i högst två basvektorer.

Påstående

För varje cykel c i en graf G kan man bilda en m -dimensionell 0-1 vektor som har en 1 i koordinatpositionerna som motsvarar kanter i c och en 0 i de återstående koordinatpositionerna. Cykelutrymmet C ( G ) i grafen är det vektorutrymme som bildas av alla möjliga linjära kombinationer av vektorer som bildas på detta sätt. I Mac Lanes karaktärisering C ( G ) ett vektorrum över det finita fältet GF(2) med två element; det vill säga i detta vektorutrymme adderas vektorer koordinatvis modulo två. En 2-bas av G är en bas för C ( G ) med egenskapen att för varje kant e i G , som mest två basvektorer har koordinater som inte är noll i positionen som motsvarar e . Sedan, mer formellt uttryckt, är Mac Lanes karakterisering att de plana graferna är exakt de grafer som har en 2-bas.

Förekomsten av en 2-bas för plana grafer

En riktning av karakteriseringen säger att varje plan graf har en 2-bas. En sådan grund kan hittas som samlingen av gränser för de avgränsade ytorna av en plan inbäddning av den givna grafen G .

Om en kant är en brygga av G visas den två gånger på en enda ytagräns och har därför en nollkoordinat i motsvarande vektor. Således är de enda kanter som har koordinater som inte är noll de som skiljer två olika ytor åt; dessa kanter visas antingen en gång (om en av ytorna är den obundna) eller två gånger i samlingen av gränser för avgränsade ytor. Det återstår att bevisa att dessa cykler utgör en grund. Ett sätt att bevisa detta genom induktion. Som basfall G ett träd, då har det inga avgränsade ytor och C ( G ) är nolldimensionell och har en tom bas. Om man annars tar bort en kant från den obegränsade ytan av G minskar både dimensionen av cykelutrymmet och antalet avgränsade ytor med en och induktionen följer.

Alternativt är det möjligt att använda Eulers formel för att visa att antalet cykler i denna samling är lika med kretsrankningen G , som är dimensionen av cykelutrymmet. Varje icke-tom delmängd av cykler har en vektorsumma som representerar gränsen för föreningen av de avgränsade ytorna i delmängden, som inte kan vara tom (föreningen inkluderar minst en avgränsad yta och exkluderar den obegränsade ytan, så det måste finnas några kanter som separerar dem). Därför finns det ingen delmängd av cykler vars vektorer summerar till noll, vilket betyder att alla cykler är linjärt oberoende . Som en linjärt oberoende uppsättning av samma storlek som rummets dimension måste denna samling av cykler utgöra en bas.

Nödvändighet av planaritet när en 2-bas existerar

O'Neil (1973) gav följande enkla argument för den andra riktningen av karaktäriseringen, baserat på Wagners teorem som karakteriserar de plana graferna med förbjudna mindretal . Som O'Neill observerar, bevaras egenskapen att ha en 2-bas under grafiska minorer : om man drar ihop en kant, kan samma kontraktion utföras i basvektorerna, om man tar bort en kant som har en koordinat som inte är noll i en enda basvektor, då kan den vektorn tas bort från basen, och om man tar bort en kant som har en koordinat som inte är noll i två basvektorer, kan dessa två vektorer ersättas med deras summa (modulo två). Dessutom, om C ( G ) är en cykelbas för någon graf, måste den täcka vissa kanter exakt en gång, för annars skulle summan vara noll (omöjligt för en bas), och så kan C ( G ) utökas med en till cykel som består av dessa enkeltäckta kanter samtidigt som egenskapen att varje kant täcks högst två gånger. Emellertid har den fullständiga grafen K ₅ ingen 2-bas: C ( G ) är sexdimensionell, varje icke-trivial vektor i C ( G ) har icke-nollkoordinater för åtminstone tre kanter, och därför skulle varje förstärkt bas ha åtminstone 21 icke-nollor överskridande de 20 icke-nollställen som skulle vara tillåtna om var och en av de tio kanterna var icke-noll i högst två basvektorer. Med liknande resonemang har den kompletta tvådelade grafen K _3,3 ingen 2-bas: C ( G ) är fyrdimensionell, och varje icke-trivial vektor i C ( G ) har icke-nollkoordinater för minst fyra kanter, så varje förstärkt bas skulle ha minst 20 icke-nollor, vilket överskrider de 18 icke-nollställen som skulle vara tillåtna om var och en av de nio kanterna var icke-noll i högst två basvektorer. Eftersom egenskapen att ha en 2-bas är minor-sluten och inte stämmer för de två minor-minimala icke-planära graferna K ₅ och K _3,3 , är det inte heller sant för någon annan icke-planär graf.

Lefschetz (1965) gav ytterligare ett bevis, baserat på algebraisk topologi . Han använder en något annorlunda formulering av planaritetskriteriet, enligt vilket en graf är plan om och endast om den har en uppsättning (inte nödvändigtvis enkla) cykler som täcker varje kant exakt två gånger, så att den enda icke-triviala relationen mellan dessa cykler i C ( G ) är att deras summa är noll. Om så är fallet, ger att utelämna någon av cyklerna en grund som uppfyller Mac Lanes formulering av kriteriet. Om en plan graf är inbäddad i en sfär, uppfyller dess ansiktscykler tydligt Lefschetz egenskap. Omvänt, som Lefschetz visar, närhelst en graf G har en uppsättning cykler med denna egenskap, bildar de nödvändigtvis frontcyklerna för en inbäddning av grafen på sfären.

Ansökan

Ja'Ja' & Simon (1982) använde Mac Lanes planaritetskriterium som en del av en parallell algoritm för att testa grafplanaritet och hitta plana inbäddningar. Deras algoritm delar upp grafen i trekopplade komponenter , varefter det finns en unik plan inbäddning (upp till valet av den yttre ytan) och cyklerna i en 2-basis kan antas vara alla perifera cykler i grafen. Ja'Ja' och Simon börjar med en grundläggande cykelbas för grafen (en cykelbas genererad från ett spännträd genom att bilda en cykel för varje möjlig kombination av en bana i trädet och en kant utanför trädet) och omvandlar den till en 2-basis av perifera cykler. Dessa cykler bildar ytorna på en plan inbäddning av den givna grafen.

Mac Lanes planaritetskriterium gör att antalet avgränsade ytcykler i en plan graf lätt kan räknas som kretsrankningen för grafen. Denna egenskap används för att definiera meshness koefficient , en normaliserad variant av antalet avgränsade ytcykler som beräknas genom att dividera kretsrankningen med 2 n − 5 , det maximalt möjliga antalet avgränsade ytor i en plan graf med samma vertexuppsättning ( Buhl et al. 2004) .

•   Buhl, J.; Gautrais, J.; Sula, RV; Kuntz, P.; Valverde, S.; Deneubourg, JL; Theraulaz, G. (2004), "Efficiency and robustness in ant networks of galleries", The European Physical Journal B , Springer-Verlag, 42 (1): 123–129, Bibcode : 2004EPJB...42..123B , doi : 10.1140/epjb/e2004-00364-9 , S2CID 14975826 .
•   Ja'Ja', Joseph; Simon, Janos (1982), "Parallell algorithms in graph theory: planarity testing", SIAM Journal on Computing , 11 (2): 314–328, doi : 10.1137/0211024 , MR 0652905 .
•      Lefschetz, Solomon (1965), "Planar graphs and related topics", Proceedings of the National Academy of Sciences of the United States of America , 54 ( 6): 1763–1765, Bibcode : 1965PNAS...54.1763L , doi : 10.1073 /pnas.54.6.1763 , JSTOR 72818 , MR 0189011 , PMC 300546 , PMID 16591326 .
• Mac Lane, S. (1937), "A combinatorial condition for planar graphs" (PDF) , Fundamenta Mathematicae , 28 : 22–32, doi : 10.4064/fm-28-1-22-32 .
•    O'Neil, PV (1973), "A short proof of Mac Lane's planarity theorem", Proceedings of the American Mathematical Society , 37 ( 2): 617–618, doi : 10.1090/S0002-9939-1973-0313098-X hdl : 2060/19720020939 , JSTOR 2039496 , MR 0313098 .