Критерий планарности Мак-Лейна - Википедия - Mac Lanes planarity criterion

В теория графов, Критерий планарности Мак-Лейна это характеристика планарные графы с точки зрения их велосипедные пространства, названный в честь Saunders Mac Lane, опубликовавший его в 1937 году. В нем говорится, что конечный неориентированный граф является плоским тогда и только тогда, когда пространство циклов графа (взятого по модулю 2) имеет основа цикла в котором каждое ребро графа участвует не более чем в двух базисных векторах.

Заявление

Для любого цикла c в графике граммможно сформировать м-мерный вектор 0-1, имеющий 1 в координатах, соответствующих ребрам в c и 0 в остальных координатах. Велосипедное пространство C(грамм) графа - векторное пространство, образованное всеми возможными линейными комбинациями векторов, сформированных таким образом. В характеристике Мак Лейна C(грамм) векторное пространство над конечное поле GF (2) с двумя элементами; то есть в этом векторном пространстве векторы складываются покоординатно по модулю два. А 2-основа из грамм является основой C(грамм) со свойством, что для каждого ребра е в грамм, не более двух базисных векторов имеют ненулевые координаты в положении, соответствующем е. Затем, говоря более формально, характеристика Мак Лейна состоит в том, что планарные графы - это именно те графы, которые имеют 2-базис.

Существование 2-базиса у плоских графов

Одно направление характеризации утверждает, что каждый планарный граф имеет 2-базис. Такой базис может быть найден как совокупность границ ограниченных граней плоского вложения данного графа грамм.

Если край - это мост грамм, он появляется дважды на границе одной грани и, следовательно, имеет нулевую координату в соответствующем векторе. Таким образом, единственные ребра с ненулевыми координатами - это те, которые разделяют две разные грани; эти ребра появляются либо один раз (если одна из граней является неограниченной), либо дважды в совокупности границ ограниченных граней. Осталось доказать, что эти циклы составляют основу. Один из способов доказать это по индукции. В качестве базового случая грамм является деревом, то у него нет ограниченных граней и C(грамм) нульмерна и имеет пустой базис. В противном случае удаление ребра с неограниченной грани грамм уменьшает как размерность пространства циклов, так и количество ограниченных граней на единицу, и следует индукция.

В качестве альтернативы можно использовать Формула Эйлера чтобы показать, что количество циклов в этом наборе равно звание цепи из грамм, который является размерностью пространства цикла. Каждое непустое подмножество циклов имеет векторную сумму, которая представляет границу объединения ограниченных граней в подмножестве, которое не может быть пустым (объединение включает по крайней мере одну ограниченную грань и исключает неограниченную грань, поэтому должны быть некоторые ребра, разделяющие их). Следовательно, не существует подмножества циклов, сумма векторов которых равна нулю, что означает, что все циклы являются линейно независимый. Как линейно независимый набор того же размера, что и размер пространства, этот набор циклов должен составлять основу.

Необходимость планарности при наличии 2-базиса

О'Нил (1973) предоставил следующий простой аргумент в пользу другого направления характеристики, основанный на Теорема Вагнера характеризуя планарные графы запрещенные несовершеннолетние. Как отмечает О'Нил, свойство иметь 2-базис сохраняется при граф миноры: если сжимать ребро, такое же сжатие может быть выполнено в базисных векторах, если удалить ребро, имеющее ненулевую координату в одном базисном векторе, то этот вектор может быть удален из базиса, и если один удаляет ребро который имеет ненулевую координату в двух базисных векторах, то эти два вектора могут быть заменены их суммой (по модулю два). Кроме того, если C(грамм) является базисом цикла для любого графа, то он должен покрывать некоторые ребра ровно один раз, иначе его сумма была бы равна нулю (невозможно для базиса), и поэтому C(грамм) может быть дополнен еще одним циклом, состоящим из этих однократно покрытых ребер, с сохранением того свойства, что каждое ребро покрывается не более чем дважды. полный график K5 не имеет 2-оснований: C(грамм) шестимерно, каждый нетривиальный вектор из C(грамм) имеет ненулевые координаты по крайней мере для трех ребер, и поэтому любой расширенный базис будет иметь по крайней мере 21 ненулевое значение, превышающее 20 ненулевых значений, которые были бы разрешены, если бы каждое из десяти ребер было ненулевым не более чем в двух базисных векторах. По аналогичным соображениям полный двудольный граф K3,3 не имеет 2-оснований: C(грамм) четырехмерно, и каждый нетривиальный вектор в C(грамм) имеет ненулевые координаты по крайней мере четырех ребер, поэтому любой расширенный базис будет иметь по крайней мере 20 ненулевых, превышающих 18 ненулевых, которые были бы разрешены, если бы каждое из девяти ребер было ненулевым не более чем в двух базисных векторах. Поскольку свойство иметь 2-базис является минорно-замкнутым и неверно для двух минорно-минимальных неплоских графов K5 и K3,3, это также неверно для любого другого неплоского графа.

Лефшец (1965) предоставил еще одно доказательство, основанное на алгебраическая топология. Он использует несколько иную формулировку критерия планарности, согласно которой граф является плоским тогда и только тогда, когда он имеет набор (не обязательно простых) циклов, покрывающих каждое ребро ровно дважды, так что единственное нетривиальное соотношение между этими циклами в C(грамм) в том, что их сумма равна нулю. Если это так, то при исключении любого из циклов получается базис, удовлетворяющий формулировке критерия Мак Лейна. Если планарный граф вложен в сферу, его циклы граней явно удовлетворяют свойству Лефшеца. И наоборот, как показывает Лефшец, всякий раз, когда граф грамм имеет набор циклов с этим свойством, они обязательно образуют циклы граней вложения графа на сферу.

Заявление

Ja'Ja 'и Саймон (1982) использовали критерий планарности Мак-Лейна как часть параллельный алгоритм для проверки планарности графа и поиска плоских вложений. Их алгоритм разбивает граф на трехкомпонентные компоненты, после которого происходит единственное (с точностью до выбора внешней грани) планарное вложение и циклами в 2-базисе можно считать все периферические циклы графа. Ja'Ja 'и Саймон начинают с фундаментального базиса цикла графа (базиса цикла, генерируемого из остовное дерево путем формирования цикла для каждой возможной комбинации пути в дереве и ребра за пределами дерева) и преобразовать его в 2-базис периферийных циклов. Эти циклы образуют грани плоского вложения данного графа.

Критерий планарности Мак Лейна позволяет легко подсчитать количество циклов ограниченных граней в плоском графе, поскольку звание цепи графа. Это свойство используется при определении коэффициент решетчатости графа, нормализованный вариант количества циклов ограниченных граней, который вычисляется путем деления ранга схемы на 2п − 5, максимально возможное количество ограниченных граней плоского графа с одним и тем же множеством вершин (Buhl et al. 2004 г. ).

Рекомендации

  • Buhl, J .; Gautrais, J .; Sole, R.V .; Kuntz, P .; Valverde, S .; Deneubourg, J.L .; Тераулаз, Г. (2004), "Эффективность и надежность в муравьиных сетях галерей", Европейский физический журнал B, Springer-Verlag, 42 (1): 123–129, Дои:10.1140 / epjb / e2004-00364-9.
  • Ja'Ja ', Джозеф; Саймон, Янош (1982), "Параллельные алгоритмы в теории графов: проверка планарности", SIAM Журнал по вычислениям, 11 (2): 314–328, Дои:10.1137/0211024, МИСТЕР  0652905.
  • Лефшец, Соломон (1965), «Планарные графики и связанные с ними темы», Труды Национальной академии наук Соединенных Штатов Америки, 54 (6): 1763–1765, Дои:10.1073 / пнас.54.6.1763, JSTOR  72818, МИСТЕР  0189011, ЧВК  300546, PMID  16591326.
  • Мак Лейн, С. (1937), «Комбинаторное условие для плоских графов» (PDF), Fundamenta Mathematicae, 28: 22–32.
  • О'Нил, П. В. (1973), "Краткое доказательство теоремы планарности Мак Лейна", Труды Американского математического общества, 37 (2): 617–618, Дои:10.1090 / S0002-9939-1973-0313098-X, HDL:2060/19720020939, JSTOR  2039496, МИСТЕР  0313098.