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

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

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

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

^[en] сформулював визначення кінців графів у 1964 році в термінах класів еквівалентності нескінченних шляхів. Промінь в нескінченному графі є напівнескінченним простим шляхом, тобто це нескінченна послідовність вершин ${\displaystyle v_{0},v_{1},v_{2},\dots }$ … , де кожна вершина з'являється більше ніж один раз у послідовності і кожні дві послідовні вершини в послідовності є двома кінцевими точками ребра в графі. Згідно з визначенням Халіна, два променя ${\displaystyle r_{0}\dots }$ та ${\displaystyle r_{1}\dots }$ є еквівалентними, якщо існує промінь ${\displaystyle r_{2}\dots }$ (не обов'язково відмінний від будь-якого з перших двох), який містить нескінченно багато вершин в кожному з ${\displaystyle r_{0}\dots }$ та ${\displaystyle r_{1}\dots }$. Це відношення еквівалентності: кожен промінь еквівалентний сам собі. Визначення симетричне щодо впорядкування двох променів. Можна також показати, що це відношення транзитивне. Таким чином, воно розділяє безліч всіх променів на класи еквівалентності. Халін визначив кінець як один з цих класів еквівалентності.

Існує альтернативне визначення того ж відношення еквівалентності: два променя ${\displaystyle r_{0}\dots }$ та${\displaystyle r_{1}\dots }$ є еквівалентними, якщо не існує скінченної множини вершин X, что відокремлює нескінченно багато вершин ${\displaystyle r_{0}\dots }$ з нескінченним числом вершин ${\displaystyle r_{1}\dots }$. Це еквівалентно визначенню Халіна: якщо промінь ${\displaystyle r_{2}\dots }$ з визначення Халіна існує, то будь-який роздільник повинен містити нескінченне число точок ${\displaystyle r_{2}\dots }$ і, отже, не може бути скінченним, і навпаки, якщо ${\displaystyle r_{2}\dots }$ не існує, то шлях, який чергується стільки раз, скільки можливо між ${\displaystyle r_{0}}$ та ${\displaystyle r_{1}\dots }$ повинен формувати необхідний скінченний роздільник. Кінці також мають більш конкретну характеристику з точки зору укриттів — функцій, які описують стратегії ухилення для ігор переслідування-ухилення на графі G. Розглядається гра, у якій грабіжник намагається вивернутися від множини поліцейських при переході від вершини до вершини уздовж ребер ${\displaystyle G}$. У поліції є вертольоти, тому бандит повинен рухатися по ребрах; Однак грабіжник вміє помічати наближення поліції та може вибрати напрям руху до приземення вертольотів. Однією з головних переваг є функція β, яка відображає кожну множину ${\displaystyle X}$ розташування поліцейських до однієї із зв'язкових компонент підграфу, утвореного видаленням ${\displaystyle X}$; розбійник може ухилитися від поліції, рухаючись в кожному раунді гри в вершину цієї компоненти. Укриття повинні задовольняти властивості узгодження, тобто грабіжник не може переміщатися через вершини, на яких поліція вже приземлилась. якщо ${\displaystyle X}$ є підмножиною ${\displaystyle Y}$, і обидві множини ${\displaystyle X}$ та ${\displaystyle Y}$ є дійсними множинами місць для даної множини поліції, тоді β(${\displaystyle X}$) повинна бути множиною, яка містить β(${\displaystyle Y}$). Укриття має порядок k, якщо сукупність місць поліції, для яких вона забезпечує стратегію евакуації включає в себе всі підмножини менші, ніж k вершин в графі. Зокрема, вона має порядок ℵ₀, якщо він відображає кожну скінченну підмножину ${\displaystyle X}$ вершин до компоненти ${\displaystyle G}$ \ ${\displaystyle X}$. Кожному променю в ${\displaystyle G}$ відповідає укриття порядку ℵ₀, а саме, функція β, що відображає кожну скінченну множину ${\displaystyle X}$ до єдиної компоненти ${\displaystyle G}$ \ ${\displaystyle X}$, яка містить нескінченно багато вершин променя. І навпаки, кожне укриття порядку ℵ₀ може бути визначене таким чином через промінь. Два променя еквівалентні тоді і тільки тоді, коли вони визначають одне і тежукриття, так що кінці графу знаходяться у взаємно однозначній відповідності з його сховищами порядку ℵ₀.

Приклади

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

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

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

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

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

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

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

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

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

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

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

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

Вільні кінці

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

Товсті кінці

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

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

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

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

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

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

Граф Келі

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

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

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

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

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

Примітки

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 ${\displaystyle \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).
7. Diestel, (2006).
8. Halin, (1965); Diestel, (2004).

Посилання

• Diestel, Reinhard (1992), The end structure of a graph: recent results and open problems, , 100 (1-3): 313—327, doi:10.1016/0012-365X(92)90650-5, MR 1172358.
• 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 (2006), End spaces and spanning trees, , Series B, 96 (6): 846—854, doi:10.1016/j.jctb.2006.02.010, MR 2274079.
• Diestel, Reinhard; (2003), Graph-theoretical versus topological ends of graphs, , Series B, 87 (1): 197—206, doi:10.1016/S0095-8956(02)00034-5, MR 1967888.
• (1931), Über die Enden topologischer Räume und Gruppen, , 33: 692—713, doi:10.1007/BF01174375.
• (1945), Über die Enden diskreter Räume und Gruppen, Commentarii Mathematici Helvetici, 17: 1—38, doi:10.1007/bf02566233, MR 0012214.
• (1964), Über unendliche Wege in Graphen, Mathematische Annalen, 157: 125—137, doi:10.1007/bf01362670, MR 0170340.
• (1965), Über die Maximalzahl fremder unendlicher Wege in Graphen, , 30: 63—85, doi:10.1002/mana.19650300106, MR 0190031.
• Krön, Bernhard; Möller, Rögnvaldur G. (2008), (PDF), , 281 (1): 62—74, doi:10.1002/mana.200510587, MR 2376468, архів оригіналу (PDF) за 4 березня 2016, процитовано 28 червня 2016.
• (1991), (PDF), Discrete Mathematics, 95 (1-3): 193—219, doi:10.1016/0012-365X(91)90337-2, MR 1141939, архів оригіналу (PDF) за 3 березня 2016, процитовано 28 червня 2016.
• ; ; (1991), Excluding infinite minors, , 95 (1-3): 303—319, doi:10.1016/0012-365X(91)90343-Z, MR 1141945.
• ; (1991), An end-faithful spanning tree counterexample, , 113 (4): 1163—1171, doi:10.2307/2048796, MR 1045600.
• (1968), On torsion-free groups with infinitely many ends, Annals of Mathematics, Second Series, 88: 312—334, doi:10.2307/1970577, MR 0228573.
• (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.
• (1992), Infinite connected graphs with no end-preserving spanning trees, , Series B, 54 (2): 322—324, doi:10.1016/0095-8956(92)90059-7, MR 1152455.