Петерсеново семейство графов

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

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

Любой из графов семейства Петерсена может быть преобразован в любой другой граф семейства Δ-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.

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

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

Минор графа 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:10.1090/S0273-0979-1993-00335-5. — arXiv:math/9301216.
• 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:10.1007/BFb0071633.
• 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.