Семья Петерсен - Petersen family

Семья Петерсен. K6 находится вверху рисунка, а график Петерсена - внизу. Синие ссылки указывают на преобразования Δ-Y или Y-Δ между графами в семействе.

В теория графов, то Семья Петерсен это набор из семи неориентированные графы это включает Граф Петерсена и полный график K6. Семья Петерсен названа в честь датского математика. Юлиус Петерсен, тезка графа Петерсена.

Любой из графов семейства Петерсена может быть преобразован в любой другой граф семейства с помощью Δ-Y или Y-Δ преобразовывает, операции, в которых треугольник заменяется вершиной третьей степени или наоборот. Эти семь графиков образуют запрещенные несовершеннолетние для бесконечно встраиваемые графы, графы, которые могут быть вложены в трехмерное пространство таким образом, что никакие два цикла в графе не связаны.[1] Они также входят в число запрещенных несовершеннолетних для YΔY-приводимые графы.[2][3]

Определение

Форма Δ-Y и Y-Δ преобразовывает используется для определения семьи Петерсен следующим образом:

  • Если график г содержит вершину v ровно с тремя соседями, то Y-Δ преобразование г в v это граф, образованный удалением v от г и добавление ребер между каждой парой из трех его соседей.
  • Если график ЧАС содержит треугольник uvw, то Δ-Y преобразование ЧАС в uvw это граф, образованный удалением ребер УФ, vw, и уф от ЧАС и добавив новую вершину, соединенную со всеми тремя ты, v, и ш.

Эти преобразования называются так из-за формы Δ треугольника в графе и формы Y вершины третьей степени. Хотя эти операции в принципе могут привести к мультиграфы, этого не происходит в семье Петерсен. Поскольку эти операции сохраняют количество ребер в графе, существует только конечное число графов или мультиграфов, которые могут быть сформированы из одного начального графа. г комбинацией преобразований Δ-Y и Y-Δ.

Семья Петерсена состоит из каждого графа, который может быть получен из Граф Петерсена комбинацией преобразований Δ-Y и Y-Δ. Всего в семействе семь графиков, включая полный график K6 на шести вершинах граф с восемью вершинами, образованный удалением единственного ребра из полный двудольный граф K4,4, а семивершинный полный трехдольный граф K3,3,1.

Запрещенные несовершеннолетние

Неприводимый вершинный граф Робертсона, показывающий, что YΔY-приводимые графы имеют дополнительные запрещенные миноры помимо тех, что входят в семейство Петерсена.

А незначительный графа г это еще один граф, сформированный из г сокращая и удаляя края. Поскольку Теорема Робертсона – Сеймура показывает, что многие важные семейства графов можно охарактеризовать конечным набором запрещенные несовершеннолетние: например, согласно Теорема Вагнера, то планарные графы - это именно те графы, которые не имеют полный график K5 ни полный двудольный граф K3,3 как несовершеннолетние.

Нил Робертсон, Пол Сеймур, и Робин Томас использовали семью Петерсена как часть аналогичной характеристики вложения без ссылок графов, вложения данного графа в Евклидово пространство таким образом, чтобы каждый цикл в графе - граница диска, которую не пересекает никакая другая часть графа.[1] Хорст Сакс ранее изучал такие вложения, показал, что семь графов семейства Петерсена не имеют таких вложений, и поставил вопрос о характеристике беззвучно вложимых графов запрещенными подграфами.[4] Робертсон и др. решил вопрос Сакса, показав, что несвязанные встраиваемые графы - это именно те графы, в которых нет члена семьи Петерсена в качестве несовершеннолетнего.

Семья Петерсена также формирует некоторые из запрещенных миноров для другого семейства графов, YΔY-приводимых графов. Связный граф является YΔY-сводимым, если его можно свести к одной вершине с помощью последовательности шагов, каждый из которых представляет собой преобразование Δ-Y или Y-Δ, удаление петли или множественной смежности, удаление вершина с одним соседом и замена вершины степени два и двух ее соседних ребер одним ребром. Например, полный график K4 может быть уменьшен до единственной вершины с помощью преобразования Y-Δ, которое превращает его в треугольник с удвоенными ребрами, удаления трех удвоенных ребер, преобразования Δ-Y, превращающего его в коготь K1,3, и удаление трех вершин когтя первой степени. Каждый из графов семейства Петерсена образует минимальный запрещенный минор для семейства YΔY-приводимых графов.[2] Однако Нил Робертсон привел пример вершина графика (беззвучный встраиваемый граф, образованный добавлением одной вершины к планарному графу), который не является YΔY-сводимым, показывая, что YΔY-сводимые графы образуют надлежащий подкласс беззвучных встраиваемых графов и имеют дополнительные запрещенные миноры.[2] Фактически, как показал Ямин Ю, существует не менее 68 897 913 652 запрещенных миноров для YΔY-приводимых графов помимо семи из семейства Петерсенов.[3]

использованная литература

  1. ^ а б Робертсон, Нил; Сеймур, П. Д.; Томас, Робин (1993), "Бесконечные вложения графов в 3-пространство", Бюллетень Американского математического общества, 28 (1): 84–89, arXiv:математика / 9301216, Дои:10.1090 / S0273-0979-1993-00335-5, Г-Н  1164063.
  2. ^ а б c Трумпер, Клаус (1992), Разложение Matroid (PDF), Academic Press, стр. 100–101..
  3. ^ а б Ю, Ямин (2006), "Больше запрещенных несовершеннолетних для сводимости звезда-дельта-звезда" (PDF), Электронный журнал комбинаторики, 13 (1): # R7.
  4. ^ Сакс, Хорст (1983), «О пространственном аналоге теоремы Куратовского о плоских графах - открытая проблема», в Horowiecki, M .; Kennedy, J. W .; Сысло, М. М. (ред.), Теория графов: Материалы конференции, состоявшейся в Лагуве, Польша, 10–13 февраля 1981 г., Конспект лекций по математике, 1018, Springer-Verlag, стр. 230–241, Дои:10.1007 / BFb0071633.