Diskrečiųjų struktūrų grafas

Pirmasis grafo terminą įvedė matematikas D. Kionigas 1936 m.
V - netuščia aibė (viršūnių), B - visų aibės V galimų dvielemenčių poaibių aibė (visų įmanomų briaunų aibė), U - bet koks aibės B poaibis (briaunų aibė).
Grafas – rinkinys viršūnių ir briaunų, jungiančių viršūnių poras (nebūtinai visas). G = (V, B).
Geometriškai viršūnė – tai vienas taškas, kuris neturi nei dydžio, nei kitų matmenų.
Grafo G = (V,B) didumu vad. skaičius, lygus grafo briaunų skaičiui.
Briaunos galų viršūnės vadinamos gretimomis viršūnėmis.
Viršūnės vi ir vj vadinamos incidentiškomis briaunai {vi, vj}.
Briaunos, turinčios bendrą incidentišką viršūnę, vadinamos gretimomis.
Briauna jungianti viršūnę su ja pačia, vadinama kilpa.
GRAFU TIPAI
1. Nulinis grafas Grafas G = (Æ,Æ) vadinamas nuliniu grafu.
2. Tuščiasis grafas Grafas, susidedantis tik iš izoliuotų viršūnių, vadinamas tuščiuoju grafu (G = (V,Æ).
3. Neorientuotas grafas Grafai, kurių briaunos neturi krypties, t.y. briauna galima keliauti bet kuria kryptimi, vad. neorientuotais grafais. Jei briaunos neturi papildomų atributų (pavyzdžiui, svorių), tai tarp dviejų viršūnių gali būti tik viena briauna (neprasminga turėti kelių identiškų briaunų).
4. Orientuotas grafas Briauna, kuriai galima suteikti kryptį, vadinama lanku.
Grafas, kuriame nurodyta kiekvienos briaunos kryptis, vadinamas orientuotu arba orgrafu.
Orientuoto grafo viršūnė v1 vadinama lanko (v1, v2) pradžia, o v2 – lanko pabaiga (galas), arba v1 ir v2 – lanko kraštinės viršūnės.
Orientuoto grafo viršūnės yra gretimos, jei jos yra kraštinės lanko viršūnės
Dvi viršūnės yra gretimos (kaimyninės), jei jos sujungtos bent vienu lanku
Lankai, turintys bendrą kraštinę viršūnę, vadinami gretimais.
Jei turime (lanką) (v1, v2), tai sakome, kad viršūnė v1 (v2) incidentiška lankui (v1, v2) ir atvirkščiai.
5. Mišrusis grafas Grafas, turintis ir briaunų ir lankų, tai jis vadinamas mišriuoju grafu.
6. Multigrafas Grafas, turintis bent vieną viršūnių porą, kuri jungiama keliomis briaunomis, vadinamas multigrafu.
7. Dvidalis grafas Grafas, kurio viršūnių aibę galima išskaidyti į du poaibius A ir B taip, kad kiekvienos briaunos galai priklausytų skirtingiems poaibiams, vadinamas dvidaliu grafu.
8. Baigtinis grafas Grafas, kurį sudaro baigtinės briaunų ir...

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!