Grafai
5 (100%) 1 vote

Grafai

Grafai – Pagrindinės sąvokos

G(n,m) – grafas, turintis n viršūnių ir m briaunų.Aibė V vadinama grafo viršūnių aibe.

Aibės V elementų skaičius yra lygus grafo viršūnių skaičiui ir vadinamas grafo eile.

Grafas turintis tik briaunas vadinamas neorientuotu.

Grafas turintis tik lankus, vadinamas orientuotu.

Grafas, turintis ir briaunų, ir lankų vadinamas mišriuoju.

Briauna, turinti vieną viršūnę, vadinama kilpa.

Dvi briaunos yra gretimos, jei jos turi bendrą galą.

Jei turime briauną (lanką) (v1, v2), tai sakome, kad viršūnė v1 ar v2 incidentiška briaunai (lankui) (v1, v2) ir atvirkščiai.

Jei grafas turi bent vieną viršūnių porą, kuri jungiama keliomis briaunomis, tai grafas vadinamas multigrafu.

Jei kiekviena grafo viršūnė jungiama briaunomis su visomis likusiomis viršūnėmis, tai toks grafas yra pilnasis grafas. Žymima Kn.

Grafas, kurio briaunų (lankų) aibė yra tuščioji aibė, vadinamas tuščiuoju grafu. Žymimas On.

Grafas, kurio viršūnių aibę galima išskaidyti į du poaibius A ir B taip, kad kiekvienos briaunos galai priklausytų skirtingiems poaibiams, vadinamas dvidaliu grafu.

Viršūnės v laipsnis – skaičius viršūnių gretimų viršūnei v. Žymėsime r(v) arba d(v).

Orientuoto grafo atveju skiriami viršūnės įėjimo ir išėjimo puslaipsniai. Įėjimo puslaipsnis, tai skaičius lankų, įeinančių į viršūnę, o išėjimo puslaipsnis – skaičius lankų, išeinančių iš viršūnės.

Seka d(v1), d(v2),… vadinama grafo viršūnių laipsnių seka.

Grafo briaunų skaičius lygus visų jo viršūnių laipsnių sumos pusei.

Pilnojo grafo visų viršūnių laipsniai yra lygūs ir lygūs (n-1). Vadinasi pilnojo grafo briaunų sk. m=n(n-1)/2.

Jei grafo visų viršūnių laipsniai yra lygūs, tai grafas vadinamas reguliariuoju grafu.

Seka briaunų (v1,v2), (v2,v3), …, (vk-1,vk), t.y. gretimų briaunų seka vadinama grandine.

Grandinę galima apibrėžti viršūnių, per kurias ji eina seka. Pvz., m=(v1, v2, …, vk). Jei grandinės pirmoji ir paskutinioji viršūnės sutampa, tai tokia grandinė vadinama ciklu.

Grandinė (ciklas) vadinama paprastąja grandine (paprastuoju ciklu), jei visos ją sudarančios briaunos yra skirtingos.

Grandinė ciklas vadinama elementariąja, jei ji eina per skirtingas viršūnes.

Grandinės (ciklo) ilgis, tai skaičius briaunų, sudarančių grandinę (ciklą.). Žymėsime l(m) arba l(v1,vk)

Seka lankų (v1,v2), (v2,v3), …, (vk-1,vk), t.y. gretimų lankų seka vadinama keliu.

Kelią galima apibrėžti viršūnių, per kurias jis eina seka. Pvz., m=(v1, v2, …, vk). Jei kelio pirmoji ir paskutinioji viršūnės sutampa, tai toks kelias vadinamas kontūru.

Grafo G=(V,U) dalinis grafas, tai grafas, turintis tą pačią viršūnių aibių dalį pradinio grafo briaunų (lankų). Tiksliau kalbant, H=(V,UH) yra grafo G=(V,U) dalinis grafas, jei UHÍU.

Tarkim A yra grafo G viršūnių aibės V poaibis. Tada grafas P(A,B) yra pografis, kurį indukuoja viršūnių aibė A (indukuotasis pografis), jei viršūnių aibė sutampa su aibe A, o briaunų (lankų) aibę B sudaro tos grafo G briaunos (lankai), kurių abu galai priklauso aibei A. Indukuoto pografio dalinis grafas vadinamas pografiu.

Grafo G={V,U) jungioji komponentė, tai pografis, kurį indukuoja aibė sudaryta iš bet kurios grafo G viršūnės v ir visų tų viršūnių, į kurias galima keliauti iš viršūnės v.

Grafas turi tris jungiamąsias komponentes. Pirmąją komponentę sudaro pografis, kurį indukuoja viršūnių aibė {1,2,3,6,7}, antrąją –{4,8,6} ir trečiąją – {5}.

Orientuotasis grafas G yra stipriai jungus, jeigu bet kokios dvi viršūnės x ir y yra pasiekiamos viena iš kitos. Kitaip tariant, iš bet kurios viršūnės galime nukeliauti į bet kurią viršūnę y ir atvirkščiai.

Orientuotasis grafas yra vienakryptiškai jungus, jeigu bet kokiai porai viršūnių x ir y , jos yra pasiekiamos bent viena kryptimi, t.y. arba y pasiekiama iš viršūnės x arba x pasiekiama iš viršūnės y.

Orientuotasi grafas yra silpnai jungus, jei yra jungus neorientuotas grafas gautas iš orientuoto, pakeitus lankus briaunomis.

Grafo vaizdavimas gretimumo matrica

Grafo G(V,U) gretimumo matrica yra kvadratinė n-otsios eilės matrica S=[sij], i=1,n, kurios elementas sij apibrėžiamas taip: sij=1, jei viršūnės yra gretimos ir 0 – priešingu atveju.

Neorientuoto grafo gretimumo matrica yra simetrinė, o orientuotojo – nesimetrinė. Gretimumo matricos i-ojoje eilutėje vienetukų skaičius yra lygus i-osios viršūnės laipsniui neorientuotojo grafo atveju ir išėjimo puslaipsniui – orientuotojo grafo atveju.

GRAFAI2

Metrinės grafo charakteristikos

Atstumas tarp viršūnių x ir y yra trumpiausios grandinės, jungiančios tas viršūnes, ilgis. Atstumą žymėsime simboliu d(x,y)

Viršūnės v ekscentricitetas – tai dydis, apskaičiuojamas pagal formulę:

t.y. ilgiausios grandinės nuo viršūnės iki likusių grafo viršūnių ilgis.

Grafo spindulys – tai skaičius, apibrėžiamas pateikta formule:

t.y. skaičius, lygus mažiausiam viršūnių ekscentricitetui.

Grafo skersmuo – tai skaičius, apibrėžiamas pateikta formule:

Šiuo metu Jūs matote 50% šio straipsnio.
Matomi 830 žodžiai iš 1645 žodžių.
Peržiūrėkite iki 100 straipsnių per 24 val. Pasirinkite apmokėjimo būdą:
El. bankininkyste - 1,45 Eur.
Įveskite savo el. paštą (juo išsiųsime atrakinimo kodą) ir spauskite Tęsti.
SMS žinute - 2,90 Eur.
Siųskite sms numeriu 1337 su tekstu INFO MEDIA ir įveskite gautą atrakinimo kodą.
Turite atrakinimo kodą?
Po mokėjimo iškart gausite atrakinimo kodą, kurį įveskite į laukelį žemiau:
Kodas suteikia galimybę atrakinti iki 100 straispnių svetainėje ir galioja 24 val.