Из Википедии, свободной энциклопедии
Перейти к навигацииПерейти к поиску

В теории графов , критерий плоскостности Маклеен является характеристикой плоских графов с точкой зрения их пространств цикла , названных в честь Маклейн , который опубликовал в 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-базиса

О'Нил (1973) представил следующий простой аргумент в пользу другого направления характеризации, основанный на теореме Вагнера, характеризующей плоские графы запрещенными минорами . Как замечает О'Нил, свойство иметь 2-базис сохраняется при минорах графа : если сжимать ребро, такое же сжатие может быть выполнено в базисных векторах, если удалить ребро, имеющее ненулевую координату в единственном базисный вектор, то этот вектор может быть удален из базиса, и если удалить ребро, имеющее ненулевую координату в двух базисных векторах, то эти два вектора могут быть заменены их суммой (по модулю два). Кроме того, если C ( G )является базисом цикла для любого графа, то он должен покрывать некоторые ребра ровно один раз, иначе его сумма была бы равна нулю (что невозможно для базиса), и поэтому C ( G ) может быть дополнен еще одним циклом, состоящим из этих однократно покрытых ребра при сохранении свойства, что каждое ребро покрывается не более чем дважды. Однако полный граф K 5 не имеет 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 имеет набор циклов с этим свойством, они обязательно образуют циклы граней вложения графа на сферу.

Заявление

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

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

Ссылки