Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

Определение и характеристика [ править ]

Концы графов были определены Рудольфом Халиным  ( 1964 ) в терминах классов эквивалентности бесконечных путей. [1] луч в бесконечном графе является полубесконечный простым путем ; то есть это бесконечная последовательность вершин v 0 , v 1 , v 2 , ..., в которой каждая вершина появляется не более одного раза в последовательности, и каждые две последовательные вершины в последовательности являются двумя конечными точками ребра в график. Согласно определению Халина, два луча r 0 и r 1 эквивалентны, если существует другой луч r 2.(не обязательно отличный от любого из первых двух лучей), который содержит бесконечно много вершин в каждом из r 0 и r 1 . Это отношение эквивалентности : каждый луч эквивалентен самому себе, определение симметрично относительно порядка двух лучей, и можно показать, что оно транзитивно . Следовательно, он разбивает множество всех лучей на классы эквивалентности , и Халин определил конец как один из этих классов эквивалентности.

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

Концы также имеют более конкретную характеристику в терминах убежищ , функций, описывающих стратегию уклонения для преследования-уклонения от игры на графе G . [3] В игре в вопросе, грабитель пытается уклониться от набора полицейских при переходе от вершины к вершине вдоль ребер G . У полиции есть вертолеты, поэтому ей не нужно следить за краями; однако грабитель видит приближающуюся полицию и может выбрать, куда двигаться дальше, прежде чем вертолеты приземлятся. Убежище - это функция β, которая отображает каждый набор X полицейских участков на один из связанных компонентов подграфа, образованного удалением X; грабитель может уклониться от полиции, перемещаясь в каждом раунде игры к вершине внутри этого компонента. Убежища должны удовлетворять свойству согласованности (соответствующему требованию, что грабитель не может перемещаться через вершины, на которые уже приземлилась полиция): если X является подмножеством Y , и оба X и Y являются допустимыми наборами местоположений для данного набора полиции. , то β ( X ) должно быть надмножеством β ( Y ). Убежище имеет порядок k, если набор полицейских участков, для которых он предоставляет стратегию побега, включает в себя все подмножества из менее чем k вершин в графе; в частности, он имеет порядок ℵ 0если оно отображает каждое конечное подмножество X вершин к компоненту G  \  X . Каждому лучу в G соответствует гавань порядка ℵ 0 , а именно функция β, которая отображает каждое конечное множество X в единственную компоненту G  \  X , содержащую бесконечно много вершин луча. И наоборот, каждое убежище порядка ℵ 0 можно определить таким образом с помощью луча. [4] Два луча эквивалентны тогда и только тогда, когда они определяют одно и то же убежище, поэтому концы графа находятся во взаимно однозначном соответствии с его убежищами порядка ℵ 0 .

Примеры [ править ]

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

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

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

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

Связь с топологическими целями [ править ]

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

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

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

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

Если граф G связен и локально конечен, то он имеет компактное покрытие, в котором множество κ i - это множество вершин, находящихся на расстоянии не более i от некоторой произвольно выбранной начальной вершины. В этом случае любая гавань β определяет конец топологического пространства, в котором . И наоборот, если это конец топологического пространства, определенного из G , он определяет убежище, в котором β ( X ) - компонент, содержащий U i , где i - любое число, достаточно большое, чтобы κ i содержало X. Таким образом, для связных и локально конечных графов топологические концы находятся во взаимно однозначном соответствии с теоретико-графовыми концами. [7]

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

Особые виды концов [ править ]

Бесплатные концы [ править ]

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

Толстые концы [ править ]

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

Особые виды графиков [ править ]

Симметричные и почти симметричные графы [ править ]

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

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

Графики Кэли [ править ]

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

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

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

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

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

Заметки [ править ]

  1. ^ Однако, как указывают Крон и Мёллер (2008) , концы графов уже рассматривались Фройденталем (1945) .
  2. ^ Например, это форма отношения эквивалентности, используемая Diestel & Kühn (2003) .
  3. ^ Номенклатура гавани и тот факт, что два луча определяют одну и ту же гавань, если и только если они эквивалентны, принадлежит Робертсону, Сеймуру и Томасу (1991) . Diestel & Kühn (2003) доказали, что каждое убежище исходит из конца, завершая взаимно однозначное соответствие между концами и убежищами, используя другую терминологию, в которой они назвали убежища «направлениями».
  4. ^ Доказательство Diestel & Kühn (2003) того, что каждое убежище может быть определено лучом, нетривиально и включает два случая. Если множество(где X пробегает все конечные множества вершин) бесконечно, то существует луч, проходящий через бесконечно много вершин S , который обязательно определяет β. С другой стороны, если S конечно, то Diestel & Kühn (2003) показывают, что в этом случае существует последовательность конечных множеств X i, которые отделяют конец от всех точек, расстояние которых от произвольно выбранной начальной точки в G  \  S это я. В этом случае убежище определяется любым лучом, за которым следует грабитель, использующий убежище, чтобы убежать от полиции, которая приземляется в множестве X i в i- м раунде игры «преследование-уклонение».
  5. ^ Точнее, в первоначальной формулировке этого результата Халином (1964), в которой концы определены как классы эквивалентности лучей, каждый класс эквивалентности лучей G содержит единственный непустой класс эквивалентности лучей остовного леса. С точки зрения гаваней, существует взаимно однозначное соответствие одному из убежищ порядка ℵ 0 между G и его остовного дерева T , для которыхдля каждого конечного множества X и каждой соответствующей пары убежищ & beta ; T и & beta ; G .
  6. ↑ Сеймур и Томас (1991) ; Томассен (1992) ; Дистель (1992) .
  7. ^ Diestel & Кюн (2003) .
  8. ^ Дистель (2006) .
  9. ↑ Халин (1965) ; Дистель (2004) .
  10. Перейти ↑ Stallings ( 1968 , 1971 ).

Ссылки [ править ]

  • Diestel, Райнхард (1992), "Конец структура графа: последние результаты и открытые проблемы", дискретной математики , 100 (1-3): 313-327, DOI : 10.1016 / 0012-365X (92) 90650-5 , Руководство по ремонту  1172358.
  • Diestel Рейнхард (2004), "Короткое доказательство теоремы Халин в сетке", Abhandlungen AUS DEM Mathematischen Семинаре дер Universität Hamburg , 74 : 237-242, DOI : 10.1007 / BF02941538 , MR  2112834.
  • Diestel Рейнхард (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), «Über die Enden topologischer Räume und Gruppen», Mathematische Zeitschrift , 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), "Убер unendliche Wege в графене", Mathematische Annalen , 157 (2): 125-137, DOI : 10.1007 / bf01362670 , ЛВП : 10338.dmlcz / 102294 , МР  0170340.
  • Халин, Рудольф (1965), "Убер умереть Maximalzahl fremder unendlicher Wege в графена", Mathematische Nachrichten , 30 (1-2): 63-85, DOI : 10.1002 / mana.19650300106 , МР  0190031.
  • Крон, Бернхард; Мёллер, Rögnvaldur Г. (2008), "Метрические концы, волокна и автоморфизмы графов" (PDF) , Mathematische Nachrichten , 281 (1): 62-74, DOI : 10.1002 / mana.200510587 , MR  2376468.
  • Mohar, Боян (1991), "Некоторые соотношения между аналитическими и геометрическими свойствами бесконечных графов" (PDF) , дискретная математика , 95 (1-3): 193-219, DOI : 10.1016 / 0012-365X (91) 90337-2 , Руководство по ремонту  1141939.
  • Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (1991), " За исключением бесконечных несовершеннолетних", дискретная математика , 95 (1-3): 303-319, DOI : 10.1016 / 0012-365X (91) 90343-Z , МР  1141945.
  • Сеймур, Пол ; Томас, Робин (1991), "Конец-верный остовного дерева контрпример", Труды Американского математического общества , 113 (4): 1163-1171, DOI : 10,2307 / 2048796 , JSTOR  2048796 , MR  1045600.
  • Сталлингс, Джон Р. (1968), "О группах без кручения с бесконечным числом концов", Анналы математики , второй серии 88 (2): 312-334, DOI : 10,2307 / 1970577 , JSTOR  1970577 , MR  0228573.
  • Столлингс, Джон Р. (1971), Теория групп и трехмерные многообразия: Лекция Джеймса К. Уиттемора по математике, прочитанная в Йельском университете, 1969 , Йельские математические монографии, 4 , Нью-Хейвен, штат Коннектикут: Yale University Press, MR  0415622.
  • Томассен, Карстен (1992), «Бесконечные связные графы без остовных деревьев, сохраняющих конец», Журнал комбинаторной теории , серия B, 54 (2): 322–324, DOI : 10.1016 / 0095-8956 (92) 90059-7 , ЛВП : 10338.dmlcz / 127625 , МР  1152455.