Grafas (matematika)

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Peršokti į: navigaciją, paiešką
Duomenų struktūra „grafas“ aprašyta straipsnyje grafas (duomenų struktūra)

Matematikoje bei informatikoje grafas – tam tikrų objektų (viršūnių), sujungtų briaunomis ir/arba lankais, rinkinys.

Grafus tiria grafų teorija.

Grafas su viršūnėmis V = {1,2,3,4,5} ir briaunomis E = {{1,2}, {2,3}, {3,4}, {4,5}, {1,5}, {1,3}, {3,5}}

Apibrėžimas[taisyti | redaguoti kodą]

Grafu vadinsime porą G=(V, E), kur V – kokia nors aibė, o E – aibės V elementų porų aibė (paprastai porose elementų tvarka nesvarbi). Aibės V elementai vadinami grafo G viršūnėmis, o aibės E elementai - briaunomis. Plokštumoje grafo viršūnės dažnai vaizduojamos taškais, o briaunos - kreivėmis arba atkarpomis, jungiančiomis tuos taškus.

Terminai[taisyti | redaguoti kodą]

Grafai, kuriuose briaunos turi kryptis (porose elementų tvarka yra svarbi), vadinami orientuotaisiais grafais arba digrafais. Šiuo atveju briaunos vadinamos lankais. Grafai vadinami mišriaisiais, jei jie turi ir briaunų, ir lankų. Grafus, kuriuose briaunoms leidžiama kartotis (E yra multiaibė) vadiname multigrafais. Neorientuotus grafus, kuriuose nėra kartotinių briaunų ir kilpų (porų iš to paties elemento) vadiname paprastaisiais.

Dvi grafo viršūnės yra gretimos, jei jas jungia briauna (lankas). Turėdami briauną {u, v} (lanką (u,v)), sakome, kad viršūnės u ir v incidenčios briaunai {u, v} (lankui (u,v)).

Neorientuotas grafas vadinamas pilnuoju, jei kiekviena jo viršūnė briaunomis sujungta su visomis likusiomis (n viršūnių pilnasis grafas paprastai žymimas Kn). Grafas, neturintis lankų (briaunų), vadinamas tuščiuoju. Neorientuotasis grafas vadinamas dvidaliu, jei jo viršūnių aibę galima išskaidyti į dvi aibes A ir B tokias, kad kiekvienos jo briaunos skirtingi galai priklausytų skirtingoms aibėms A ir B.

Neorientuoto grafo viršūnės laipsnis yra viršūnių, gretimų duotajai, skaičius. Orientuotame grafe analogiškai apibrėžiami viršūnės įėjimo ir išėjimo laipsniai. Neorientuotasis grafas yra reguliarusis, jei jo visų viršūnių laipsniai yra lygūs.

Grafo grandine vadinama briaunų (lankų) seka (v0, v1), (v1, v2), …, (vn-1, vn). Norint apibrėžti grandinę, pakanka eilės tvarka nurodyti viršūnes, per kurias eina grandinė. Grandinės, kurių pirma viršūnė sutampa su paskutine, vadinamos ciklais. Grandinė (ciklas) yra paprastoji, jei ta pati viršūnė grandinėje pasikartoja tik vieną kartą (ciklo atveju pirma viršūnė gali sutapti su paskutine). Kelias – grandinė orientuotame grafe, o kontūras – ciklas orientuotame grafe. Grandinės ilgis – briaunų, priklausančių grandinei, skaičius.

Grafas H vadinamas grafo G pografiu, jei H viršūnių ir briaunų aibės yra atitinkamai grafo G viršūnių ir briaunų aibių poaibiai. Jei grafo H briaunų aibę sudaro visos G briaunų aibės briaunos, kurių abu galai priklauso H, tai H vadinamas indukuotuoju grafo G pografiu.

Neorientuotas grafas yra jungus (arba rišlus), jei kiekvieną jo viršūnių porą jungia grandinė. Grafo G maksimalus indukuotas pografis (toks, kurio negalima praplėsti, taip kad pografis liktų jungus) vadinamas jungiąja komponente.

Orientuoti grafai gali būti stipriai, vienakryptiškai ir silpnai jungūs arba nejungūs.


Commons-logo.svg Vikiteka: Grafas (matematika) – vaizdinė ir garsinė medžiaga

Vikiteka