Konec (teorie grafů) - End (graph theory) - Wikipedia

V matematika z nekonečné grafy, an konec grafu představuje intuitivně směr, kterým se graf rozšiřuje do nekonečna. Konce mohou být matematicky formalizovány jako třídy ekvivalence nekonečný cesty, tak jako ráje popisující strategie pro pronásledování hry v grafu, nebo (v případě lokálně konečných grafů) jako topologické konce z topologické prostory spojené s grafem.

Lze použít konce grafů (přes Cayleyovy grafy ) definovat konce konečně generované skupiny. Konečně generované nekonečné skupiny mají jeden, dva nebo nekonečně mnoho konců a Věta o zastavení o koncích skupin poskytuje rozklad pro skupiny s více než jedním koncem.

Definice a charakterizace

Konce grafů byly definovány pomocí Rudolf Halin  (1964 ), pokud jde o třídy ekvivalence nekonečných cest.^[1] A paprsek v nekonečném grafu je polo nekonečný jednoduchá cesta; tj. je to nekonečná posloupnost vrcholů proti₀, proti₁, proti₂, ... ve kterém se každý vrchol objeví nanejvýš jednou v posloupnosti a každé dva po sobě jdoucí vrcholy v posloupnosti jsou dva koncové body hrany v grafu. Podle Halinovy ​​definice dva paprsky r₀ a r₁ jsou ekvivalentní, pokud existuje další paprsek r₂ (nemusí se nutně lišit od jednoho z prvních dvou paprsků), který obsahuje nekonečně mnoho vrcholů v každém z nich r₀ a r₁. Tohle je vztah ekvivalence: každý paprsek je ekvivalentní sobě samému, definice je symetrická s ohledem na uspořádání obou paprsků a lze jej ukázat jako tranzitivní. Proto rozděluje množinu všech paprsků na třídy ekvivalence a Halin definovali konec jako jednu z těchto tříd ekvivalence.

Rovněž byla použita alternativní definice stejného vztahu ekvivalence:^[2] dva paprsky r₀ a r₁ jsou ekvivalentní, pokud neexistuje konečná množina X vrcholů, které odděluje nekonečně mnoho vrcholů r₀ z nekonečně mnoha vrcholů r₁. To odpovídá Halinově definici: pokud paprsek r₂ z Halinovy ​​definice existuje, pak jakýkoli oddělovač musí obsahovat nekonečně mnoho bodů r₂ a proto nemohou být konečné, a naopak pokud r₂ neexistuje tedy cesta, která se mezi sebou střídá tolikrát, kolikrát je to možné r₀ a r₁ musí tvořit požadovaný konečný oddělovač.

Konce mají také konkrétnější charakterizaci, pokud jde o ráje, funkce, které popisují únikové strategie pro pronásledování hry v grafu G.^[3] V dotyčné hře se lupič snaží uniknout množině policistů pohybem od vrcholu k vrcholu po okrajích G. Policie má vrtulníky, a proto nemusí sledovat okraje; lupič však vidí přicházející policii a před přistáním vrtulníků si může vybrat, kam se má pohnout dále. Útočiště je funkce β, která mapuje každou sadu X policejních stanovišť k jedné z připojených součástí podgrafu vytvořeného vymazáním X; lupič se může vyhnout policii pohybem v každém kole hry na vrchol v této složce. Útočiště musí splňovat vlastnost konzistence (odpovídající požadavku, aby se lupič nemohl pohybovat přes vrcholy, na které policie již přistála): pokud X je podmnožinou Ya obojí X a Y jsou platné sady míst pro danou sadu policie, pak β (X) musí být nadmnožinou β (Y). Útočiště má pořádek k pokud kolekce policejních lokací, pro které poskytuje únikovou strategii, zahrnuje všechny podskupiny menší než k vrcholy v grafu; zejména má pořádek ℵ₀ pokud mapuje každou konečnou podmnožinu X vrcholů na komponentu G \ X. Každý paprsek dovnitř G odpovídá útočišti řádu ℵ₀, jmenovitě funkce β, která mapuje každou konečnou množinu X k jedinečné složce G \ X který obsahuje nekonečně mnoho vrcholů paprsku. Naopak, každý útočiště pořádku ℵ₀ lze takto definovat paprskem.^[4] Dva paprsky jsou ekvivalentní tehdy a jen tehdy, pokud definují stejný přístav, takže konce grafu jsou v korespondenci jedna k jedné s jeho ráji řádu ℵ₀.

Příklady

Část nekonečna mřížkový graf, s vrcholy v bodech, kde se setkávají dvě čáry mřížky. Přestože má mnoho různých paprsků, má jen jeden konec.

Pokud nekonečný graf G je sám paprskem, pak má nekonečně mnoho paprskových podgrafů, jeden vycházející z každého vrcholu G. Všechny tyto paprsky jsou si však navzájem rovnocenné G má pouze jeden konec.

Li G je les (tj. graf bez konečných cyklů), pak průsečík jakýchkoli dvou paprsků je cesta nebo paprsek; dva paprsky jsou ekvivalentní, pokud je jejich průsečík paprsek. Pokud je v každé připojené komponentě zvolen základní vrchol G, pak každý konec G obsahuje jedinečný paprsek vycházející z jednoho ze základních vrcholů, takže konce mohou být umístěny v korespondenci jedna k jedné s těmito kanonickými paprsky. Každý spočetný graf G má překlenující les se stejnou sadou konců jako G.^[5] Existují však nespočetně nekonečné grafy pouze s jedním koncem, ve kterém má každý kostra nekonečně mnoho konců.^[6]

Li G je nekonečný mřížkový graf, pak má mnoho paprsků a libovolně velké sady vrcholů disjunktních paprsků. Má to však jen jeden konec. To lze nejsnadněji vidět pomocí charakterizace konců z hlediska přístavů: odstranění jakékoli konečné sady vrcholů ponechává právě jednu nekonečnou spojenou komponentu, takže existuje pouze jeden přístav (ten, který mapuje každou konečnou množinu na jedinečnou nekonečnou spojenou součástka).

Vztah k topologickým cílům

v bodová topologie, existuje koncept konce, který je podobný konceptu konce v teorii grafů, ale ne úplně stejný jako koncept, který sahá mnohem dříve Freudenthal (1931). Pokud lze topologický prostor pokrýt vnořenou sekvencí kompaktní sady ${ displaystyle kappa _ {0} podmnožina kappa _ {1} podmnožina kappa _ {2} tečky}$, pak konec prostoru je sekvence komponent ${ displaystyle U_ {0} supset U_ {1} supset U_ {2} dots}$ doplňků kompaktních sad. Tato definice nezávisí na volbě kompaktních množin: konce definované jednou takovou volbou mohou být umístěny v korespondenci jedna k jedné s konci definovanými jakoukoli jinou volbou.

Nekonečný graf G může být vytvořen do topologického prostoru dvěma různými, ale souvisejícími způsoby:

• Nahrazení každého vrcholu grafu bodem a každé hrany grafu otevřením jednotkový interval vyrábí a Hausdorffův prostor z grafu, ve kterém množina S je definován jako otevřený pokaždé, když každá křižovatka S s okrajem grafu je otevřená podmnožina jednotkového intervalu.
• Nahrazení každého vrcholu grafu bodem a každou hranou grafu bodem vytvoří prostor, který není Hausdorffův, ve kterém jsou otevřené množiny množinami S s vlastností, že pokud vrchol proti z G patří S, pak také každá hrana proti jako jeden z jeho koncových bodů.

V obou případech každý konečný podgraf G odpovídá kompaktnímu podprostoru topologického prostoru a každý kompaktní podprostor odpovídá konečnému podgrafu spolu s, v případě Hausdorffa, konečně mnoha kompaktními vlastními podmnožinami hran. Graf tedy může být zakryt vnořenou posloupností kompaktních množin právě tehdy, je-li lokálně konečný, mající konečný počet hran na každém vrcholu.

Pokud graf G je spojen a lokálně konečný, pak má kompaktní kryt, ve kterém je množina κ_i je sada vrcholů ve vzdálenosti maximálně i z libovolně zvoleného počátečního vrcholu. V tomto případě jakýkoli přístav β definuje konec topologického prostoru, ve kterém ${ displaystyle U_ {i} = beta ( kappa _ {i})}$. A naopak, pokud ${ displaystyle U_ {0} supset U_ {1} supset U_ {2} dots}$ je konec topologického prostoru definovaného z G, definuje útočiště, ve kterém β (X) je složka obsahující U_i, kde i je libovolné číslo dostatečně velké na to, že κ_i obsahuje X. U spojených a lokálně konečných grafů jsou tedy topologické konce v osobní korespondenci s teoreticko-teoretickými konci.^[7]

Pro grafy, které nemusí být lokálně konečné, je stále možné definovat topologický prostor z grafu a jeho konců. Tento prostor lze reprezentovat jako a metrický prostor právě když má graf a normální kostra, zakořeněný kostra tak, že každá hrana grafu spojuje pár předků a potomků. Pokud existuje normální kostra, má stejnou sadu konců jako daný graf: každý konec grafu musí obsahovat přesně jednu nekonečnou cestu ve stromu.^[8]

Zvláštní druhy konců

Volné konce

Konec E grafu G je definován jako a volný konec pokud existuje konečná množina X vrcholů s vlastností, že X odděluje E ze všech ostatních konců grafu. (To znamená, pokud jde o ráje, β_E(X) je disjunktní od β_D(X) za každý druhý konec D.) V grafu s konečně mnoha konci musí být každý konec volný. Halin (1964) dokazuje, že pokud G má nekonečně mnoho konců, pak buď existuje konec, který není volný, nebo existuje nekonečná rodina paprsků, které sdílejí společný počáteční vrchol a jinak jsou navzájem nesouvislé.

Silné konce

A silný konec grafu G je konec, který obsahuje nekonečně mnoho párů -disjunktní paprsky. Halinova věta o mřížce charakterizuje grafy, které obsahují silné konce: jsou to přesně grafy, které mají a pododdělení z šestihranný obklad jako podgraf.^[9]

Speciální druhy grafů

Symetrické a téměř symetrické grafy

Mohar (1991) definuje připojený lokálně konečný graf jako „téměř symetrický“, pokud existuje vrchol proti a číslo D tak, že pro každý další vrchol w, tady je automorfismus grafu, pro který je obrázek proti je na dálku D z w; ekvivalentně je místně konečný graf téměř symetrický, pokud má jeho skupina automorfismu konečně mnoho drah. Jak ukazuje, pro každý připojený lokálně konečný téměř symetrický graf je počet konců buď maximálně dva, nebo nespočetný; pokud je to nepočítatelné, konce mají topologii a Cantor set. Mohar navíc ukazuje, že počet konců řídí Cheegerova konstanta

${ displaystyle h = inf left {{ frac {| částečné V |} {| V |}} right },}$

kde PROTI rozsahy přes všechny konečné neprázdné sady vrcholů grafu a kdekoli ${ displaystyle částečné V}$ označuje sadu hran s jedním koncovým bodem v PROTI. U téměř symetrických grafů s nespočetně mnoha konci h > 0; pro téměř symetrické grafy s pouze dvěma konci však h = 0.

Cayleyovy grafy

Cayleyův graf volná skupina na dvou generátorech A a b. Konce skupiny jsou v individuální korespondenci s paprsky (nekonečné cesty) z prvku identity E k okraji kresby.

Každý skupina a sada generátorů pro skupinu určuje a Cayleyův graf, graf, jehož vrcholy jsou prvky skupiny a hrany jsou páry prvků (X,gx) kde G je jedním z generátorů. V případě a konečně generovaná skupina, konce skupiny jsou definovány jako konce Cayleyova grafu pro konečnou sadu generátorů; tato definice je neměnná podle volby generátorů v tom smyslu, že pokud jsou vybrány dvě různé konečné sady generátorů, konce dvou Cayleyových grafů jsou navzájem v korespondenci jedna k jedné.

Například každý volná skupina má Cayleyův graf (pro jeho volné generátory), což je strom. Volná skupina na jednom generátoru má dvojnásobně nekonečnou cestu jako Cayleyův graf se dvěma konci. Každá další bezplatná skupina má nekonečně mnoho cílů.

Každá konečně vygenerovaná nekonečná skupina má buď 1, 2, nebo nekonečně mnoho konců a Věta o zastavení o koncích skupin poskytuje rozklad skupin s více než jedním koncem.^[10] Zejména:

1. Konečně vygenerovaná nekonečná skupina má 2 konce právě tehdy, pokud má a cyklický podskupina konečný index.
2. Konečně vygenerovaná nekonečná skupina má nekonečně mnoho konců právě tehdy, pokud jde buď o netriviální bezplatný produkt se sloučením nebo Prodloužení HNN s konečným sloučením.
3. Všechny ostatní konečně generované nekonečné skupiny mají přesně jeden konec.

Poznámky

Reference

• Diestel, Reinhard (1992), „Koncová struktura grafu: nedávné výsledky a otevřené problémy“, Diskrétní matematika, 100 (1–3): 313–327, doi:10.1016 / 0012-365X (92) 90650-5, PAN  1172358.
• Diestel, Reinhard (2004), „Krátký důkaz Halinovy ​​věty o mřížce“, Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 74: 237–242, doi:10.1007 / BF02941538, PAN  2112834.
• Diestel, Reinhard (2006), „Koncové prostory a kostry“, Journal of Combinatorial Theory, Řada B, 96 (6): 846–854, doi:10.1016 / j.jctb.2006.02.010, PAN  2274079.
• Diestel, Reinhard; Kühn, Daniela (2003), „Graf-teoretické versus topologické konce grafů“, Journal of Combinatorial Theory, Řada B, 87 (1): 197–206, doi:10.1016 / S0095-8956 (02) 00034-5, PAN  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, PAN  0012214.
• Halin, Rudolf (1964), „Über unendliche Wege in Graphen“, Mathematische Annalen, 157 (2): 125–137, doi:10.1007 / bf01362670, hdl:10338.dmlcz / 102294, PAN  0170340.
• Halin, Rudolf (1965), „Über die Maximalzahl fremder unendlicher Wege in Graphen“, Mathematische Nachrichten, 30 (1–2): 63–85, doi:10,1002 / many19650300106, PAN  0190031.
• Krön, Bernhard; Möller, Rögnvaldur G. (2008), „Metrické konce, vlákna a automorfismy grafů“ (PDF), Mathematische Nachrichten, 281 (1): 62–74, doi:10,1002 / many.200510587, PAN  2376468.
• Mohar, Bojan (1991), "Některé vztahy mezi analytickými a geometrickými vlastnostmi nekonečných grafů" (PDF), Diskrétní matematika, 95 (1–3): 193–219, doi:10.1016 / 0012-365X (91) 90337-2, PAN  1141939.
• Robertson, Neil; Seymour, Paule; Thomas, Robin (1991), „Vyjma nekonečných nezletilých“, Diskrétní matematika, 95 (1–3): 303–319, doi:10.1016 / 0012-365X (91) 90343-Z, PAN  1141945.
• Seymour, Paule; Thomas, Robin (1991), „Konečně věrný protiklad stromu“, Proceedings of the American Mathematical Society, 113 (4): 1163–1171, doi:10.2307/2048796, JSTOR  2048796, PAN  1045600.
• Stallings, John R. (1968), „O skupinách bez kroucení s nekonečně mnoha konci“, Annals of Mathematics, Druhá série, 88 (2): 312–334, doi:10.2307/1970577, JSTOR  1970577, PAN  0228573.
• Stallings, John R. (1971), Skupinová teorie a trojrozměrné varietá: Přednáška Jamese K. Whittemora z matematiky na Yale University, 1969, Yale Mathematical Monographs, 4, New Haven, Conn .: Yale University Press, PAN  0415622.
• Thomassen, Carsten (1992), „Nekonečné propojené grafy bez konců zachovaných stromů“, Journal of Combinatorial Theory, Řada B, 54 (2): 322–324, doi:10.1016/0095-8956(92)90059-7, hdl:10338.dmlcz / 127625, PAN  1152455.