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

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

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

Любой из графов семейства Петерсена может быть преобразован в любой другой граф семейства Δ-Y или Y-Δ преобразованиями, операциями, при которых треугольник заменяется вершиной степени 3, или наоборот. Эти семь графов образуют запрещённые миноры для незацепленно вложимых графов, графов, которые могут быть вложены в трёхмерное пространство таким образом, что никакие два цикла не образуют зацепление (в смысле теории узлов)[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-Δ. В семействе семь графов, и в него входят полный граф K6 с шестью вершинами, граф с восемью вершинами, образованный удалением одного ребра из полного двудольного графа K4,4, и полный трёхдольный граф с семью вершинами K3,3,1.

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

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

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

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

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

Примечания

  1. ↑ 1 2 Robertson, Seymour, Thomas, 1993, с. 84–89.
  2. ↑ 1 2 3 Truemper, 1992, с. 100–101.
  3. ↑ 1 2 Yu, 2006, с. #R7.
  4. ↑ Sachs, 1983, с. 230–241.

Литература

  • 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.