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...

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!