Grafų teorija (konspektas)
Grafai. Ciklai. Keliai.
Grafas – figūra, sudaryta iš taškų (vadinamų viršūnėmis) ir atkarpų (vadinamų briaunomis). Briauna nebūtinai turi būti tiesi linija (gali būti lenkta, banguota), tačiau ji visada jungia dvi viršūnes. Kai briauna jungia viršūnę su ja pačia, ji vadinama kilpa. Grafas gali būti sudarytas iš dviejų ar daugiau atskirų nesujungtų dalių. Tokie grafai vadinami nejungiaisiais, o atskiri jo “gabalai” – grafo komponentėmis. Grafas yra sąsajų struktūra: jis mums pasako, kad yra objektų grupė (viršūnės) ir kad šie objektai yra tarpusavyje susiję (arba nesusiję). Kaip šie objektai susiję – nurodo briaunos.
•Dvi viršūnės vadinamos gretimomis, jei jas jungia bent viena briauna.
•Viršūnės laipsnis yra briaunų, išeinančių iš tos viršūnės, skaičius (kilpos “įnašas” lygus 2). Viršūnė, kurios laipsnis 0, vadinama izoliuota.
•Grafo keliu vadinama gretimų viršūnių seka. Kelyje ta pati viršūnė gali būti kelis kartus, tačiau ta pati briauna gali pasitaikyti tik vieną kartą.
•Kelias vadinamas ciklu, jei jis prasideda ir baigiasi ta pačia viršūne. •Sakoma, kad grafas jungusis, jei bet kurias dvi viršūnes galima sujungti keliu. Tai reiškia, kad iš vienos viršūnės galima nukeliauti į bet kurią kitą. Priešingu atveju grafas vadinamas nejungiuoju. Nejungusis grafas yra sudarytas iš jungiųjų dalių, vadinamų grafo komponentėmis.
•Jeigu jungiajame grafe yra tokia briauna, kurią ištrynus grafas tampa nejungiuoju, ji vadinam tiltu.
•Jei kelią sudaro visos jungiojo grafo briaunos (lygiai po vieną kartą), jos vadinamas Oilerio keliu. Oilerio kelias, kuris prasideda ir baigiasi toje pačioje viršūnėje, vadinamas Oilerio ciklu.
Maršrutų sudarymo uždaviniai – tai uždaviniai, kylantys ieškant efektyviausio kelio nugabenti į paskirties vietas prekes ar suteikti paslaugas. Bendras Oilerio ciklų uždavinių bruožas – tai poreikis efektyviai apeiti visas gatves (šaligatvius, kelius ir t.t.) nurodytoje vietovėje – mieste ar miesto rajone.
Oilerio teoremos
Pirmoji Oilerio teorema
•Jei grafas turi nelyginio laipsnio viršūnę, tai jis neturi Oilerio ciklų.
•Jei jungiojo grafo visos viršūnės yra lyginių laipsnių, tai jis turi bent vieną Oilerio ciklą (paprastai daugiau kaip vieną).
Antroji Oilerio teorema
•Jei grafas turi daugiau kaip dvi nelyginio laipsnio viršūnes, tai jis neturi nė vieno Oilerio kelio.
•Jei jungusis grafas turi lygiai dvi nelyginio laipsnio viršūnes, tai jis turi bent vieną Oilerio kelią (paprastai daugiau). Kiekvienas toks kelias prasideda vienoje nelyginio laipsnio viršūnėje ir baigiasi kitoje.
Trečioji Oilerio teorema •Visų grafo viršūnių laipsnių suma yra lyginis skaičius (lygus dvigubam briaunų skaičiui).
•Bet kurio grafo nelyginio laipsnio viršūnių skaičius yra lyginis.
Flerio algoritmas Oilerio ciklui rasti
•Pirmiausia įsitikiname, ar grafas yra jungusis ir ar visų viršūnių laipsniai yra lyginiai.
•Pradedame nuo bet kurios viršūnės.
•Keliaujame briauna, jei ji nėra nekeliautos dalies tiltas arba nėra kito pasirinkimo.
•Sunumeruojame briaunas perėjimo eilės tvarka.
•Darbą baigiame, kai apkeliaujame visas briaunas.
Flerio algoritmas Oilerio keliui rasti
•Pirmiausia įsitikiname, ar grafas yra jungusis ir ar yra tik dvi nelyginio laipsnio viršūnės.
•Pradedame nuo bet kurios nelyginio laipsnio viršūnės.
•Keliaujame briauna, jei ji nėra nekeliautos dalies tiltas arba nėra kito pasirinkimo.
•Sunumeruojame briaunas perėjimo eilės tvarka. •Darbą baigiame, kai apkeliaujame visas briaunas.
•Prie grafo prijungtos papildomos briaunos (vadinamos fiktyviomis) taip, kad nelyginio laipsnio viršūnės taptų lyginio laipsnio viršūnėmis. Ši grafo perdarymo procedūra, kai viršūnių nelyginumas pašalinamas, prijungiant papildomas briaunas, vadinam grafo oilerizavimu. Oilerizuodami grafą, turime atidžiai stebėti, kad prijungiamos briaunos būtų tik esančių grafo briaunų dublikatai. Optimali oilerizacija – kai “pridėtų” briaunų skaičius minimalus.
• Pusiau oilerizavimą turėsime, kai dviems viršūnėms paliksime nelyginius laipsnius, o visas kitas nelyginio laipsnio viršūnes padarysime lyginio laipsnio viršūnėmis.