Семья Петерсен
В теории графов семейство Петерсена собой набор из семи неориентированных графов , включающий граф Петерсена и полный граф K6 представляет . Семья Петерсенов названа в честь датского математика Юлиуса Петерсена , тезки графа Петерсена.
Любой из графов семейства Петерсена можно преобразовать в любой другой граф семейства с помощью 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 — это другой граф, образованный из путем сжатия и удаления ребер. Как показывает теорема Робертсона-Сеймура , многие важные семейства графов могут характеризоваться конечным набором запрещенных миноров : например, согласно теореме Вагнера , планарные графы — это именно те графы, которые не имеют ни полного графа K5 , ни полного графа. двудольный граф 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]
Ссылки
[ редактировать ]- ^ Jump up to: Перейти обратно: а б Робертсон, Нил ; Сеймур, Полиция ; Томас, Робин (1993), «Бесзвенные вложения графов в трехмерное пространство», Бюллетень Американского математического общества , 28 (1): 84–89, arXiv : math/9301216 , doi : 10.1090/S0273-0979-1993- 00335-5 , МР 1164063 .
- ^ Jump up to: Перейти обратно: а б с Трумпер, Клаус (1992), Разложение матроида (PDF) , Academic Press, стр. 100–101 .
- ^ Jump up to: Перейти обратно: а б Ю, Яминг (2006), «Более запрещенные миноры для сводимости звезда-дельта-звезда» (PDF) , Электронный журнал комбинаторики , 13 (1): #R7 .
- ^ Сакс, Хорст (1983), «О пространственном аналоге теоремы Куратовского о плоских графах - открытая проблема», в Горовецкий, М.; Кеннеди, JW; Сысло М.М. (ред.), Теория графов: материалы конференции, состоявшейся в Лагуве, Польша, 10–13 февраля 1981 г. , Конспекты лекций по математике, том. 1018, Springer-Verlag, стр. 230–241, doi : 10.1007/BFb0071633 .