Планарний граф — граф, який може бути зображений на площині без перетину ребер.
Граф зображений на площині називається плоским, якщо його ребра не перетинаються. Граф називається планарним, якщо він ізоморфний деякому плоскому графу. Тобто існує відображення вершин графа на деякі точки площини і ребер графа на прості криві у площині, так що кінцями кривих є точки, що відповідають вершинам ребра і дві різні криві не мають спільних точок, окрім можливо кінцевих.
Критерій непланарності
- достатня умова — якщо граф містить двочастковий підграф K3,3 або повний підграф K5, то він є не планарним;
- необхідна умова — якщо граф не планарний, то він повинен містити більше 4 вершин, степінь яких більше 3, або більше 5 вершин, степінь яких більше 2.
Теорема Куратовського
Граф є планарним тоді і тільки тоді, коли він не містить підграфів, гомеоморфних K5 або K3,3.
Теорема Вагнера
Граф є планарним тоді і тільки тоді, коли він не містить підграфів, що (стягуються) в K5 або K3,3.
Формула Ейлера
Для зв'язного плоского графа справедливе таке співвідношення між кількістю вершин V, ребер E і граней F (включаючи зовнішню грань):
Його було знайдено Ейлером в 1736 році при вивченні властивостей опуклих багатогранників. Це співвідношення справедливе і для інших поверхонь з точністю до коефіцієнта, що називається характеристикою Ейлера. Це інваріант поверхні, для площини або сфери він дорівнює два.
Формула має багато корисних наслідків. З того, що кожна грань обмежена не менше ніж трьома ребрами і кожне ребро дотичне, щонайбільше до двох граней, випливає, що для плоского графа:
Тобто, при більшому числі ребер граф непланарний. Звідси випливає, що в планарному графі завжди можна знайти вершину степеня не більше 5.
Властивості
- Довільний планарний граф може бути зображений на площині так, щоб всі його ребра були прямими відрізками (теорема Фарі).
- Вершини довільного планарного графа можна розфарбувати в чотири кольори так, щоб усі суміжні вершини мали різні кольори.
Різновиди планарних графів
Максимальні планарні графи
Граф називається максимальним планарним якщо він планарний, але додавання будь-якого ребра (до існуючих вершин) зробить його не планарним.
Цей розділ потребує доповнення. |
Зовнішні планарні графи
Планарний граф називається зовнішнім планарним, якщо існує грань, що містить всі його вершини. Дані графи можна зобразити на поверхні так, що всі вершини будуть розміщені на колі.
Приклади
- Усі дерева є зовнішніми планарними графами.
- Граф K4 є планарним графом, що не є зовнішнім планарним.
Властивості зовнішніх планарних графів
- Довільний зовнішній планарний граф має вершину степеня щонайбільше 2.
- Вершини довільного зовнішнього планарного графа можна розфарбувати в три кольори так, щоб усі суміжні вершини мали різні кольори.
Див. також
Джерела
- А. Ю. Ольшанский. Плоские графы, СОЖ, 1996, No 11,
- Ф. Харари. Теория графов. М.: «Мир». 1973
В іншому мовному розділі є повніша стаття Planar graph(англ.). Ви можете допомогти, розширивши поточну статтю за допомогою з англійської. (липень 2022)
|
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Planarnij graf graf yakij mozhe buti zobrazhenij na ploshini bez peretinu reber Graf zobrazhenij na ploshini nazivayetsya ploskim yaksho jogo rebra ne peretinayutsya Graf nazivayetsya planarnim yaksho vin izomorfnij deyakomu ploskomu grafu Tobto isnuye vidobrazhennya vershin grafa na deyaki tochki ploshini i reber grafa na prosti krivi u ploshini tak sho kincyami krivih ye tochki sho vidpovidayut vershinam rebra i dvi rizni krivi ne mayut spilnih tochok okrim mozhlivo kincevih Kriterij neplanarnostidostatnya umova yaksho graf mistit dvochastkovij pidgraf K3 3 abo povnij pidgraf K5 to vin ye ne planarnim neobhidna umova yaksho graf ne planarnij to vin povinen mistiti bilshe 4 vershin stepin yakih bilshe 3 abo bilshe 5 vershin stepin yakih bilshe 2 Teorema KuratovskogoGraf ye planarnim todi i tilki todi koli vin ne mistit pidgrafiv gomeomorfnih K5 abo K3 3 K5 povnij graf z 5 vershinamiK3 3 povnij dvochastkovij grafTeorema Vagnera Dokladnishe Teorema Vagnera Graf ye planarnim todi i tilki todi koli vin ne mistit pidgrafiv sho styaguyutsya v K5 abo K3 3 Formula EjleraDlya zv yaznogo ploskogo grafa spravedlive take spivvidnoshennya mizh kilkistyu vershin V reber E i granej F vklyuchayuchi zovnishnyu gran V E F 2 displaystyle V E F 2 Jogo bulo znajdeno Ejlerom v 1736 roci pri vivchenni vlastivostej opuklih bagatogrannikiv Ce spivvidnoshennya spravedlive i dlya inshih poverhon z tochnistyu do koeficiyenta sho nazivayetsya harakteristikoyu Ejlera Ce invariant poverhni dlya ploshini abo sferi vin dorivnyuye dva Formula maye bagato korisnih naslidkiv Z togo sho kozhna gran obmezhena ne menshe nizh troma rebrami i kozhne rebro dotichne shonajbilshe do dvoh granej viplivaye sho dlya ploskogo grafa E 3V 6 displaystyle E leqslant 3V 6 Tobto pri bilshomu chisli reber graf neplanarnij Zvidsi viplivaye sho v planarnomu grafi zavzhdi mozhna znajti vershinu stepenya ne bilshe 5 VlastivostiDovilnij planarnij graf mozhe buti zobrazhenij na ploshini tak shob vsi jogo rebra buli pryamimi vidrizkami teorema Fari Vershini dovilnogo planarnogo grafa mozhna rozfarbuvati v chotiri kolori tak shob usi sumizhni vershini mali rizni kolori Riznovidi planarnih grafivMaksimalni planarni grafi Graf Goldnera Harari maksimalnij planarnij Vsi jogo grani obmezheni troma rebrami Graf nazivayetsya maksimalnim planarnim yaksho vin planarnij ale dodavannya bud yakogo rebra do isnuyuchih vershin zrobit jogo ne planarnim Cej rozdil potrebuye dopovnennya Zovnishni planarni grafi Dokladnishe Zovniplanarnij graf Graf K4 Planarnij graf nazivayetsya zovnishnim planarnim yaksho isnuye gran sho mistit vsi jogo vershini Dani grafi mozhna zobraziti na poverhni tak sho vsi vershini budut rozmisheni na koli Prikladi Usi dereva ye zovnishnimi planarnimi grafami Graf K4 ye planarnim grafom sho ne ye zovnishnim planarnim Vlastivosti zovnishnih planarnih grafiv Dovilnij zovnishnij planarnij graf maye vershinu stepenya shonajbilshe 2 Vershini dovilnogo zovnishnogo planarnogo grafa mozhna rozfarbuvati v tri kolori tak shob usi sumizhni vershini mali rizni kolori Div takozhTeorema pro planarne rozbittya Gipoteza Shejnermana Teorema Shnajdera Kriterij planarnosti VitniDzherelaA Yu Olshanskij Ploskie grafy SOZh 1996 No 11 F Harari Teoriya grafov M Mir 1973V inshomu movnomu rozdili ye povnisha stattya Planar graph angl Vi mozhete dopomogti rozshirivshi potochnu stattyu za dopomogoyu perekladu z anglijskoyi lipen 2022 Divitis avtoperekladenu versiyu statti z movi anglijska Perekladach povinen rozumiti sho vidpovidalnist za kincevij vmist statti u Vikipediyi nese same avtor redaguvan Onlajn pereklad nadayetsya lishe yak korisnij instrument pereglyadu vmistu zrozumiloyu movoyu Ne vikoristovujte nevichitanij i nevidkorigovanij mashinnij pereklad u stattyah ukrayinskoyi Vikipediyi Mashinnij pereklad Google ye korisnoyu vidpravnoyu tochkoyu dlya perekladu ale perekladacham neobhidno vipravlyati pomilki ta pidtverdzhuvati tochnist perekladu a ne prosto skopiyuvati mashinnij pereklad do ukrayinskoyi Vikipediyi Ne perekladajte tekst yakij vidayetsya nedostovirnim abo neyakisnim Yaksho mozhlivo perevirte tekst za posilannyami podanimi v inshomovnij statti Dokladni rekomendaciyi div Vikipediya Pereklad