Для установки нажмите кнопочку Установить расширение. И это всё.

Исходный код расширения WIKI 2 регулярно проверяется специалистами Mozilla Foundation, Google и Apple. Вы также можете это сделать в любой момент.

4,5
Келли Слэйтон
Мои поздравления с отличным проектом... что за великолепная идея!
Александр Григорьевский
Я использую WIKI 2 каждый день
и почти забыл как выглядит оригинальная Википедия.
Статистика
На русском, статей
Улучшено за 24 ч.
Добавлено за 24 ч.
Альтернативы
Недавние
Show all languages
Что мы делаем. Каждая страница проходит через несколько сотен совершенствующих техник. Совершенно та же Википедия. Только лучше.
.
Лео
Ньютон
Яркие
Мягкие

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

Из Википедии — свободной энциклопедии

Петерсеново семейство. 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.

Нейл Робертсон[en], Пол Сеймур и Робин Томас использовали петерсеново семейство как часть похожей характеризации допускающих незацепленное вложение графов, то есть графов, которые можно вложить в евклидово пространство таким образом, что любой цикл в графе является границей (топологического) диска, не пересекаемого никакой другой частью графа[1]. Сакс Хорст[en] изучал до этого такие вложения и показал, что семь графов петерсенова семейства не имеют таких вложений, и поставил вопрос характеризации графов с незацеплённым вложением путём перечисления запрещённых подграфов[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.
Эта страница в последний раз была отредактирована 27 июля 2019 в 14:07.
Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.
Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License. Нетекстовые медиаданные доступны под собственными лицензиями. Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. WIKI 2 является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).