В теории графов петерсеново семейство графов — это набор из семи неориентированных графов , включающий граф Петерсена и полный граф K ₆ . Петерсеново семейство названо именем датского математика Юлиуса Петерсена , поскольку в набор входит граф Петерсена.

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

Определение

Δ-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 ₆ с шестью вершинами, граф с восемью вершинами, образованный удалением одного ребра из полного двудольного графа K _4,4 , и полный трёхдольный граф с семью вершинами K _3,3,1 .

Запрещённые миноры

Минор графа G — это другой граф, образованный из графа G стягиванием и удалением рёбер. Как показывает теорема Робертсона — Сеймура , многие важные семейства графов могут быть охарактеризованы конечным набором запрещённых миноров . Например, согласно теореме Вагнера планарные графы — это в точности графы, которые не содержат в качестве миноров ни полный граф K ₅ , ни полный двудольный граф K _3,3 .

, Пол Сеймур и Робин Томас использовали петерсеново семейство как часть похожей характеризации допускающих незацепленное вложение графов, то есть графов, которые можно вложить в евклидово пространство таким образом, что любой цикл в графе является границей (топологического) диска, не пересекаемого никакой другой частью графа . изучал до этого такие вложения и показал, что семь графов петерсенова семейства не имеют таких вложений, и поставил вопрос характеризации графов с незацеплённым вложением путём перечисления запрещённых подграфов . Робертсон и др. разрешили вопрос Сакса, показав, что графы, вложимые без зацеплений — это в точности те графы, которые не имеют членов петерсенова семейства в качестве миноров.

Графы семейства Петерсена входят в запрещённые миноры другого семейства графов, YΔY-приводимые графы. Связный граф является YΔY-приводимым, если он может быть преобразован к единственной вершине последовательностью шагов, каждый из которых является преобразованием Δ-Y или Y-Δ, удалением петли или многократного ребра, удалением вершины с единственным соседом и заменой вершины степени два и двух смежных рёбер одним ребром. Например, полный граф K ₄ может быть сведён к одной вершине с помощью преобразования Y-Δ, которое превращает его в треугольник с двойными рёбрами. После удаления трёх двойных рёбер, преобразования Δ-Y, преобразующего треугольник в клешню (три ребра с одной общей вершиной) K _1,3 , и удаления висячих вершин клешни граф превращается в вершину. Каждый из графов семейства Петерсена образует минимальный запрещённый минор для семейства YΔY-приводимых графов . Однако Нейл Робертсон даёт пример верхушечного графа (граф, вложимый без зацеплений, образованный добавлением одной вершины к планарному графу), который не является YΔY-приводимым. Это показывает, что YΔY-приводимые графы образуют собственный подкласс вложимых без зацеплений графов, но, кроме графов семейства Петерсена, имеют дополнительные запрещённые миноры . Фактически, как показал Яминг Ю (Yaming Yu), существует по меньшей мере 68 897 913 652 запрещённых минора для YΔY-приводимых графов, кроме семи графов семейства Петерсена .

Примечания

Литература

• Neil Robertson, P. D. Seymour, Robin Thomas. Linkless embeddings of graphs in 3-space // Bulletin of the American Mathematical Society. — 1993. — Т. 28 , вып. 1 . — С. 84–89 . — doi : . — arXiv : .
• Horst Sachs. Graph Theory: Proceedings of a Conference held in Łagów, Poland, February 10–13, 1981 / M. Horowiecki, J. W. Kennedy, M. M. Sysło. — Springer-Verlag, 1983. — Т. 1018. — С. 230–241. — (Lecture Notes in Mathematics). — ISBN 0-387-12687-2 , 3-540-12687-2. — doi : .
• Klaus Truemper. Matroid Decomposition. — Academic Press, 1992. — С. 100–101. (Revised edition 1998)
• Yaming Yu. More forbidden minors for wye-delta-wye reducibility // Electronic Journal of Combinatorics. — 2006. — Т. 13 , вып. 1 . — С. #R7 .