Критерій планарності Маклейна
Крите́рій плана́рності Макле́йна — це опис планарних графів у термінах їхнього простору циклів. Критерій носить ім'я Саундерса Маклейна[en], який опублікував його 1937 року. Критерій стверджує, що скінченний неорієнтований граф є планарним тоді й лише тоді, коли простір циклів графа (за модулем 2) має базис циклів, у якому кожне ребро графа належить не більше ніж двом базисним векторам.
Для будь-якого циклу c у графі G можна сформувати m-вимірний 0-1-вектор, що має 1 в позиціях, відповідних ребрам циклу c, і 0 в інших позиціях. Простір циклів C(G) графа — це векторний простір, утворений усіма можливими комбінаціями векторів, утворених так способом. В описі Маклейна C(G) є векторним простором над скінченним полем GF(2) з двома елементами. Тобто в цьому векторному просторі вектори додаються покоординатно за модулем 2. 2-базис графа G — це базис графа C(G) з властивістю, що для кожного ребра e графа G максимум два базисних вектори мають ненульові координати в позиціях, відповідних e. Тоді, формальніше, опис Маклейна графів стверджує, що планарні графи — це точно ті графи, які мають 2-базис.
В одному напрямку критерій стверджує, що будь-який планарний граф має 2-базис. Такий базис можна знайти як набір меж граней планарного вкладення заданого графа G.
Якщо ребро є мостом графа G, воно з'являється двічі на одній межі, а тому має нульову координату у відповідному векторі. Таким чином, тільки ребра, які мають ненульові координати, розділяють дві різні грані. Ці ребра з'являються або один раз (якщо одна з граней не обмежена), або двічі в наборі меж обмежених граней. Залишається довести, що ці цикли утворюють базис. Один зі способів показати це — індукція. Базис індукції — випадок, коли граф G є деревом, ттому не має обмежених граней і C(G) має нульову розмірність і порожній базис. В іншому випадку, видалення ребра з необмеженої грані графа G зменшує як розмірність простору циклів, так і число обмежених граней на одиницю, що є індукційним переходом.
Альтернативно, можна використати формулу Ейлера, щоб показати, що число циклів у цьому наборі дорівнює контурному рангу графа G, який дорівнює розмірності простору циклів. Кожна непорожня підмножина циклів має суму векторів, яка представляє межу об'єднання обмежених граней у підмножині, яка не може бути порожньою (об'єднання включає принаймні одну межу і не включає необмеженої грані, так що повинні бути деякі ребра, які їх розділяють). Отже, немає підмножин циклів, суми векторів яких дорівнюють нулю, що означає, що всі цикли лінійно незалежні. Як лінійно незалежна множина того ж розміру, що й розмірність простору, цей набір циклів має формувати базис.
О'Ніл[1] запропонував такий простий аргумент для доведення критерію в іншому напрямку, ґрунтуючись на теоремі Вагнера, що описує планарні графи забороненими графами. Як зауважив О'Ніл, властивість містити 2-базис зберігається при створенні мінорів графів — якщо стягнути ребро, те саме стягування можна здійснити в базисних векторах. Якщо видалити ребро, яке має ненульову координату в базисному векторі, цей вектор можна видалити з базису, а якщо видалити ребро, що має ненульові координати в двох базисних векторах, то ці два вектори можна замінити їх сумою (за модулем 2). Крім того, якщо C(G) є базисом циклів для будь-якого графа, то цей базис має перекривати деякі ребра рівно один раз, в іншому випадку їх сума дорівнюватиме нулю (що неможливо для базису), а тоді C(G) можна розширити одним циклом, що складається з цих покритих один раз ребер, зберігаючи властивість, що кожне ребро покривається не більше двох разів.
Так, повний граф K5 не має 2-базису — C(G) є шестивимірним, кожен нетривіальний вектор в C(G) має ненульові координати принаймні для трьох ребер, а тому будь-яке розширення базису мало би принаймні 21 відмінний від нулів елемент, що перевищує 20 не рівних нулю компонент, які можуть бути ненульовими в десяти ребер у двох базисних векторах. З аналогічних причин, повний двочастковий граф K3,3 не має 2-базису — C(G) має розмірність 4, а будь-який нетривіальний вектор в C(G) має ненульові координати щонайменше для чотирьох ребер, так що будь-яке розширення базису мало би принаймні 20 ненульових елементів, що перевищує значення 18, яке виходить, коли кожне з дев'яти ребер ненульове в двох базисних векторах. Оскільки властивість мати 2-базис замкнута за мінорами і не виконується для двох мінімальних за мінорами непланарних графів K5 і K3,3, вона не виконується для будь-якого іншого непланарного графа.
Лефшец[2][./Критерий_планарности_Маклейна#cite_note-_d43248a8adb9c78e-2 [2]] надав інше доведення, засноване на алгебричній топології. Він використав злегка відмінне формулювання критерію планарності, згідно з яким граф планарний тоді й лише тоді, коли він має набір (не обов'язково простих) циклів, що покривають кожне ребро рівно двічі, так що єдиний нетривіальний зв'язок цих циклів у C(G) — їх сума дорівнює нулю. Якщо це так, то видалення одного з цих циклів дає базис, що задовольняє формулюванню критерію Маклейна. Якщо планарний граф вкладений у сферу, ясно, що його цикли граней задовольняють властивості Лефшеца. З іншого боку, як показав Лефшец, якщо граф G має набір циклів із цією властивістю, він обов'язково формує цикли граней при вкладенні у сферу.
Джа'Джа' і Саймон[3] використали критерій планарності Маклейна як частину паралельного алгоритму тестування планарності графа і знаходження планарних вкладень. Їхній алгоритм розбиває граф на тризв'язні компоненти, після чого є єдине планарне вкладення (з точністю до вибору зовнішньої грані) і цикли в 2-базисі будуть усіма периферійними циклами графа. Джа'Джа' і Саймон почали з фундаментального базису циклів графа (базис циклів, отриманих з кістякового дерева формуванням циклу для кожної можливої комбінації шляху в дереві і ребра поза деревом) і перетворюють його в 2-базис периферійних циклів. Ці цикли утворюють грані планарного вкладення заданого графа.
Критерій планарності Маклейна дозволяє легко порахувати число обмежених граней як контурний ранг графа. Властивість використовують у визначенні коефіцієнта сітчастості графа, нормалізованого варіанту числа циклів обмежених граней, який обчислюється діленням контурного рангу на 2n − 5, найбільше число обмежених граней планарного графа з тим самим набором вершин[4].
- Buhl J., Gautrais J., Sole R.V., Kuntz P., Valverde S., Deneubourg J.L., Heraulaz G. Efficiency and robustness in ant networks of galleries // The European Physical Journal B. — Springer-Verlag, 2004. — Т. 42, вип. 1. — С. 123–129. — DOI:.
- Joseph Ja'Ja', Janos Simon. Parallel algorithms in graph theory: planarity testing // SIAM Journal on Computing. — 1982. — Т. 11, вип. 2. — С. 314–328. — DOI:.
- Solomon Lefschetz. Planar graphs and related topics // Proceedings of the National Academy of Sciences of the United States of America. — 1965. — Т. 54. — С. 1763–1765. — DOI:.
- Mac Lane S. A combinatorial condition for planar graphs // Fundamenta Mathematicae. — 1937. — Т. 28. — С. 22–32. Архівовано з джерела 20 січня 2022. Процитовано 29 травня 2022.
- O'Neil P. V. A short proof of Mac Lane's planarity theorem // Proceedings of the American Mathematical Society. — 1973. — Т. 37. — С. 617–618. — DOI:.