Введение

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

Заявление

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

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

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

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

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

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

Применение

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