Главная
Новости
Строительство
Ремонт
Дизайн и интерьер




06.03.2021


06.03.2021


06.03.2021


06.03.2021


06.03.2021





Яндекс.Метрика





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

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

04.02.2021

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

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

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

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

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

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