Koniec (teoria grafów) - End (graph theory)

W matematyce o nieskończonej wykresów An koniec wykresu reprezentuje intuicyjnie do kierunku, w którym rozciąga się na wykresie w nieskończoność. Koniec może być sformalizowane matematycznie jako klasy równoważności nieskończonych ścieżek , jako raje opisujące strategie pogoń-uchylanie się od gry na wykresie, lub (w przypadku lokalnie skończonych wykresów) jako topologicznych końcach o przestrzeniach topologicznych związanych z wykresu.

Końce wykresów mogą być użyte (poprzez wykresy Cayleya ) do zdefiniowania końców skończenie generowanych grup . Skończenie generowane nieskończone grupy mają jeden, dwa lub nieskończenie wiele końców, a twierdzenie Stallingsa o ​​końcach grup zapewnia rozkład grup z więcej niż jednym końcem.

Definicja i charakterystyka

Końce grafów zostały zdefiniowane przez Rudolfa Halina  ( 1964 ) w kategoriach klas równoważności ścieżek nieskończonych. ZA promień w nieskończonym wykresie jest półnieskończonąprostą ścieżką; oznacza to, że jest to nieskończona sekwencja wierzchołkówv₀,v₁,v₂, ... w której każdy wierzchołek pojawia się co najwyżej raz w sekwencji, a każde dwa kolejne wierzchołki w sekwencji są dwoma punktami końcowymi krawędzi w ciągu wykres. Zgodnie z definicją Halina dwa promienier₀ir₁są równoważne, jeśli istnieje inny promieńr₂(niekoniecznie różny od któregokolwiek z pierwszych dwóch promieni), który zawiera nieskończenie wiele wierzchołków w każdym zr₀ir₁. Jest torelacja równoważności: każdy promień jest sobie równy, definicja jest symetryczna w odniesieniu do kolejności dwóch promieni i można wykazać, że jestprzechodnia. Dlatego dzieli zbiór wszystkich promieni naklasy równoważności, a Halin zdefiniował koniec jako jedną z tych klas równoważności.

Zastosowano również alternatywną definicję tej samej relacji równoważności: dwa promienie r ₀ i r ₁ są równoważne, jeśli nie istnieje skończony zbiór X wierzchołków, który oddziela nieskończenie wiele wierzchołków r ₀ od nieskończenie wielu wierzchołków r ₁ . Jest to równoznaczne z definicją Halina: jeśli promień r ₂ z definicji Halina istnieje, to każdy separator musi zawierać nieskończenie wiele punktów r ₂ i dlatego nie może być skończony, i odwrotnie, jeśli r ₂ nie istnieje, to ścieżka, która zmienia się tyle razy sposób pomiędzy R ₀ i R ₁ mogą tworzyć żądanej skończoną separator.

Końce mają również bardziej konkretną charakterystykę pod względem schronień , funkcji opisujących strategie uników w grach pościg-unikanie na grafie G . W omawianej grze złodziej próbuje ominąć grupę policjantów, przechodząc od wierzchołka do wierzchołka wzdłuż krawędzi G . Policja ma helikoptery i dlatego nie musi podążać za krawędziami; jednak złodziej widzi nadchodzącą policję i może wybrać, gdzie się przenieść, zanim wylądują helikoptery. Przystań jest funkcją β, która odwzorowuje każdy zbiór X lokalizacji policyjnych na jeden z połączonych elementów podgrafu utworzonego przez usunięcie X ; złodziej może uniknąć policji, przesuwając się w każdej rundzie gry do wierzchołka w tym komponencie. Schronienia muszą spełniać właściwość spójności (odpowiadającą wymaganiu, że złodziej nie może poruszać się po wierzchołkach, na których policja już wylądowała): jeśli X jest podzbiorem Y , a zarówno X, jak i Y są prawidłowymi zestawami lokalizacji dla danego zestawu policji , to β( X ) musi być nadzbiorem β( Y ). Przystań ma porządek k, jeśli zbiór lokalizacji policyjnych, dla których zapewnia strategię ucieczki, obejmuje wszystkie podzbiory mniej niż k wierzchołków na wykresie; w szczególności ma rząd ℵ _0, jeśli odwzorowuje każdy skończony podzbiór X wierzchołków na składnik G  \  X . Każdy promień w G odpowiada przystani rzędu ℵ ₀ , mianowicie funkcji β, która odwzorowuje każdy skończony zbiór X na unikalną składową G  \  X, która zawiera nieskończenie wiele wierzchołków promienia. I odwrotnie, każde przystań rzędu ℵ ₀ może być w ten sposób zdefiniowana przez promień. Dwa promienie są równoważne wtedy i tylko wtedy, gdy definiują tę samą przystań, więc końce grafu odpowiadają jeden do jednego z jego przystaniami rzędu of ₀ .

Przykłady

Część nieskończonego wykresu siatki , z wierzchołkami w punktach, w których spotykają się dwie linie siatki. Pomimo wielu różnych promieni ma tylko jeden koniec.

Jeśli nieskończony graf G sam jest promieniem, to ma nieskończenie wiele podgrafów promienia, po jednym rozpoczynającym się od każdego wierzchołka G . Jednak wszystkie te promienie są sobie równoważne, więc G ma tylko jeden koniec.

Jeśli G jest lasem (to znaczy grafem bez cykli skończonych), to przecięcie dowolnych dwóch promieni jest albo ścieżką, albo promieniem; dwa promienie są równoważne, jeśli ich przecięcie jest promieniem. Jeśli wierzchołek podstawy jest wybrany w każdym połączonym elemencie G , to każdy koniec G zawiera unikalny promień wychodzący z jednego z wierzchołków podstawy, więc końce mogą być umieszczone w korespondencji jeden do jednego z tymi promieniami kanonicznymi. Każdy policzalny graf G ma las opinający z takim samym zestawem końców jak G . Istnieją jednak niezliczone nieskończone grafy z tylko jednym końcem, w którym każde drzewo opinające ma nieskończenie wiele końców.

Jeśli G jest nieskończonym wykresem siatkowym , to ma wiele promieni i dowolnie duże zestawy promieni rozłącznych wierzchołków. Ma jednak tylko jeden koniec. Najłatwiej można to zaobserwować, używając charakterystyki końców w kategoriach przystani: usunięcie dowolnego skończonego zbioru wierzchołków pozostawia dokładnie jedną nieskończenie spójną składową, więc istnieje tylko jedna przystań (ta, która odwzorowuje każdy skończony zbiór na unikalny nieskończenie spójny składnik).

Stosunek do topologicznych końców

W topologii zbioru punktów istnieje pojęcie końca podobne do koncepcji końca w teorii grafów, ale nie do końca takie samo, pochodzące znacznie wcześniej od Freudenthala (1931) . Jeżeli przestrzeń topologiczną można pokryć zagnieżdżonym ciągiem zbiorów zwartych , to koniec przestrzeni jest ciągiem składowych dopełnień zbiorów zwartych. Ta definicja nie zależy od wyboru zwartych zbiorów: końce określone przez jeden taki wybór mogą być umieszczone w korespondencji jeden do jednego z końcami zdefiniowanymi przez dowolny inny wybór. ${\displaystyle \kappa _{0}\subset \kappa _{1}\subset \kappa _{2}\dots }$${\displaystyle U_{0}\supset U_{1}\supset U_{2}\dots }$

Nieskończony graf G można przekształcić w przestrzeń topologiczną na dwa różne, ale powiązane ze sobą sposoby:

• Zastąpienie każdego wierzchołka grafu punktem i każdą krawędzią grafu interwałem otwartej jednostki daje przestrzeń Hausdorffa z grafu, w której zbiór S jest zdefiniowany jako otwarty, ilekroć każde przecięcie S z krawędzią grafu jest otwarty podzbiór przedziału jednostkowego.
• Zastąpienie każdego wierzchołka grafu punktem i każdej krawędzi grafu punktem tworzy przestrzeń nie-Hausdorffa, w której zbiory otwarte są zbiorami S o własności, że jeśli wierzchołek v z G należy do S , to tak czy każda krawędź mająca v jako jeden z jej punktów końcowych.

W obu przypadkach każdy skończony podgraf G odpowiada zwartej podprzestrzeni przestrzeni topologicznej, a każda zwarta podprzestrzeń odpowiada skończonemu podgrafowi wraz z, w przypadku Hausdorffa, skończenie wieloma zwartymi właściwymi podzbiorami krawędzi. Zatem graf może być pokryty zagnieżdżoną sekwencją zbiorów zwartych wtedy i tylko wtedy, gdy jest lokalnie skończony, mając skończoną liczbę krawędzi na każdym wierzchołku.

Jeśli graf G jest spójny i lokalnie skończony, to ma zwarte pokrycie, w którym zbiór κ _i jest zbiorem wierzchołków w odległości co najwyżej i od jakiegoś arbitralnie wybranego wierzchołka początkowego. W tym przypadku dowolna przystań β określa koniec przestrzeni topologicznej, w którym . I odwrotnie, jeśli jest końcem przestrzeni topologicznej określonej z G , definiuje przystań, w której β( X ) jest składnikiem zawierającym U _i , gdzie i jest dowolną liczbą na tyle dużą, że κ _i zawiera X . Tak więc, w przypadku grafów połączonych i lokalnie skończonych, końce topologiczne są w relacji jeden do jednego z końcami grafoteoretycznymi. ${\displaystyle U_{i}=\beta (\kappa _{i})}$${\displaystyle U_{0}\supset U_{1}\supset U_{2}\dots }$

W przypadku grafów, które mogą nie być lokalnie skończone, nadal możliwe jest zdefiniowanie przestrzeni topologicznej na podstawie grafu i jego końców. Przestrzeń ta może być reprezentowana jako przestrzeń metryczna wtedy i tylko wtedy, gdy graf ma normalne drzewo opinające , zakorzenione drzewo opinające , w którym każda krawędź grafu łączy parę przodek-potomek. Jeśli istnieje normalne drzewo opinające, ma ono taki sam zestaw końców jak dany graf: każdy koniec grafu musi zawierać dokładnie jedną nieskończoną ścieżkę w drzewie.

Specjalne rodzaje końcówek

Darmowe końce

Koniec E grafu G jest zdefiniowany jako wolny koniec, jeśli istnieje skończony zbiór X wierzchołków o własności, że X oddziela E od wszystkich innych końców grafu. (Oznacza to, że pod względem schronień β _E ( X ) jest rozłączne od β _D ( X ) dla każdego drugiego końca D .) W grafie o skończenie wielu końcach każdy koniec musi być wolny. Halin (1964) udowadnia, że ​​jeśli G ma nieskończenie wiele końców, to albo istnieje koniec, który nie jest wolny, albo istnieje nieskończona rodzina promieni, które mają wspólny wierzchołek początkowy i są od siebie rozłączne.

Grube końce

Gruby koniec grafu G jest koniec, który zawiera nieskończenie wiele pairwise- rozłączne promieni. Siatka jest twierdzenie Halin charakteryzuje wykresy, które zawierają grube końce: są dokładnie te wykresy, które mają podział na heksagonalnej kafli jako podgrafu.

Specjalne rodzaje wykresów

Wykresy symetryczne i prawie symetryczne

Mohar (1991) definiuje połączony lokalnie skończony graf jako „prawie symetryczny”, jeśli istnieje wierzchołek v i liczba D takie, że dla każdego innego wierzchołka w występuje automorfizm grafu, dla którego obraz v mieści się w odległość D z w ; równoważnie, połączony lokalnie skończony graf jest prawie symetryczny, jeśli jego grupa automorfizmu ma skończenie wiele orbit. Jak pokazuje, dla każdego połączonego lokalnie skończonego prawie symetrycznego grafu liczba końców jest albo co najwyżej dwa, albo niepoliczalna; jeśli jest niepoliczalny, końce mają topologię zbioru Cantora . Dodatkowo Mohar pokazuje, że liczba końców kontroluje stałą Cheeger

${\displaystyle h=\inf \left\{{\frac {|\partial V|}{|V|}}\right\},}$

gdzie V obejmuje wszystkie skończone niepuste zbiory wierzchołków grafu i gdzie oznacza zbiór krawędzi z jednym punktem końcowym w V . Dla prawie symetrycznych grafów z niezliczoną liczbą końców, h  > 0; jednak dla prawie symetrycznych grafów z tylko dwoma końcami h  = 0. ${\displaystyle \partial V}$

Wykresy Cayleya

Wykres Cayleya wolnej grupy na dwóch generatorach a i b . Końce grupy odpowiadają jeden do jednego z promieniami (nieskończonymi ścieżkami) od elementu tożsamości e do obrzeży rysunku.

Każda grupa i zbiór generatorów dla grupy określa graf Cayleya , graf , którego wierzchołki są elementami grupy, a krawędziami są parami elementów ( x , gx ), gdzie g jest jednym z generatorów. W przypadku skończenie generowanej grupy końce grupy definiuje się jako końce grafu Cayleya dla skończonego zbioru generatorów; definicja ta jest niezmienna w przypadku wyboru generatorów, w tym sensie, że jeśli wybrano dwa różne skończone zbiory generatorów, końce dwóch grafów Cayleya są ze sobą w korespondencji jeden-do-jednego.

Na przykład każda wolna grupa ma wykres Cayleya (dla swoich wolnych generatorów), który jest drzewem. Wolna grupa w jednym generatorze ma ścieżkę podwójnie nieskończoną jako swój wykres Cayleya, z dwoma końcami. Każda inna wolna grupa ma nieskończenie wiele końców.

Każda skończenie generowana nieskończona grupa ma albo 1, 2, albo nieskończenie wiele końców, a twierdzenie Stallingsa o ​​końcach grup zapewnia rozkład grup z więcej niż jednym końcem. W szczególności:

1. Skończenie generowana nieskończona grupa ma 2 końce wtedy i tylko wtedy, gdy ma cykliczną podgrupę o skończonym indeksie .
2. Skończenie generowana nieskończona grupa ma nieskończenie wiele zakończeń wtedy i tylko wtedy, gdy jest albo nietrywialnym, wolnym produktem z amalgamacją, albo rozszerzeniem HNN ze skończoną amalgamacją.
3. Wszystkie inne skończenie generowane nieskończone grupy mają dokładnie jeden koniec.

Uwagi

Bibliografia

• Diestel, Reinhard (1992), „Struktura końcowa grafu: ostatnie wyniki i otwarte problemy”, Matematyka dyskretna , 100 (1–3): 313–327, doi : 10.1016/0012-365X(92)90650-5 , MR  1172358.
• Diestel, Reinhard (2004), „Krótki dowód twierdzenia siatki Halina”, Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg , 74 : 237-242, doi : 10.1007/BF02941538 , MR  2112834.
• Diestel, Reinhard (2006), "Przestrzenie końcowe i drzewa opinające ", Journal of Combinatorial Theory , Seria B, 96 (6): 846-854, doi : 10.1016/j.jctb.2006.02.010 , MR  2274079.
• Diestel, Reinhard; Kühn, Daniela (2003), "Wykres teoretyczny kontra topologiczne końce grafów", Journal of Combinatorial Theory , Seria B, 87 (1): 197-206, doi : 10.1016/S0095-8956(02)00034-5 , MR  1967888.
• Freudenthal, Hans (1931), „Über die Enden topologischer Räume und Gruppen”, Mathematische Zeitschrift , 33 : 692-713, doi : 10.1007/BF01174375.
• Freudenthal, Hans (1945), „Über die Enden diskreter Räume und Gruppen”, Commentarii Mathematici Helvetici , 17 : 1-38, doi : 10.1007/bf02566233 , MR  0012214.
• Halin, Rudolf (1964), "Über unendliche Wege in Graphen", Mathematische Annalen , 157 (2): 125-137, doi : 10.1007/bf01362670 , hdl : 10338.dmlcz/102294 , MR  0170340.
• Halin, Rudolf (1965), „Über die Maximalzahl Fremder unendlicher Wege in Graphen”, Mathematische Nachrichten , 30 (1-2): 63-85, doi : 10.1002/mana.19650300106 , MR  0190031.
• Kron, Bernhard; Möller, Rögnvaldur G. (2008), "Końce metryczne, włókna i automorfizmy wykresów" (PDF) , Mathematische Nachrichten , 281 (1): 62-74, doi : 10.1002/mana.200510587 , MR  2376468.
• Mohar, Bojan (1991), „Niektóre relacje między właściwościami analitycznymi i geometrycznymi nieskończonych grafów” (PDF) , Matematyka dyskretna , 95 (1-3): 193-219, doi : 10.1016/0012-365X(91)90337-2 , MR  1141939.
• Robertson, Neil ; Seymour, Paweł ; Thomas, Robin (1991), "Z wyłączeniem nieskończonych nieletnich", Matematyka dyskretna , 95 (1-3): 303-319, doi : 10.1016/0012-365X (91) 90343-Z , MR  1141945.
• Seymour, Paweł ; Thomas, Robin (1991), „ Kontrprzykład drzewa opinającego końca wiernego”, Proceedings of the American Mathematical Society , 113 (4): 1163-1171, doi : 10.2307/2048796 , JSTOR  2048796 , MR  1045600.
• Stallings, John R. (1968), „O grupach bez skręcania z nieskończenie wieloma końcami”, Annals of Mathematics , Druga seria, 88 (2): 312-334, doi : 10.2307/1970577 , JSTOR  1970577 , MR  0228573.
• Stallings, John R. (1971), Teoria grup i trójwymiarowe rozmaitości: A James K. Whittemore Lecture in Mathematics wygłoszony na Uniwersytecie Yale, 1969 , Yale Mathematical Monographs, 4 , New Haven, Connecticut: Yale University Press, MR  0415622.
• Thomassen, Carsten (1992), „Nieskończone połączone wykresy bez drzew opinających zachowujących koniec”, Journal of Combinatorial Theory , Seria B, 54 (2): 322-324, doi : 10.1016/0095-8956 (92) 90059-7 , hdl : 10338.dmlcz/127625 , MR  1152455.