Grafas (matematika)

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.

Duomenų struktūra „grafas“ aprašyta straipsnyje grafas (duomenų struktūra)

Matematikoje bei kompiuterių moksluose grafas – tam tikrų objektų (viršūnių), sujungtų lankais, rinkinys. Lankai gali turėti kryptį arba būti bekrypčiais, taip pat lankams gali būti priskirtas svoris.

Grafus tiria grafų teorija.

Turinys 1 Apibrėžimai 1.1 Populiariausias apibrėžimas 1.2 Alternatyvus apibrėžimas 2 Terminai 3 Teoremos

[taisyti] Apibrėžimai

[taisyti] Populiariausias apibrėžimas

Tarkime, V – netuščia aibė (viršūnių), E – visų aibės V galimų dvielemenčių poaibių aibė (visų įmanomų briaunų aibė), U – bet koks aibės E poaibis (briaunų aibė). Grafu vadinama pora (V, U), t.y. G =(V, U).

[taisyti] Alternatyvus apibrėžimas

Grafu vadinamas rinkinys G=(V, Γ), kur

• V – netuščia aibė (viršūnių);
• Γ – aibės V atvaizdis į V.

Apibrėžimas pateiktas C. Berge knygoje Theory des Graphes et ses applications (1958 m.).

[taisyti] Terminai

Grafai, kuriuose briaunos turi kryptis, vadinami orientuotaisiais grafais. Šiuo atveju briaunos vadinamos lankais. Grafai vadinami mišriaisiais, jei jie turi briaunų (jomis vadinsime grafo krašines, kurių nenurodyta kryptis) ir lankų. Jei bet kurias dvi grafo viršūnes jungia daugiausiai vienas lankas, tai paprastasis grafas, kitaip – multigrafas. Grafas, kuriame galimi ciklai arba galimas lankas, jungiantis viršūnę su pačia savim, vadinamas pseudografu.

Lankai (briaunos) vadinami gretimais, jei jie turi bendrą viršūnę. Viršūnės yra gretimos, jei jas jungia vienas lankas (briauna). Turėdami lanką (briauną) (u, v), galime teigti, kad viršūnės u ir v incidentiškos lankui (briaunai) (u, v).

Neorientuotas grafas vadinamas pilnuoju, jei kiekviena jo viršūnė briaunomis sujungta su visomis likusiomis (n viršūnių pilnasis grafas paprastai žymimas K_n). Grafas, neturintis lankų (briaunų), vadinamas tuščiuoju ir atitinkamai žymimas O_n. Neorientuotasis grafas vadinamas dvidaliu, jei jo viršūnių aibę galima išskaidyti į dvi aibes A ir B tokias, kad kiekvienos jo briaunos skirtingi kraštai 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 puslaipsniai. Neorientuotasis grafas yra reguliarusis, jei jo visų viršūnių laipsniai yra lygūs.

Grafo grandine vadinama briaunų (lankų) seka (v₀, v₁), (v₁, v₂), ..., (v_n-1, v_n). 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 daliniu grafui G, jei H ir G viršūnių aibė sutampa, o H briaunų aibė yra mažesnės galios G briaunų aibės poaibis. Grafas H vadinamas grafo G pografiu, jei H viršūnių aibė yra mažesnės galios G viršūnių aibės poaibis ir H briaunų aibę sudaro visos G briaunų aibės briaunos, kurių abu galai priklauso H viršūnių poaibiui. Grafo G jungioji komponentė – G pografis, kurį indukuoja tarpusavy sujungtos G viršūnės. Neorientuotas grafas yra jungus (arba rišlus), jei jį sudaro vienintelė jungioji komponentė. Orientuoti grafai gali būti stipriai, vienakryptiškai ir silpnai jungūs arba nejungūs.

[taisyti] Teoremos

Jungus neorientuotas grafas su N viršūnių turi ne mažiau kaip N-1 briauną 

Reikia prisiminti, kad jungiame grafe egzistuoja kelias tarp bet kurių dviejų viršūnių. Tarkime, pasirenkame viršūnę ir sujungiame ją briauna su kita viršūne: 2 viršūnės ir 1 briauna; jei pridedama dar vieną viršūnę, būtina ir papildoma briauna jai prijungti prie bet kurios kitos grafo viršūnės.

Jungus neorientuotas grafas su N viršūnių ir N-1 briauna negali turėti ciklų 

Pagal ankstesnę savybę orientuotas grafas su N viršūnių privalo turėti ne mažiau kaip N-1 briauną, kad būtų jungus. Jei jungus grafas turi ciklą, galima pašalinti bet kurią briauną iš ciklo ir grafas liks jungus. Taigi, jei grafas su N viršūnių ir N-1 briauna turės ciklą, galima bus pašalinti vieną briauną ir gautas grafas su N-2 briauna turi likti jungus, kas prieštarauja ankstesnei savybei.

Jungus neorientuotas grafas su N viršūnių ir daugiau kaip N-1 briauna turi bent vieną ciklą 

Paimkime jungų neorientuotą grafą su N viršūnių ir N-1 briauna. Pasirinkime bet kokią porą viršūnių X ir Y ir pridėkime naują briauną B, jungiančią viršūnes X ir Y. Kadangi pradinis grafas buvo jungus, tai jame egzistavo kelias iš viršūnės X į viršūnę Y. Pridėjus prie šio kelio naują briauną B, gaunamas ciklas, t.y. kelią iš viršūnės X į ją pačią.