В теории графов семейство Петерсена — это набор из семи неориентированных графов , включающий граф Петерсена и полный граф K 6. Семейство Петерсена названо в честь датского математика Юлиуса Петерсена , в честь которого назван граф Петерсена.
Любой из графов в семействе Петерсена может быть преобразован в любой другой граф в семействе с помощью YΔ- и ΔY-преобразований , операций, в которых треугольник заменяется вершиной степени три или наоборот. Эти семь графов образуют запрещенные миноры для графов, в которых можно вложить графы без зацепления , графы, которые можно вложить в трехмерное пространство таким образом, что никакие два цикла в графе не будут связаны . [1] Они также входят в число запрещенных миноров для графов, в которых можно свести YΔY . [2] [3]
Форма YΔ- и ΔY-преобразований, используемая для определения семейства Петерсена, выглядит следующим образом:
Эти преобразования так называются из-за Δ-формы треугольника в графе и 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]