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 bbent 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ų vviršū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, ., vvk). 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 ppriklauso 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 yy 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:

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

Skersmens ilgio grandinė, jungianti bet kurias dvi periferines grafo viršūnes, vadinama skersmens grandine.

Viršūnės, kurių ekscentricitetas lygus spinduliui, vadinamos centro viršūnėmis.

Aibė, kurią sudaro centro viršūnės, vadinama grafo centru.

Viršūnės, kurių ekscentricitetas lygus skersmeniui, vadinamos periferinėmis viršūnėmis.

Svorinis grafas – grafas, kurio kiekvienai briaunai priskirtas skaičius, vadinamas briaunos svoriu.

Briaunos svorį traktuosime kaip atstumą tarp gretimų viršūnių.

Svorinio grafo grandinės ilgis – tai grandinę sudarančių briaunų svorių suma.

Atstumas tarp svorinio grafo viršūnių x ir y, tai trumpiausios grandinės, jungiančios šias viršūnes, ilgis.

Viršūnės šalinimas. Duotas grafas G(V,U). Pašalinti viršūnę x, tai iš grafo pašalinti šią viršūnę drauge su jai incidentinėmis briaunomis.

Briaunos (v1,v2) šalinimas. Iš grafo G(V,U) šalinama briauna (v1, v2). Gaunamas grafas, turintis tą pačią viršūnių aibę V ir briaunų aibę U*=U{(v1,v2)}

Viršūnių sutapatinimas. Tarkime, kad v1 ir v2 grafo G(V,U) viršūnės. Viršūnių v1 ir v2 sutapatinimas atliekamas taip:

1) Iš grafo G pašalinamos viršūnės v1 ir v2;

2) Įveama nauja viršūnė v;

3) Viršūnė v jungiama bbriaunomis su tomis viršūnėmis, kurios buvo gretimos arba viršūnei v1, arba viršūnei v2, t.y. N(v)=N(v1)ÈN(v2).

Briaunos sutraukimas. Tarkime (v1,v2) yra grafo G(V,U) briauna. Tada briaunos (v1,v2) sutraukimas, tai gretimų viršūnių v1 ir v2 sutapatinimas.

Viršūnės išskaidymo operacija. Tarkime v yra viena iš grafo G viršūnių ir N(v)=AÈB, AÇB=Æ. Tada viršūnės išskaidymo operacija atliekama taip:

1) Iš grafo G pašalinama viršūnė v;

2) Įvedamos dvi naujos viršūnės v1 ir v2 ir jas jungiančioji briauna.

3) Viršūnė v1, jungiama su aibės A viršūnėmis, o v2-su aibės B viršūnėmis.

Grafų sąjunga. Tarkime duoti grafai G1=(V1,U1) ir G2=(V2,U2). Tada grafas G=(V,U) yra šių grafų sąjunga (žymime G=G1ÈG2), jei V=V1 ÈV2, o U=U1 ÈU2. Jei V1ÇV2=Æ, tai grafų G1 ir G2 sąjunga vadinama disjunktyvinė sąjunga.

Grafų sandauga. Grafų G1=(V1,U1) ir G2=(V2,U2) sandaugos grafas G =(V,U) (žymime G=G1xG2) apibrėžiamas taip:

1) V=V1xV2 – aibių Dekarto sandauga;

2) Viršūnė (a,b) jungiama su viršūne (c,d), jeigu a=с ir (b,d)ÎU2 arba b=d ir (a,c)ÎU1.

Grafo viršūnių skaičius yra lygus V=|V1|*|V2|, o U=|V1|*|U2|+|V2|*|U1|.

GRAFAI3

Veiksmai su grafais

Papildomas grafas. Grafas H=(V,UH) yra grafo G=(V,UG) papaildomas grafas, jei GÈH=Kn, čia n=|V|, tai yra grafas, papildantis grafą G iki pilnojo.

Briaunainis grafas. Grafo G(V,U) briaunainis grafas H=(A,B) apibrėžiamas taip:

1) Viršūnių aibės A elementų skaičius yra lygus grafo G briaunų skaičiui, t.y. kiekviena grafo viršūnė vaizduoja (atitinka) grafo G

briauną.

2) Viršūnės a1ÎA ir a2 ÎA jungiamo briauna, jeigu toms viršūnėms atitinkančios grafo briaunos yra gretimos.

Jei d1,d2, .., dn yra (n,m) – grafo G viršūnių laipsnių seka, tai jo briaunainis grafas H yra (m,l) – grafas, čia

Grafų izomorfiškumas

Grafai G(VG,UG) ir H(VH, UH) yra izomorfiniai, jei

1) |VG|=|VH|,

2) |UG|=|UH| ir

3) yra toks aibės VG atvaizdis (bijekcija) j į aibę VH, kad, jie v1 ir v2 yra gretimos grafo G viršūnės, tai j (v1) ir j (v2) yra gretimos grafo H viršūnės.

Žymėtieji grafai, jei kiekvienai grafo vviršūnei priskiriama žymė, pvz., {1,2,..n}

Du žymėtieji grafai yra izomorfiniai, jei galima vieno grafo viršūnes pernumeruoti taip, kad abiejų grafų briaunų aibės sutaptų.

Grafų vaizdavimas incidencijų matrica

(n,m) – grafo G=(V,U) incidencijų matrica yra stačiakampė (n x m) formato matrica A=х[aij], i=1,n, j=1,m ir jos elementas aij neorientuoto grafo atveju apibrėžiamas taip:

Grafų vaizdavimas briaunų matrica

Briaunų (lankų) matrica. (2 x m) formato matrica B vadinamas briaunų (lankų) matrica, jei (b1j, b2j), j=1,m yra j-oji grafo briauna (lankas).

Orientuoto grafo atveju b1j žymi j-ojo llanko pradžią, o b2j – j-ojo lanko pabaigą.

Grafų vaizdavimas gretimumo struktūra

Gretimumo struktūra – tai viršūnėms gretimų viršūnių aibių šeima. Vaizduojama:

1: {2,5};

2: {1,3}.

Oilerio grandinė (kelias) – grandinė, apeinanti visas grafo briaunas po vieną kartą.

Hamiltono grandinė (kelias)– grandinė, apeinanti visas grafo viršūnes ppo vieną kartą. Jei sutampa galinė ir pradinė viršūnės, tada turėsime Hamiltono ciklą.

Medžiai

Medžiai – jungieji grafai, neturintys nė vieno ciklo. Medžiuose yra tik vienas kelias tarp kiekvienos poros viršūnių.

Medžių pavyzdžiai: