Plokščiasis grafas
Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Plokščiasis grafas – toks grafas, kurį galima pavaizduoti plokštumoje taip, kad nė viena briauna nesikirstų. Kitaip dar vadinamas planariniu grafu.
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 (Kuratovskio teorema) teiga, kad:
- Baigtinis grafas yra plokščiasis tada ir tik tada, jei neturi pografio, kuris būtų homeomorfinis grafui K5 (pilnasis 5 viršūnių grafas) arba K3,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).
[taisyti] 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. Eulerio charakteristika 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.
