Крите́рій плана́рності Макле́йна — це опис планарних графів у термінах їхнього простору циклів. Критерій носить ім'я [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-базису для планарних графів
В одному напрямку критерій стверджує, що будь-який планарний граф має 2-базис. Такий базис можна знайти як набір меж граней планарного вкладення заданого графа G.
Якщо ребро є мостом графа G, воно з'являється двічі на одній межі, а тому має нульову координату у відповідному векторі. Таким чином, тільки ребра, які мають ненульові координати, розділяють дві різні грані. Ці ребра з'являються або один раз (якщо одна з граней не обмежена), або двічі в наборі меж обмежених граней. Залишається довести, що ці цикли утворюють базис. Один зі способів показати це — індукція. Базис індукції — випадок, коли граф G є деревом, ттому не має обмежених граней і C(G) має нульову розмірність і порожній базис. В іншому випадку, видалення ребра з необмеженої грані графа G зменшує як розмірність простору циклів, так і число обмежених граней на одиницю, що є індукційним переходом.
Альтернативно, можна використати формулу Ейлера, щоб показати, що число циклів у цьому наборі дорівнює контурному рангу графа G, який дорівнює розмірності простору циклів. Кожна непорожня підмножина циклів має суму векторів, яка представляє межу об'єднання обмежених граней у підмножині, яка не може бути порожньою (об'єднання включає принаймні одну межу і не включає необмеженої грані, так що повинні бути деякі ребра, які їх розділяють). Отже, немає підмножин циклів, суми векторів яких дорівнюють нулю, що означає, що всі цикли лінійно незалежні. Як лінійно незалежна множина того ж розміру, що й розмірність простору, цей набір циклів має формувати базис.
Неминучість планарності, якщо існує 2-базис
О'Ніл запропонував такий простий аргумент для доведення критерію в іншому напрямку, ґрунтуючись на теоремі Вагнера, що описує планарні графи забороненими графами. Як зауважив О'Ніл, властивість містити 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 має набір циклів із цією властивістю, він обов'язково формує цикли граней при вкладенні у сферу.
Застосування
Джа'Джа' і Саймон використали критерій планарності Маклейна як частину паралельного алгоритму тестування планарності графа і знаходження планарних вкладень. Їхній алгоритм розбиває граф на , після чого є єдине планарне вкладення (з точністю до вибору зовнішньої грані) і цикли в 2-базисі будуть усіма периферійними циклами графа. Джа'Джа' і Саймон почали з фундаментального базису циклів графа (базис циклів, отриманих з кістякового дерева формуванням циклу для кожної можливої комбінації шляху в дереві і ребра поза деревом) і перетворюють його в 2-базис периферійних циклів. Ці цикли утворюють грані планарного вкладення заданого графа.
Критерій планарності Маклейна дозволяє легко порахувати число обмежених граней як контурний ранг графа. Властивість використовують у визначенні коефіцієнта сітчастості графа, нормалізованого варіанту числа циклів обмежених граней, який обчислюється діленням контурного рангу на 2n − 5, найбільше число обмежених граней планарного графа з тим самим набором вершин.
Примітки
Література
- 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 // . — 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: .
- 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: .
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Krite rij plana rnosti Makle jna ce opis planarnih grafiv u terminah yihnogo prostoru cikliv Kriterij nosit im ya en yakij opublikuvav jogo 1937 roku Kriterij stverdzhuye sho skinchennij neoriyentovanij graf ye planarnim todi j lishe todi koli prostir cikliv grafa za modulem 2 maye bazis cikliv u yakomu kozhne rebro grafa nalezhit ne bilshe nizh dvom bazisnim vektoram TverdzhennyaDlya bud yakogo ciklu c u grafi G mozhna sformuvati m vimirnij 0 1 vektor sho maye 1 v poziciyah vidpovidnih rebram ciklu c i 0 v inshih poziciyah Prostir cikliv C G grafa ce vektornij prostir utvorenij usima mozhlivimi kombinaciyami vektoriv utvorenih tak sposobom V opisi Maklejna C G ye vektornim prostorom nad skinchennim polem GF 2 z dvoma elementami Tobto v comu vektornomu prostori vektori dodayutsya pokoordinatno za modulem 2 2 bazis grafa G ce bazis grafa C G z vlastivistyu sho dlya kozhnogo rebra e grafa G maksimum dva bazisnih vektori mayut nenulovi koordinati v poziciyah vidpovidnih e Todi formalnishe opis Maklejna grafiv stverdzhuye sho planarni grafi ce tochno ti grafi yaki mayut 2 bazis Isnuvannya 2 bazisu dlya planarnih grafivV odnomu napryamku kriterij stverdzhuye sho bud yakij planarnij graf maye 2 bazis Takij bazis mozhna znajti yak nabir mezh granej planarnogo vkladennya zadanogo grafa G Yaksho rebro ye mostom grafa G vono z yavlyayetsya dvichi na odnij mezhi a tomu maye nulovu koordinatu u vidpovidnomu vektori Takim chinom tilki rebra yaki mayut nenulovi koordinati rozdilyayut dvi rizni grani Ci rebra z yavlyayutsya abo odin raz yaksho odna z granej ne obmezhena abo dvichi v nabori mezh obmezhenih granej Zalishayetsya dovesti sho ci cikli utvoryuyut bazis Odin zi sposobiv pokazati ce indukciya Bazis indukciyi vipadok koli graf G ye derevom ttomu ne maye obmezhenih granej i C G maye nulovu rozmirnist i porozhnij bazis V inshomu vipadku vidalennya rebra z neobmezhenoyi grani grafa G zmenshuye yak rozmirnist prostoru cikliv tak i chislo obmezhenih granej na odinicyu sho ye indukcijnim perehodom Alternativno mozhna vikoristati formulu Ejlera shob pokazati sho chislo cikliv u comu nabori dorivnyuye konturnomu rangu grafa G yakij dorivnyuye rozmirnosti prostoru cikliv Kozhna neporozhnya pidmnozhina cikliv maye sumu vektoriv yaka predstavlyaye mezhu ob yednannya obmezhenih granej u pidmnozhini yaka ne mozhe buti porozhnoyu ob yednannya vklyuchaye prinajmni odnu mezhu i ne vklyuchaye neobmezhenoyi grani tak sho povinni buti deyaki rebra yaki yih rozdilyayut Otzhe nemaye pidmnozhin cikliv sumi vektoriv yakih dorivnyuyut nulyu sho oznachaye sho vsi cikli linijno nezalezhni Yak linijno nezalezhna mnozhina togo zh rozmiru sho j rozmirnist prostoru cej nabir cikliv maye formuvati bazis Neminuchist planarnosti yaksho isnuye 2 bazisO Nil zaproponuvav takij prostij argument dlya dovedennya kriteriyu v inshomu napryamku gruntuyuchis na teoremi Vagnera sho opisuye planarni grafi zaboronenimi grafami Yak zauvazhiv O Nil vlastivist mistiti 2 bazis zberigayetsya pri stvorenni minoriv grafiv yaksho styagnuti rebro te same styaguvannya mozhna zdijsniti v bazisnih vektorah Yaksho vidaliti rebro yake maye nenulovu koordinatu v bazisnomu vektori cej vektor mozhna vidaliti z bazisu a yaksho vidaliti rebro sho maye nenulovi koordinati v dvoh bazisnih vektorah to ci dva vektori mozhna zaminiti yih sumoyu za modulem 2 Krim togo yaksho C G ye bazisom cikliv dlya bud yakogo grafa to cej bazis maye perekrivati deyaki rebra rivno odin raz v inshomu vipadku yih suma dorivnyuvatime nulyu sho nemozhlivo dlya bazisu a todi C G mozhna rozshiriti odnim ciklom sho skladayetsya z cih pokritih odin raz reber zberigayuchi vlastivist sho kozhne rebro pokrivayetsya ne bilshe dvoh raziv Tak povnij graf K5 ne maye 2 bazisu C G ye shestivimirnim kozhen netrivialnij vektor v C G maye nenulovi koordinati prinajmni dlya troh reber a tomu bud yake rozshirennya bazisu malo bi prinajmni 21 vidminnij vid nuliv element sho perevishuye 20 ne rivnih nulyu komponent yaki mozhut buti nenulovimi v desyati reber u dvoh bazisnih vektorah Z analogichnih prichin povnij dvochastkovij graf K3 3 ne maye 2 bazisu C G maye rozmirnist 4 a bud yakij netrivialnij vektor v C G maye nenulovi koordinati shonajmenshe dlya chotiroh reber tak sho bud yake rozshirennya bazisu malo bi prinajmni 20 nenulovih elementiv sho perevishuye znachennya 18 yake vihodit koli kozhne z dev yati reber nenulove v dvoh bazisnih vektorah Oskilki vlastivist mati 2 bazis zamknuta za minorami i ne vikonuyetsya dlya dvoh minimalnih za minorami neplanarnih grafiv K5 i K3 3 vona ne vikonuyetsya dlya bud yakogo inshogo neplanarnogo grafa Lefshec 2 Kriterij planarnosti Maklejna cite note d43248a8adb9c78e 2 2 nadav inshe dovedennya zasnovane na algebrichnij topologiyi Vin vikoristav zlegka vidminne formulyuvannya kriteriyu planarnosti zgidno z yakim graf planarnij todi j lishe todi koli vin maye nabir ne obov yazkovo prostih cikliv sho pokrivayut kozhne rebro rivno dvichi tak sho yedinij netrivialnij zv yazok cih cikliv u C G yih suma dorivnyuye nulyu Yaksho ce tak to vidalennya odnogo z cih cikliv daye bazis sho zadovolnyaye formulyuvannyu kriteriyu Maklejna Yaksho planarnij graf vkladenij u sferu yasno sho jogo cikli granej zadovolnyayut vlastivosti Lefsheca Z inshogo boku yak pokazav Lefshec yaksho graf G maye nabir cikliv iz ciyeyu vlastivistyu vin obov yazkovo formuye cikli granej pri vkladenni u sferu ZastosuvannyaDzha Dzha i Sajmon vikoristali kriterij planarnosti Maklejna yak chastinu paralelnogo algoritmu testuvannya planarnosti grafa i znahodzhennya planarnih vkladen Yihnij algoritm rozbivaye graf na pislya chogo ye yedine planarne vkladennya z tochnistyu do viboru zovnishnoyi grani i cikli v 2 bazisi budut usima periferijnimi ciklami grafa Dzha Dzha i Sajmon pochali z fundamentalnogo bazisu cikliv grafa bazis cikliv otrimanih z kistyakovogo dereva formuvannyam ciklu dlya kozhnoyi mozhlivoyi kombinaciyi shlyahu v derevi i rebra poza derevom i peretvoryuyut jogo v 2 bazis periferijnih cikliv Ci cikli utvoryuyut grani planarnogo vkladennya zadanogo grafa Kriterij planarnosti Maklejna dozvolyaye legko porahuvati chislo obmezhenih granej yak konturnij rang grafa Vlastivist vikoristovuyut u viznachenni koeficiyenta sitchastosti grafa normalizovanogo variantu chisla cikliv obmezhenih granej yakij obchislyuyetsya dilennyam konturnogo rangu na 2n 5 najbilshe chislo obmezhenih granej planarnogo grafa z tim samim naborom vershin PrimitkiO Neil 1973 Lefschetz 1965 Ja Ja Simon 1982 Buhl Gautrais Sole Kuntz i dr 2004 LiteraturaBuhl 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 T 42 vip 1 S 123 129 DOI 10 1140 epjb e2004 00364 9 Joseph Ja Ja Janos Simon Parallel algorithms in graph theory planarity testing 1982 T 11 vip 2 S 314 328 DOI 10 1137 0211024 Solomon Lefschetz Planar graphs and related topics Proceedings of the National Academy of Sciences of the United States of America 1965 T 54 S 1763 1765 DOI 10 1073 pnas 54 6 1763 A combinatorial condition for planar graphs Fundamenta Mathematicae 1937 T 28 S 22 32 z dzherela 20 sichnya 2022 Procitovano 29 travnya 2022 O Neil P V A short proof of Mac Lane s planarity theorem Proceedings of the American Mathematical Society 1973 T 37 S 617 618 DOI 10 1090 S0002 9939 1973 0313098 X