Plokščiasis grafas

Plokščiasis grafas – toks grafas, kurį galima pavaizduoti plokštumoje taip, kad nė viena briauna nesikirstų. Kitaip dar vadinamas planariniu grafu.

Plokščiasis grafas

Grafas K₅

Neplokščiojo grafo pavyzdys paveikslėlyje kairėje. Šio grafo neįmanoma perpiešti plokštumoje taip, kad briaunos nesikirstų. Iš tiesų tai vienas iš dviejų mažiausių neplokščiųjų grafų.

Lenkų matematiko Kazimiero Kuratovskio suformuluota teorema apie plokščiuosius grafus () teiga, kad:

Baigtinis grafas yra plokščiasis tada ir tik tada, jei neturi pografio, kuris būtų grafui K₅ (pilnasis 5 viršūnių grafas) arba K_3,3.

Deja, naudojantis Kuratovskio teorema negalima greitai nustatyti ar grafas plokščiasis. Tačiau egzistuoja greiti O(n) sudėtingumo algoritmai, sprendžiantys šią problemą (n – viršūnių skaičius).

Eulerio formulė

Eulerio formulė teigia, kad jei baigtinis plokščiasis sujungtas grafas yra nubrėžtas plokštumoje be susikirtimų, v yra viršūnių skaičius, b – briaunų skaičius, o f – uždarų erdvių skaičius (įskaitant išorinį begalinį regioną), tai

v – b + f = 2

t. y. yra lygi 2. Šios formulės įrodymas labai paprastas – jei grafas nėra medis, pašaliname vieną cikle esančią briauną. Tai sumažins e ir f vienetu, taigi v – b + f liks nepakitęs. Kartojame tol, kol gausime medį, tada v = e + 1, f = 1, taigi v – b + f = 2.

Šaltiniai

1. Barthelemy, Marc (2017-12-30). Morphogenesis of Spatial Networks. Cham: Springer. ISBN .