В теории графов семейство Петерсена - это набор из семи неориентированных графов, который включает граф Петерсена и полный граф K 6 . Семья Петерсена названа в честь датского математика Юлиуса Петерсена , тезки графа Петерсена.
Любой из графов семейства Петерсена может быть преобразован в любой другой граф этого семейства с помощью преобразований Δ-Y или Y-Δ , операций, в которых треугольник заменяется вершиной третьей степени или наоборот. Эти семь графов образуют запрещенные миноры для безвыходных встраиваемых графов , графов, которые могут быть встроены в трехмерное пространство таким образом, что никакие два цикла в графе не связаны . [1] Они также входят в число запрещенных миноров для YΔY-приводимых графов . [2] [3]
Определение [ править ]
Форма преобразований Δ-Y и Y-Δ, используемых для определения семейства Петерсена, следующая:
- Если граф G содержит вершину v с ровно тремя соседями, то преобразование Y-Δ графа G в v - это граф, образованный удалением v из G и добавлением ребер между каждой парой из трех его соседей.
- Если граф H содержит треугольник uvw , то Δ-Y преобразование H в uvw - это граф, образованный удалением ребер uv , vw и uw из H и добавлением новой вершины, соединенной со всеми тремя из u , v и w .
Эти преобразования называются так из-за формы Δ треугольника в графе и формы Y вершины третьей степени. Хотя эти операции в принципе могут привести к созданию мультиграфов , в семье Петерсенов этого не происходит. Поскольку эти операции сохраняют количество ребер в графе, существует только конечное число графов или мультиграфов, которые могут быть сформированы из одного начального графа G комбинациями преобразований Δ-Y и Y-Δ.
Тогда семейство Петерсена состоит из каждого графа, который может быть получен из графа Петерсена комбинацией преобразований Δ-Y и Y-Δ. В семействе семь графов, включая полный граф K 6 на шести вершинах, граф с восемью вершинами, образованный удалением одного ребра из полного двудольного графа K 4,4 , и полный трехдольный граф с семью вершинами K 3, 3,1 .
Запрещенные несовершеннолетние [ править ]
Минор графа G представляет другой график формируется из G стягивания и удаления ребер. Как теорема Робертсон-Сеймура показывает, многие важные семейства графов можно характеризовать конечное множество запрещенных несовершеннолетних : например, согласно теореме Вагнера , то плоские графы в точности графика , которые не имеют ни полного граф K 5 , ни полных двудольный граф K 3,3 как миноры.
Нил Робертсон , Пол Сеймур и Робин Томас использовали семейство Петерсена как часть аналогичной характеристики вложения графов без звеньев , вложений данного графа в евклидово пространство таким образом, что каждый цикл в графе является границей диска, который не пересекается ни одной другой частью графика. [1] Хорст Сакс ранее изучал такие вложения, показал, что семь графов семейства Петерсена не имеют таких вложений, и поставил вопрос о характеризации беззвучно вложимых графов запрещенными подграфами. [4]Робертсон и др. решил вопрос Сакса, показав, что несвязанные встраиваемые графы - это именно те графы, в которых нет члена семьи Петерсена в качестве несовершеннолетнего.
Семья Петерсена также формирует запрещенные миноры для другого семейства графов, YΔY-приводимых графов. Связный граф является YΔY-сводимым, если его можно свести к одной вершине с помощью последовательности шагов, каждый из которых представляет собой преобразование Δ-Y или Y-Δ, удаление петли или множественной смежности, удаление вершина с одним соседом и замена вершины степени два и двух ее соседних ребер на одно ребро. Например, полный граф K 4 может быть уменьшен до одной вершины с помощью преобразования Y-Δ, которое превращает его в треугольник с удвоенными ребрами, удаления трех удвоенных ребер, преобразования Δ-Y, превращающего его в клешню K 1,3, и удаление трех вершин когтя первой степени. Каждый из графов семейства Петерсена образует минимальный запрещенный минор для семейства YΔY-приводимых графов. [2] Тем не менее, Нил Робертсон представил пример вершинного графа (беззвенного встраиваемого графа, образованного добавлением одной вершины к плоскому графу), который не является YΔY-сводимым, показывая, что Y∆Y-сводимые графы образуют надлежащий подкласс бессвязных вложенные графы и имеют дополнительные запрещенные миноры. [2] Фактически, как показал Ямин Ю, существует не менее 68 897 913 652 запрещенных миноров для YΔY-приводимых графов, помимо семи из семейства Петерсена. [3]
Ссылки [ править ]
- ^ a b Робертсон, Нил ; Сеймур, PD ; Томас, Робин (1993), "Бесконечные вложения графов в 3-пространство", Бюллетень Американского математического общества , 28 (1): 84–89, arXiv : math / 9301216 , doi : 10.1090 / S0273-0979-1993- 00335-5 , Руководство по ремонту 1164063.
- ^ a b c Truemper, Klaus (1992), Matroid Decomposition (PDF) , Academic Press, стр. 100–101. .
- ^ a b Yu, Yaming (2006), "Более запрещенные несовершеннолетние для сводимости звезда-дельта-звезда" (PDF) , Электронный журнал комбинаторики , 13 (1): # R7 .
- ^ Сакс, Хорст (1983), "О пространственном аналоге теоремы Куратовского о плоских графах - открытая проблема", в Horowiecki, M .; Кеннеди, JW; Сисло, М.М. (ред.), Теория графов: Материалы конференции, состоявшейся в Лагуве, Польша, 10–13 февраля 1981 г. , Лекционные заметки по математике, 1018 , Springer-Verlag, стр. 230–241, doi : 10.1007 / BFb0071633.
