Кінець (теорія графів)

В математиці нескінченних графів, кінець графу інтуїтивно являє собою напрямок, в якому граф тягнеться до нескінченності. Кінець може бути математично формалізовано як клас еквівалентності нескінченних шляхів, які описують стратегії переслідування-ухилення у іграх на графі, або (в разі локально скінченних графів) як топологічні кінці топологічних просторів, пов'язаних з графом.

Кінці графів можуть бути використані (за допомогою графів Келі), щоб визначити кінці звичайно породжених груп. Скінченно породжені нескінченні групи мають один, два, або нескінченно багато кінців, а теорема Сталлінгса про кінці груп забезпечує розкладання для груп з більш ніж одним кінцем.

Визначення та характеристика

Кінці графів були визначені Рудольфом Халіном (1964) в термінах класів еквівалентності нескінченних шляхів.[1] Промінь в нескінченному графі є напівнескінченний простий шлях, тобто, це нескінченна послідовність вершин v₀, v₁, v₂, … , де кожна вершина з'являється більше одного разу в послідовності і кожні дві послідовні вершини в послідовності є двома кінцевими точками ребра в графі. Згідно з визначенням Халіна, два променя r₀ та r₁ є еквівалентними, якщо існує ще один промінь r₂ (він не обов'язково відрізняється від будь-якого з перших двох променів), який містить нескінченно багато вершин в кожному з r₀ та r₁. Це відношення еквівалентності: кожен промінь еквівалентний сам собі, тобто визначення симетрично щодо впорядкування двох променів, також можливо показати, що це відношення транзитивне. Таким чином, воно розділяє безліч всіх променів на класи еквівалентності, і Халін визначив кінець як один з цих класів еквівалентності.

Альтернативне визначення того ж відношення еквівалентності таке:[2] два променя r₀ та r₁ є еквівалентними, якщо не існує скінченної множини вершин X, что відокремлює нескінченно багато вершин r₀ з нескінченним числом вершин r₁. Це еквівалентно визначенню Халіна: якщо промінь r₂ з визначення Халіна існує, то будь-який роздільник повинен містити нескінченне число точок r₂ і, отже, не може бути скінченним, і навпаки, якщо r₂ не існує, то шлях, який чергується стільки раз, скільки можливо між r₀ та r_1, повинен формувати необхідний скінченний роздільник.

Кінці також мають більш конкретну характеристику з точки зору сховищ, функцій, які описують стратегії ухилення від сплати для гри переслідування-ухилення на графі G.[3] У грі в питанні, грабіжник намагається ухилитися від множини поліцейських при переході від вершини до вершини уздовж ребер G. У поліції є вертольоти, і тому вони не повинні слідувати по ребрах; Однак грабіжник може бачити, що поліція приходить і може вибрати, куди рухатися, перш ніж вертольоти приземлються. Одним з головних достоїнств є функцієя β, яка відображає кожну множину X розташування поліцейських до однієї з зв'язкових компонент підграфу, утвореного видаленням X; розбійник може ухилитися від поліції, рухаючись в кожному раунді гри в вершину цієї компоненти. Сховища повинні задовольняти властивості узгодження (що відповідає вимозі, що грабіжник не може переміщатися через вершини, на яких поліція вже приземлилась): якщо X є підмножина Y, і обидві множини X та Y є дійсними множинами місць для даної множини поліції, тоді β(X) повинна бути множиною, яка містить β(Y).Одним з головних достоїнств є порядок k, якщо сукупність місць поліції, для яких вона забезпечує стратегію евакуації включає в себе всі підмножини менші, ніж k вершин в графі; зокрема, вона має порядок ℵ₀, якщо він відображає кожну скінченну підмножину X вершин до компоненти G \ X. Кожному проміню в G відповідає сховище порядку ℵ₀, а саме, функція β, що відображає кожну скінченну множину X до єдиної компоненти G \ X, яка містить нескінченно багато вершин променя. І навпаки, кожне сховище порядку ℵ₀ може бути визначене таким чином променем. Два променя еквівалентні тоді і тільки тоді, коли вони визначають одне і теж сховище, так що кінці графу знаходяться у взаємно однозначній відповідності з його сховищами порядку ℵ₀.

Приклади

Частина нескінченної сітки графу з вершинами в точках, де дві лінії сітки зустрічаються. Незважаючи на безліч різних променів, він має тільки один кінець.

Якщо нескінченний граф G сам є променем, то він має нескінченне число променів-підграфів, по-одному, починаючи з кожної вершини G. Однак, всі ці промені еквівалентні один одному, так що G має тільки один кінець.

Якщо G ліс (тобто граф без скінченних циклів), то перетин будь-яких двох променів або шлях, або промінь; два променя еквівалентні, якщо їх перетин є променем. Якщо базова вершина вибирається в кожній компоненті зв'язності G, то кожен кінець G містить унікальний промінь, починаючи з однієї з базових вершин, так що кінці можуть бути розміщені у взаємно-однозначній відповідності з цими канонічними променями. Кожен рахунковий граф G має кістяковий ліс з тією ж множиною кінців, як G.[4] Однак існують незліченні нескінченні графи тільки з одним кінцем, в якому кожне кістякове дерево має нескінченно багато кінців.[5]

Якщо G є нескінченним графом решітки, то він має багато променів, і як завгодно великі множини вершин непересічних променів. Тим не менш, він має тільки один кінець. Це можна побачити найбільш легко, використовуючи характеристику кінців з точки зору сховищ: видалення будь-якої скінченної множини вершин залишає рівно одну нескінченну зв'язкову компоненту, тому є тільки одне сховище (то, яке відображає кожну скінченну множину з єдиною нескінченною зв'язною компонентою).

Зв'язок з топологічними кінцями

У теоретико-множинній топології, існує поняття кінця, який подібний до, але не зовсім такий же, як, поняття кінця в теорії графів, введений набагато раніше Фрейденталем (1931). Якщо топологічний простір може бути покрито вкладеною послідовністю компактів $\kappa _{0}\subset \kappa _{1}\subset \kappa _{2}\dots$ , то кінець простору являє собою послідовність компонентів $U_{0}\supset U_{1}\supset U_{2}\dots$ доповнень компактних множин. Це визначення не залежить від вибору компактів: кінці, які визначаються одним таким вибором можуть бути розміщені у взаємно-однозначній відповідності з кінцями, визначеними будь-яким іншим вибором.

Нескінченний граф G може бути побудований у топологічному просторі в двома різними, але пов'язаними способами:

Заміна кожної вершини графу на точку і кожного ребра графу на відкритий одиничний інтервал породжує Гаусдорфів простір з графом, в якому множина S визначає, що буде відкритим, коли кожен перетин S з ребром графу є відкрите підмножина одиничного інтервалу.
Заміна кожної вершини графу точкою і кожного ребра графу точкою робить простір нехаусдорфовим, в якому відкриті множини є множини S з тією властивістю, що, якщо вершина v з G належить S, то належить й кожне ребро, що має v як один з його кінців.

У будь-якому випадку, кожний скінченний підграф відповідає компактним підпросторам топологічного простору, і кожен компактний підпростір відповідає скінченному підграфу разом з, в разі Хаусдорфого простора, скінченним числом компактних власних підмножин ребер. Таким чином, граф може бути покритий вкладеною послідовністю компактів тоді і тільки тоді, коли вона локально скінченна, тобто граф має скінченне число ребер в кожній вершині.

Якщо граф G зв'язний і локально скінченний, то він має компактне покриття, в якому множина κ_i це множина вершин, що знаходяться на відстані не більше i від деякої довільно обраної вихідної вершини. У цьому випадку будь-яке сховище β визначає кінець топологічного простору, в якому

 $U_{i}=\beta (\kappa _{i})$ . І навпаки, якщо  $U_{0}\supset U_{1}\supset U_{2}\dots$   є кінцем топологічного простору, утвореного із G, він визначає сховище, в якому β (X) є компонент, який містить U_i, де i будь-яке число, таке, що κ_i містить X.  Таким чином, для зв'язних і локально скінченних графів, топологічні кінці знаходяться у взаємно-однозначній відповідності з кінцями графів.[6]

Для графів, які не можуть бути локально-скінченними, можна визначити топологічний простір з графу та його кінців. Цей простір може бути представлений як метричний простір тоді і тільки тоді, коли граф має нормальне кістякове дерево — коренева остова така, що кожне ребро графу з'єднує пару предок-нащадок. Якщо нормальний остов існує, то він має той же набір кінців, що й даний граф: кожен кінець графу повинен містити рівно один нескінченний шлях в дереві.[7]

Спеціальні види кінців

Вільні кінці

Кінець Е графу G визначається як вільний кінець, якщо існує скінченна множина X вершин, така, що X відокремлює Е від усіх інших кінців графу. Тобто, з точки зору сховищ, β_E(X) не перетинається з β_D(X) для будь-якого іншого кінця D. У графі зі скінченним числом кінців, кожен кінець повинен бути вільним. Халін (1964) доводить, що, якщо G має нескінченно багато кінців, то або існує кінець, який не вільний, або існує нескінченне сімейство променів, які поділяють загальну вихідну вершину, і в іншому випадку не перетинаються один з одним.

Товсті кінці

Товстий кінець графу G є кінцем, який містить нескінченне число попарно непересічних променів. Теорема сітки Халіна характеризує графіки, які містять товсті кінці: вони точно графи, які мають підрозділ гексагонально-мозаїчних підграфів.[8]

Спеціальні види графів

Симетричні і майже симетричні графи

Мохар (1991) визначає зв'язний локально скінченний граф, як «майже симетричний», якщо існує вершина V і число D таке, що для будь-якої іншої вершини w, існує автоморфізм графу, для якого образ V знаходиться на відстані D від w; що те ж саме, що зв'язний локально скінченний граф є майже симетричним, якщо його група автоморфізмів має скінченне число орбіт. Мохар показує, що кожен зв'язний локально-скінченний майже симетричний граф, має число кінців або не більше двох або незліченне число; якщо він незліченний, кінці мають топологію множини Кантора. Крім того, Мохар показує, що число кінців контролює константу Чігера

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

де V пробігає всі скінченні непорожні множини вершин графу і де $\partial V$ позначає множину ребер з однією кінцевою точкою в V. Для майже симетричних графів з незліченною кількістю кінців, h > 0; однак, для майже симетричних графів тільки з двома кінцями, h = 0.

Граф Келі

Граф Келі вільної групи на двох генераторах a та b. Кінці групи знаходяться у взаємно-однозначній відповідності з променями (нескінченні шляхи) від одиничного елемента е до периферії на малюнку.

Кожна група і множина генераторів групи визначають граф Келі, граф, вершинами якого є елементи групи і ребра — пари елементів (x,gx) де g є одним з генераторів. У разі звичайно породженою групи, кінці групи визначаються як кінці графу Келі для скінченної множини генераторів; це визначення інваріантно щодо вибору генераторів, в тому сенсі, що якщо обрані дві різні скінченні множини генераторів, кінці двох октав графів знаходяться у взаємно-однозначній відповідності один з одним.

Наприклад, кожна вільна група має граф Келі (для її вільних генераторів), що є деревом. Вільна група на одному генераторі має подвійний нескінченний шлях як її граф Келі, з двома кінцями. Будь-яка інша вільна група має нескінченно багато кінців.

Кожна звичайно породжена нескінченна група має або 1, 2, або нескінченно багато кінців, і теорема Сталлінгса про кінці груп забезпечує розкладання груп з більш ніж одним кінцем. Зокрема:

Звичайно породжена нескінченна група має 2 кінці тоді і тільки тоді, коли вона має циклічну підгрупу скінченного індексу.
Звичайно породжена нескінченна група має нескінченно багато кінців тоді і тільки тоді, коли вона є або нетривіальним вільним твором з об'єднаною підгрупою, або HNN-розширенням з скінченним об'єднанням.
Всі інші звичайно породжені нескінченні групи мають рівно один кінець.

Примітки

However, as Krön та Möller, (2008) point out, ends of graphs were already considered by Freudenthal, (1945).
E.g., this is the form of the equivalence relation used by Diestel та Kühn, (2003).
The haven nomenclature, and the fact that two rays define the same haven if and only if they are equivalent, is due to Robertson, Seymour та Thomas, (1991). Diestel та Kühn, (2003) proved that every haven comes from an end, completing the bijection between ends and havens, using a different nomenclature in which they called havens «directions».
More precisely, in the original formulation of this result by Halin, (1964) in which ends are defined as equivalence classes of rays, every equivalence class of rays of G contains a unique nonempty equivalence class of rays of the spanning forest. In terms of havens, there is a one-to-one correspondence of havens of order ℵ₀ between G and its spanning tree T for which $\beta _{T}(X)\subset \beta _{G}(X)$ for every finite set X and every corresponding pair of havens β_T and β_G.
Seymour та Thomas, (1991); Thomassen, (1992); Diestel, (1992).
Diestel та Kühn, (2003).
Diestel, (2006).
Halin, (1965); Diestel, (2004).

Посилання

Diestel, Reinhard (1992). The end structure of a graph: recent results and open problems. Discrete Mathematics 100 (1-3): 313–327. MR 1172358. doi:10.1016/0012-365X(92)90650-5..
Diestel, Reinhard (2004). A short proof of Halin's grid theorem. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 74: 237–242. MR 2112834. doi:10.1007/BF02941538..
Diestel, Reinhard (2006). End spaces and spanning trees. Journal of Combinatorial Theory. Series B 96 (6): 846–854. MR 2274079. doi:10.1016/j.jctb.2006.02.010..
Diestel, Reinhard; Kühn, Daniela (2003). Graph-theoretical versus topological ends of graphs. Journal of Combinatorial Theory. Series B 87 (1): 197–206. MR 1967888. doi:10.1016/S0095-8956(02)00034-5..
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. MR 0012214. doi:10.1007/bf02566233..
Halin, Rudolf (1964). Über unendliche Wege in Graphen. Mathematische Annalen 157: 125–137. MR 0170340. doi:10.1007/bf01362670..
Halin, Rudolf (1965). Über die Maximalzahl fremder unendlicher Wege in Graphen. Mathematische Nachrichten 30: 63–85. MR 0190031. doi:10.1002/mana.19650300106..
Krön, Bernhard; Möller, Rögnvaldur G. (2008). Metric ends, fibers and automorphisms of graphs. Mathematische Nachrichten 281 (1): 62–74. MR 2376468. doi:10.1002/mana.200510587..
Mohar, Bojan (1991). Some relations between analytic and geometric properties of infinite graphs. Discrete Mathematics 95 (1-3): 193–219. MR 1141939. doi:10.1016/0012-365X(91)90337-2..
Robertson, Neil; Seymour, Paul; Thomas, Robin (1991). Excluding infinite minors. Discrete Mathematics 95 (1-3): 303–319. MR 1141945. doi:10.1016/0012-365X(91)90343-Z..
Seymour, Paul; Thomas, Robin (1991). An end-faithful spanning tree counterexample. Proceedings of the American Mathematical Society 113 (4): 1163–1171. MR 1045600. doi:10.2307/2048796..
Stallings, John R. (1968). On torsion-free groups with infinitely many ends. Annals of Mathematics. Second Series 88: 312–334. MR 0228573. doi:10.2307/1970577..
Stallings, John R. (1971). Group theory and three-dimensional manifolds: A James K. Whittemore Lecture in Mathematics given at Yale University, 1969. Yale Mathematical Monographs 4. New Haven, Conn.: Yale University Press. MR 0415622..
Thomassen, Carsten (1992). Infinite connected graphs with no end-preserving spanning trees. Journal of Combinatorial Theory. Series B 54 (2): 322–324. MR 1152455. doi:10.1016/0095-8956(92)90059-7..

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] However, as Krön та Möller, (2008) point out, ends of graphs were already considered by Freudenthal, (1945).

[2] E.g., this is the form of the equivalence relation used by Diestel та Kühn, (2003).

[3] The haven nomenclature, and the fact that two rays define the same haven if and only if they are equivalent, is due to Robertson, Seymour та Thomas, (1991). Diestel та Kühn, (2003) proved that every haven comes from an end, completing the bijection between ends and havens, using a different nomenclature in which they called havens «directions».

[4] More precisely, in the original formulation of this result by Halin, (1964) in which ends are defined as equivalence classes of rays, every equivalence class of rays of G contains a unique nonempty equivalence class of rays of the spanning forest. In terms of havens, there is a one-to-one correspondence of havens of order ℵ₀ between G and its spanning tree T for which $\beta _{T}(X)\subset \beta _{G}(X)$ for every finite set X and every corresponding pair of havens β_T and β_G.

[5] Seymour та Thomas, (1991); Thomassen, (1992); Diestel, (1992).

[6] Diestel та Kühn, (2003).

[FOOTNOTEDiestel2006-7] Diestel, (2006).

[8] Halin, (1965); Diestel, (2004).