Критерий планарности Мак Лейна

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

Заявление

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

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

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

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

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

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

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

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

Приложение

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

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

Ссылки

Буль, Дж.; Готре, Ж.; Соле, Р.В.; Кунц, П.; Вальверде, С.; Денебур, JL; Тераулаз, Г. (2004), «Эффективность и надежность муравьиных сетей галерей», The European Physical Journal B , 42 (1), Springer-Verlag: 123–129, Bibcode : 2004EPJB...42..123B , doi : 10.1140/epjb/e2004-00364-9 , S2CID 14975826 .
Джа'Джа, Джозеф; Саймон, Янош (1982), «Параллельные алгоритмы в теории графов: проверка планарности», SIAM Journal on Computing , 11 (2): 314–328, doi : 10.1137/0211024 , MR 0652905 .
Лефшец, Соломон (1965), «Плоские графы и смежные темы», Труды Национальной академии наук Соединенных Штатов Америки , 54 (6): 1763–1765, Бибкод : 1965PNAS...54.1763L , doi : 10.1073 /pnas.54.6.1763 , JSTOR 72818 , MR 0189011 , PMC 300546 , PMID 16591326 .
Мак Лейн, С. (1937), «Комбинаторное условие для плоских графов» (PDF) , Fundamentals of Mathematics , 28 : 22–32, doi : 10.4064/fm-28-1-22-32 .
О'Нил, П.В. (1973), «Краткое доказательство теоремы Мак Лейна о планарности», Proceedings of the American Mathematical Society , 37 (2): 617–618, doi : 10.1090/S0002-9939-1973-0313098-X , HDL : 2060/19720020939 , JSTOR 2039496 , MR 0313098 .