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

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

Утверждение

Для любого цикла c в графе G можно сформировать m-мерный 0-1 вектор, имеющий 1 в позициях, соответствующих рёбрам цикла c, и 0 в остальных позициях. Пространство циклов 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) может быть расширен одним циклом, состоящим из этих покрытых один раз рёбер, сохраняя свойство, что каждое ребро покрывается не более двух раз.

Так, полный граф K₅ не имеет 2-базиса — C(G) является шестимерным, каждый нетривиальный вектор в C(G) имеет ненулевые координаты по меньшей мере для трёх рёбер, а потому любое расширение базиса имело бы по меньшей мере 21 отличный от нулей элемент, что превышает 20 не равных нулю компонент, которые могут быть ненулевыми у десяти рёбер в двух базисных векторах. По аналогичным причинам, полный двудольный граф K_3,3 не имеет 2-базиса — C(G) имеет размерность четыре, а любой нетривиальный вектор в C(G) имеет ненулевые координаты по меньшей мере для четырёх рёбер, так что любое расширение базиса имело бы по меньшей мере 20 ненулевых элементов, что превышает значение 18, которое получается, когда каждое из девяти рёбер ненулевое в двух базисных векторах. Поскольку свойство иметь 2-базис замкнуто по минорам и не выполняется для двух минимальных по минорам непланарных графов K₅ и K_3,3, оно не выполняется для любого другого непланарного графа.

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

Приложения

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

Критерий планарности Маклейна позволяет легко посчитать число ограниченных граней как контурный ранг графа. Свойство используется в определении коэффициента сетчатости графа, нормализованного варианта числа циклов ограниченных граней, который вычисляется путём деления контурного ранга на 2n − 5, максимальное число ограниченных граней планарного графа с тем же набором вершин.