Halins rutnätssats
I grafteorin , en gren av matematiken, säger Halins rutnätsats att de oändliga graferna med tjocka ändar är exakt de grafer som innehåller underavdelningar av planets sexkantiga plattsättning . Den publicerades av Rudolf Halin ( 1965 ) och är en föregångare till Robertsons och Seymours arbete med att länka trädbredd till stora rutnät mindreåriga , vilket blev en viktig del av den algoritmiska teorin om bidimensionalitet .
Definitioner och uttalande
0 En stråle, i en oändlig graf, är en semi-oändlig bana : en sammankopplad oändlig subgraf där en vertex har grad ett och resten har grad två. Halin (1964) definierade två strålar r och r 1 som ekvivalenta om det finns en stråle r 2 som inkluderar oändligt många hörn från var och en av dem. Detta är en ekvivalensrelation och dess ekvivalensklasser (uppsättningar av ömsesidigt ekvivalenta strålar) kallas ändarna på grafen. Halin (1965) definierade en tjock ände av en graf som en ände som innehåller oändligt många strålar som är parvis osammanhängande från varandra.
0 Ett exempel på en graf med en tjock ände tillhandahålls av den hexagonala plattsättningen av det euklidiska planet . Dess hörn och kanter bildar en oändlig kubisk plan graf , som innehåller många strålar. Till exempel bildar några av dess strålar Hamiltonska banor som spiralerar ut från en central startpunkt och täcker alla hörn i grafen. En av dessa spiralformade strålar kan användas som strålen r 2 i definitionen av ekvivalens av strålar (oavsett vilka strålar r och r 1 ges), vilket visar att varannan strålning är ekvivalent och att denna graf har en enda ände. Det finns också oändliga uppsättningar av strålar som alla är åtskilda från varandra, till exempel de uppsättningar av strålar som bara använder två av de sex riktningarna som en väg kan följa inom plattsättningen. Eftersom den har oändligt många parvis disjunkta strålar, alla likvärdiga med varandra, har denna graf en tjock ände.
Halins teorem säger att detta exempel är universellt: varje graf med en tjock ände innehåller som en subgraf antingen denna graf i sig eller en graf som bildas av den genom att modifiera den på enkla sätt, genom att dela upp några av dess kanter i ändliga banor. Subgrafen för denna form kan väljas så att dess strålar hör till den givna tjocka änden. Omvänt, närhelst en oändlig graf innehåller en underavdelning av den hexagonala plattsättningen, måste den ha en tjock ände, nämligen den ände som innehåller alla strålar som är subgrafer av denna underavdelning.
Analoger för finita grafer
Som en del av deras arbete med grafer som leder till Robertson–Seymour-satsen och grafstruktursatsen , bevisade Neil Robertson och Paul Seymour att en familj F av ändliga grafer har obegränsad trädbredd om och endast om de mindre graferna i F inkluderar godtyckligt stora kvadratiska rutnätsgrafer , eller motsvarande subgrafer av den hexagonala plattan som bildas genom att skära den med godtyckligt stora skivor. Även om det exakta förhållandet mellan trädbredd och rutnäts mindre storlek förblir svåröverskådlig, blev detta resultat en hörnsten i teorin om bidimensionalitet , en karakterisering av vissa grafparametrar som har särskilt effektiva algoritmer som kan hanteras med fasta parametrar och approximationsscheman för polynom-tid .
För finita grafer är trädbredden alltid en mindre än den maximala ordningen för en tillflyktsort , där en tillflyktsort beskriver en viss typ av strategi för en rånare att undkomma polisen i ett jakt-undvikande spel som spelas på grafen, och ordningen för haven anger antalet poliser som behövs för att fånga en rånare med denna strategi. Således kan relationen mellan trädbredd och rutnätsminorer återställas: i en familj av ändliga grafer är ordningen på tillflyktsorterna obegränsad om och endast om storleken på rutnätsminorerna är obegränsad. För oändliga grafer är ekvivalensen mellan trädbredd och fristadsordning inte längre sant, utan tillflyktsorterna är i stället intimt förbundna med ändar: ändarna på en graf är i en-till-en-överensstämmelse med tillflyktsorterna i ordningen ℵ 0 . Det är inte alltid sant att en oändlig graf har en tillflyktsort av oändlig ordning om och bara om den har en rutnätsmoll av oändlig storlek, men Halins sats ger ett extra villkor (tjockleken på änden som motsvarar tillflyktsorten) under vilken den blir Sann.
Anteckningar
- Demaine, Erik D. ; Hajiaghayi, MohammadTaghi (2005), "Bidimensionality: new connections between FPT algorithms and PTASs", Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA) (PDF) , s. 590–601, MR 929 .
- Diestel, Reinhard (2004), "A short proof of Halin's grid theorem", Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg , 74 : 237–242, doi : 10.1007/BF02941538 , MR 2112834 .
- Diestel, Reinhard; Kühn, Daniela (2003), "Graph-theoretical versus topological ends of graphs", Journal of Combinatorial Theory , Series B, 87 (1): 197–206, doi : 10.1016/S0095-8956(02)00034-5 , MR 1967888 .
- Halin, Rudolf (1964), "Über unendliche Wege in Graphen", Mathematische Annalen , 157 : 125–137, doi : 10.1007/bf01362670 , hdl : 10338.dmlcz/102294 01 , 3 MR 4 01 .
- Halin, Rudolf (1965), "Über die Maximalzahl fremder unendlicher Wege in Graphen", Mathematische Nachrichten , 30 : 63–85, doi : 10.1002/mana.19650300106 , MR 0190031 .
- Seymour, Paul D .; Thomas, Robin (1993), "Graph searching and a min-max theorem for tree-width", Journal of Combinatorial Theory , Series B, 58 (1): 22–33, doi : 10.1006/jctb.1993.1027 .