Grafas (matematika): Skirtumas tarp puslapio versijų
Ištrintas turinys Pridėtas turinys
S Pusiau automatinis straipsnių be šaltinių datavimas |
S Automatizuotas santrumpų taisymas. |
||
Eilutė 11:
Abstrakčiai grafas apibrėžiamas kaip pora <math>G = (V,E)</math>, kur <math>V</math> — kokia nors aibė, o <math>E</math> — aibės ''<math>V</math>'' elementų porų aibė. Aibės ''<math>V</math>'' elementai vadinami grafo ''G'' '''viršūnėmis''', o aibės E elementai — '''briaunomis'''.
Dažnai naudinga briaunoms priskirti kryptis, t. y., briauną <math>\{u,v\}</math> pakeisti sutvarkyta pora <math>(u,v)</math>, kurią vadiname ''lanku'' (angl. ''arc''). Šiuo atveju gauname struktūrą vadinamą '''orientuotuoju grafu''' arba '''digrafu'''.
Grafo sąvoką galima apibendrinti leidžiant kartotines briaunas. '''Multigrafu vadinama pora <math>G = (V,E)</math>''', kur <math>E</math> yra ''<math>V</math>'' elementų porų ''multiaibė''. Analogiškai <math>G = (V,A)</math> yra '''multidigrafas''', jei ''<math>A</math>'' yra sutvarkytų porų iš ''<math>V</math>'' multiaibė.
Eilutė 21:
Dvi grafo viršūnės vadinamos '''gretimomis''' (angl. ''adjacent''), kai jas jungia briauna. Turėdami briauną <math>\{u,v\} \in E</math> , sakome, kad viršūnės <math>u</math> ir <math>v</math> '''incidenčios''' (angl. ''incident'') briaunai <math>\{u,v\}</math>.
(Multi)grafo viršūnės <math>v</math> '''laipsnis''' (angl. ''degree''), žymimas <math>\deg_G(v)</math>, yra briaunų, incidenčių viršūnei <math>v</math>, skaičius. Digrafe <math>G=(V,A)</math> '''išėjimo laipsniu''' (angl. ''out-degree'') <math>\deg^+_G(v)</math> vadinamas skaičius lankų vedančių iš <math>v</math> (t. y., <math>(v,u)\in A</math>); analogiškai '''įėjimo laipsniu''' (angl. ''in-degree'') <math>\deg^-_G(v)</math> vadinamas skaičius lankų vedančių į <math>v</math> (t. y., <math>(u,v)\in A</math>). Grafas vadinamas '''reguliariuoju''' (angl. ''regular''), jei jo visų viršūnių laipsniai yra lygūs.
'''Keliu''' (angl. ''walk'') (multi)grafe vadinama seka <math>v_0, e_1, v_1, \dots, e_n, v_n </math>, kurioje <math>v_0, \dots, v_n</math> yra viršūnės, o <math>e_1, \dots, e_n</math> yra briaunos, kur briauna <math>e_i</math> jungia viršūnes <math>v_{i-1}</math> ir <math>v_i</math> (jei digrafe reikalaujame, kad <math>e_i</math> yra lankas iš <math>v_{i-1}</math> į <math>v_i</math>, tokį kelią vadiname '''orientuotuoju keliu''', angl. ''oriented walk''). Jei grafe nėra kartotinių briaunų, kiekvieną kelią vienareikšmiškai apibrėžia viršūnių seka <math>v_0, \dots, v_n</math>. Kelias, kuriame nesikartoja briaunos, vadinamas '''grandine''' (angl. ''trail''). Grandinė, kurioje nesikartoja viršūnės, vadinama '''taku''' (angl. ''path'').
| |||