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

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

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

Определение и характеристика

Концы графов были определены Рудольфом Халином ( 1964 ) в терминах классов эквивалентности бесконечных путей. ^[1] А луч в бесконечном графе — это полубесконечный простой путь ; то есть это бесконечная последовательность вершин $v_{0},v_{1},v_{2},\dots$ в котором каждая вершина появляется в последовательности не более одного раза, а каждые две последовательные вершины в последовательности являются двумя конечными точками ребра в графе. По определению Халина, два луча $r_{0}$ и $r_{1}$ эквивалентны, если существует луч $r_{2}$ (который может равняться одному из двух данных лучей), который содержит бесконечное число вершин в каждом из $r_{0}$ и $r_{1}$ . Это отношение эквивалентности : каждый луч эквивалентен самому себе, определение симметрично относительно порядка двух лучей, и можно показать, что оно транзитивно . Следовательно, он разбивает множество всех лучей на классы эквивалентности , и Халин определил конец как один из этих классов эквивалентности. ^[2]

Также использовалось альтернативное определение того же отношения эквивалентности: два луча $r_{0}$ и $r_{1}$ эквивалентны, если не существует конечного множества $X$ вершин, разделяющее бесконечное число вершин $r_{0}$ из бесконечного числа вершин $r_{1}$ . ^[3] Это эквивалентно определению Халина: если луч $r_{2}$ из определения Халина существует, то любой разделитель должен содержать бесконечно много точек $r_{2}$ и поэтому не может быть конечным, и наоборот, если $r_{2}$ не существует тогда пути, который чередуется как можно больше раз между $r_{0}$ и $r_{1}$ должен образовывать искомый конечный сепаратор.

Концы также имеют более конкретную характеристику в терминах убежищ — функций, описывающих стратегии уклонения для игр преследования-уклонения на графе. $G$ . ^[4] В рассматриваемой игре грабитель пытается уйти от группы полицейских, перемещаясь от вершины к вершине по краям $G$ . У полиции есть вертолеты, поэтому ей не нужно следить за краями; однако грабитель видит приближающуюся полицию и может выбрать, куда двигаться дальше, прежде чем приземлятся вертолеты. Убежище – это функция $\beta$ который отображает каждый набор $X$ полицейских локаций к одному из связных компонентов подграфа, образованного удалением $X$ ; грабитель может уйти от полиции, перемещаясь в каждом раунде игры в вершину внутри этого компонента. Убежища должны удовлетворять свойству согласованности (соответствующему требованию, чтобы грабитель не мог перемещаться через вершины, на которых уже высадилась полиция): если $X$ является подмножеством $Y$ и оба $X$ и $Y$ являются действительными наборами локаций для данного набора полиции, тогда $\beta (X)$ должно быть надмножеством $\beta (Y)$ . В убежище есть порядок $k$ если совокупность полицейских участков, для которых предусмотрена стратегия побега, включает в себя все подмножества размером менее $k$ вершины графа; в частности, у него есть порядок $\aleph _{0}$ (наименьшее число алефа ), если оно отображает каждое конечное подмножество $X$ вершин в компоненту $G\setminus X$ . Каждый луч в $G$ соответствует пристанищу порядка $\aleph _{0}$ , а именно функция $\beta$ ; который отображает каждое конечное множество $X$ к уникальному компоненту $G\setminus X$ содержащая бесконечное число вершин луча. И наоборот, всякая гавань порядка $\aleph _{0}$ таким образом можно определить лучом. ^[5] Два луча эквивалентны тогда и только тогда, когда они определяют одно и то же убежище, поэтому концы графа находятся во взаимно однозначном соответствии с его убежищами порядка. $\aleph _{0}$ . ^[4]

Примеры

Если бесконечный граф $G$ сам является лучом, то он имеет бесконечно много подграфов лучей, по одному из каждой вершины $G$ . Однако все эти лучи эквивалентны друг другу, поэтому $G$ имеет только один конец.

Если $G$ является лесом (т. е. графом без конечных циклов), то пересечение любых двух лучей является либо путём, либо лучом; два луча эквивалентны, если их пересечение является лучом. Если в каждой компоненте связности выбрана базовая вершина $G$ , то каждый конец $G$ содержит уникальный луч, начинающийся из одной из базовых вершин, поэтому концы можно поставить во взаимно однозначное соответствие этим каноническим лучам. Каждый счетный граф $G$ имеет охватывающий лес с тем же набором концов, что и $G$ . ^[6] Однако существуют бесчисленные бесконечные графы только с одним концом, в которых каждое остовное дерево имеет бесконечно много концов. ^[7]

Если $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$ соответствует компактному подпространству топологического пространства, а каждое компактное подпространство соответствует конечному подграфу вместе с, в случае Хаусдорфа, конечным числом компактных собственных подмножеств ребер. Таким образом, граф может быть покрыт вложенной последовательностью компактов тогда и только тогда, когда он локально конечен и имеет конечное число ребер в каждой вершине.

Если график $G$ связно и локально конечно, то оно имеет компактное покрытие, в котором множество $\kappa _{i}$ это набор вершин на расстоянии не более $i$ из некоторой произвольно выбранной начальной вершины. В этом случае любое убежище $\beta$ определяет конец топологического пространства, в котором $U_{i}=\beta (\kappa _{i})$ . И наоборот, если $U_{0}\supset U_{1}\supset U_{2}\dots$ является концом топологического пространства, определенного из $G$ , он определяет убежище, в котором $\beta (X)$ компонент, содержащий $U_{i}$ , где $i$ какое-либо число достаточно велико, чтобы $\kappa _{i}$ содержит $X$ . Таким образом, для связных и локально конечных графов топологические концы находятся во взаимно однозначном соответствии с теоретико-графовыми концами. ^[8]

Для графов, которые не могут быть локально конечными, все же можно определить топологическое пространство из графа и его концов. Это пространство может быть представлено как метрическое пространство тогда и только тогда, когда граф имеет нормальное остовное дерево , корневое остовное дерево, такое, что каждое ребро графа соединяет пару предок-потомок. Если существует нормальное остовное дерево, оно имеет тот же набор концов, что и данный граф: каждый конец графа должен содержать ровно один бесконечный путь в дереве. ^[9]

Особые виды концов

Свободные концы

Конец $E$ графика $G$ определяется как свободный конец, если существует конечное множество $X$ вершин со свойством, что $X$ отделяет $E$ со всех остальных концов графа. (То есть, с точки зрения убежищ, $\beta _{E}(X)$ не пересекается с $\beta _{D}(X)$ для любого другого конца $D$ .) В графе с конечным числом концов каждый конец должен быть свободным. Халин (1964) доказывает, что если $G$ имеет бесконечно много концов, то либо существует несвободный конец, либо существует бесконечное семейство лучей, имеющих общую начальную вершину и в остальном не пересекающихся друг с другом.

Толстые концы

Толстый конец графика $G$ — конец, содержащий бесконечное число попарно непересекающихся лучей. Теорема Халина о сетке характеризует графы, содержащие толстые концы: это именно те графы, у которых есть подразделение шестиугольной мозаики в виде подграфа. ^[10]

Специальные виды графиков

Симметричные и почти симметричные графы

Мохар (1991) определяет связный локально конечный граф как «почти симметричный», если существует вершина $v$ и номер $D$ такая, что для каждой второй вершины $w$ , существует автоморфизм графа, для которого образ $v$ находится на расстоянии $D$ из $w$ ; эквивалентно, связный локально конечный граф почти симметричен, если его группа автоморфизмов имеет конечное число орбит. Как он показывает, для каждого связного локально конечного почти симметричного графа число концов либо не более двух, либо несчетно; если оно несчетно, то концы имеют топологию канторового множества . Кроме того, Мохар показывает, что количество концов контролирует константу Чигера. $h=\inf \left\{{\frac {|\partial V|}{|V|}}\right\},$ где $V$ пробегает все конечные непустые множества вершин графа игде $\partial V$ обозначает множество ребер с одной конечной точкой в $V$ . Для почти симметричных графов с несчетным числом концов $h>0$ ; однако для почти симметричных графов только с двумя концами $h=0$ .

Графики Кэли

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

Например, каждая свободная группа имеет граф Кэли (для ее свободных генераторов), который является деревом. Свободная группа с одним генератором имеет в качестве графа Кэли дважды бесконечный путь с двумя концами. Любая другая свободная группа имеет бесконечно много концов.

Каждая конечно порожденная бесконечная группа имеет либо 1, 2, либо бесконечно много концов, а теорема Столлингса о концах групп обеспечивает разложение групп с более чем одним концом. ^[11] В частности:

Конечно порожденная бесконечная группа имеет 2 конца тогда и только тогда, когда она имеет циклическую подгруппу конечного индекса .
Конечно порожденная бесконечная группа имеет бесконечное число концов тогда и только тогда, когда она является либо нетривиальным свободным произведением с объединением , либо HNN-расширением с конечным объединением.
Все остальные конечно порожденные бесконечные группы имеют ровно один конец.

Примечания

^ Однако, как отмечают Крон и Мёллер (2008) , концы графов уже рассматривались Фрейденталем (1945) .
^ Статус (1964) .
^ Например, это форма отношения эквивалентности, используемая Дистелем и Кюном (2003) .
^ Jump up to: Перейти обратно: ^а ^б Номенклатура убежища и тот факт, что два луча определяют одно и то же убежище тогда и только тогда, когда они эквивалентны, принадлежат Робертсону, Сеймуру и Томасу (1991) . Дистель и Кюн (2003) доказали, что каждое убежище происходит от конца, дополняя биекцию между концами и убежищами, используя другую номенклатуру, в которой они называли убежища «направлениями».
^ Доказательство Дистеля и Кюн (2003) того, что каждое убежище может быть определено лучом, нетривиально и включает два случая. Если набор $S=\bigcap _{X}\left(\beta (X)\cup X\right)$ (где $X$ пробегает все конечные множества вершин) бесконечно, то существует луч, проходящий через бесконечное число вершин $S$ , что обязательно определяет $\beta$ . С другой стороны, если $S$ конечна, то Дистель и Кюн (2003) показывают, что в этом случае существует последовательность конечных множеств $X_{i}$ которые отделяют конец от всех точек, расстояние которых от произвольно выбранной начальной точки в $G\setminus S$ является $i$ . В этом случае убежище определяется любым лучом, за которым следует грабитель, использующий убежище, чтобы уйти от полиции, приземлившейся в установленном месте. $X_{i}$ в раунде $i$ игры «преследование-уклонение».
^ Точнее, в исходной формулировке этого результата Халина (1964) , в которой концы определяются как классы эквивалентности лучей, каждый класс эквивалентности лучей $G$ содержит уникальный непустой класс эквивалентности лучей остовного леса. Что касается убежищ, то существует взаимно однозначное соответствие убежищ порядка. $\aleph _{0}$ между $G$ и его связующее дерево $T$ для чего $\beta _{T}(X)\subset \beta _{G}(X)$ для каждого конечного множества $X$ и каждая соответствующая пара убежищ $\beta _{T}$ и $\beta _{G}$ .
^ Сеймур и Томас (1991) ; Томассен (1992) ; Дистель (1992) .
^ Дистель и Кюн (2003) .
^ Дистель (2006) .
^ Халин (1965) ; Дистель (2004) .
^ Столлингс ( 1968 , 1971 ).

Ссылки

Дистель, Рейнхард (1992), «Конечная структура графа: последние результаты и открытые проблемы», Discrete Mathematics , 100 (1–3): 313–327, doi : 10.1016/0012-365X(92)90650-5 , МР 1172358
Дистель, Рейнхард (2004), «Краткое доказательство теоремы Халина о сетке», Статьи математического семинара Гамбургского университета , 74 : 237–242, doi : 10.1007/BF02941538 , MR 2112834 , S2CID 124603912
Дистель, Рейнхард (2006), «Конечные пространства и остовные деревья», Журнал комбинаторной теории , серия B, 96 (6): 846–854, doi : 10.1016/j.jctb.2006.02.010 , MR 2274079
Дистель, Рейнхард; Кюн, Даниэла (2003), «Теоретико-графовые и топологические концы графов», Журнал комбинаторной теории , серия B, 87 (1): 197–206, doi : 10.1016/S0095-8956(02)00034-5 , MR 1967888
Фрейденталь, Ганс (1931), «О концах топологических пространств и групп», Mathematical Journal , 33 : 692–713, doi : 10.1007/BF01174375 , S2CID 120965216
Фрейденталь, Ганс (1945), «О концах дискретных пространств и групп», Commentarii Mathematici Helvetici , 17 : 1–38, doi : 10.1007/bf02566233 , MR 0012214 , S2CID 125014683
Халин, Рудольф (1964), «О бесконечных путях в графах», Mathematical Annals , 157 (2): 125–137, doi : 10.1007/bf01362670 , hdl : 10338.dmlcz/102294 , MR 0170340 , S2CID 122125458
Халин, Рудольф (1965), «О максимальном количестве странных бесконечных путей в графах», Mathematical News , 30 (1–2): 63–85, doi : 10.1002/mana.19650300106 , MR 0190031
Крон, Бернхард; Мёллер, Рёнвальдур Г. (2008), «Метрические концы, слои и автоморфизмы графов» (PDF) , Mathematical News , 281 (1): 62–74, doi : 10.1002/mana.200510587 , MR 2376468 , S2CID 18378856
Мохар, Боян (1991), «Некоторые отношения между аналитическими и геометрическими свойствами бесконечных графов» (PDF) , Discrete Mathematics , 95 (1–3): 193–219, doi : 10.1016/0012-365X(91)90337-2 , МР 1141939
Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (1991), «Исключая бесконечные миноры», Discrete Mathematics , 95 (1–3): 303–319, doi : 10.1016/0012-365X(91)90343-Z , MR 1141945
Сеймур, Пол ; Томас, Робин (1991), «Контрольный пример связующего дерева», Proceedings of the American Mathematical Society , 113 (4): 1163–1171, doi : 10.2307/2048796 , JSTOR 2048796 , MR 1045600
Столлингс, Джон Р. (1968), «О группах без кручения с бесконечно многими концами», Annals of Mathematics , Second Series, 88 (2): 312–334, doi : 10.2307/1970577 , JSTOR 1970577 , MR 0228573
Столлингс, Джон Р. (1971), Теория групп и трехмерные многообразия: Лекция Джеймса К. Уитмора по математике, прочитанная в Йельском университете, 1969 , Йельские математические монографии, том. 4, Нью-Хейвен, Коннектикут: Издательство Йельского университета, MR 0415622
Томассен, Карстен (1992), «Бесконечные связные графы без сохраняющих концы остовных деревьев», Журнал комбинаторной теории , серия B, 54 (2): 322–324, doi : 10.1016/0095-8956(92)90059-7 , HDL : 10338.dmlcz/127625 , MR 1152455

[1] Однако, как отмечают Крон и Мёллер (2008) , концы графов уже рассматривались Фрейденталем (1945) .

[FOOTNOTEHalin1964-2] Статус (1964) .

[3] Например, это форма отношения эквивалентности, используемая Дистелем и Кюном (2003) .

[haven-end-4] Jump up to: Перейти обратно: ^а ^б Номенклатура убежища и тот факт, что два луча определяют одно и то же убежище тогда и только тогда, когда они эквивалентны, принадлежат Робертсону, Сеймуру и Томасу (1991) . Дистель и Кюн (2003) доказали, что каждое убежище происходит от конца, дополняя биекцию между концами и убежищами, используя другую номенклатуру, в которой они называли убежища «направлениями».

[5] Доказательство Дистеля и Кюн (2003) того, что каждое убежище может быть определено лучом, нетривиально и включает два случая. Если набор $S=\bigcap _{X}\left(\beta (X)\cup X\right)$ (где $X$ пробегает все конечные множества вершин) бесконечно, то существует луч, проходящий через бесконечное число вершин $S$ , что обязательно определяет $\beta$ . С другой стороны, если $S$ конечна, то Дистель и Кюн (2003) показывают, что в этом случае существует последовательность конечных множеств $X_{i}$ которые отделяют конец от всех точек, расстояние которых от произвольно выбранной начальной точки в $G\setminus S$ является $i$ . В этом случае убежище определяется любым лучом, за которым следует грабитель, использующий убежище, чтобы уйти от полиции, приземлившейся в установленном месте. $X_{i}$ в раунде $i$ игры «преследование-уклонение».

[6] Точнее, в исходной формулировке этого результата Халина (1964) , в которой концы определяются как классы эквивалентности лучей, каждый класс эквивалентности лучей $G$ содержит уникальный непустой класс эквивалентности лучей остовного леса. Что касается убежищ, то существует взаимно однозначное соответствие убежищ порядка. $\aleph _{0}$ между $G$ и его связующее дерево $T$ для чего $\beta _{T}(X)\subset \beta _{G}(X)$ для каждого конечного множества $X$ и каждая соответствующая пара убежищ $\beta _{T}$ и $\beta _{G}$ .

[7] Сеймур и Томас (1991) ; Томассен (1992) ; Дистель (1992) .

[8] Дистель и Кюн (2003) .

[FOOTNOTEDiestel2006-9] Дистель (2006) .

[10] Халин (1965) ; Дистель (2004) .

[11] Столлингс ( 1968 , 1971 ).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]