Vikipedija

Grafas (matematika): Skirtumas tarp puslapio versijų

Naršyti istoriją interaktyviai
← Prieš tai darytas keitimasKitas pakeitimas →
Ištrintas turinys Pridėtas turinys
VizualusVikitekstas
S Atmestas 78.61.240.69 pakeitimas, grąžinta ankstesnė versija (Homobot keitimas)
Žyma: Atmesti
Pakeista straipsnio struktūra, akcentai, kai kurie terminai. Su tikslu sumažinti sąvokų skaičių, pašalinau kai kurias elementarias sąvokas (pvz., tuščiojo grafo). Kadangi ieškant papildomos literatūros angliškai kyla pavojus neteisingai išversti terminus iš lietuvių kalbos, kur nepamiršau, nurodžiau angliškus atitikmenis. Lietuviškos terminologijos laikiausi pagal vieną vėlesnių šaltinių, t.y., M. Bloznelio konspektus https://klevas.mif.vu.lt/~bloznelis/vadovelis/k2016.pdf
Eilutė 1:
{{kiti|grafas|}}
: ''Duomenų struktūra „grafas“ aprašyta straipsnyje [[grafas (duomenų struktūra)]]''
[[Matematika|Matematikoje]], tiksliau [[grafų teorija|grafų teorijoje]], '''grafas''' yra abstrakti struktūra aprašantį rinkinį objektų, kuriame kai kurios poros susietos ryšiais. Objektus abstrakčiai aprašantys elementai vadinami ''viršūnėmis'' (angl. ''vertex'', dgs. vertices), kartais — ''mazgais'' (angl. ''node'') arba ''taškais'' (angl. ''points''). Susietos poros vadinamos ''briaunomis'', kartais — ''ryšiais'' (angl. ''link'') arba ''linijomis'' (angl. ''line'')''.'' Plokštumoje grafo viršūnės dažnai vaizduojamos taškais ar kitais paprastomis geometrinėmis figūromis, o briaunos — kreivėmis arba atkarpomis, jungiančiomis tuos taškus. Briaunos gali būti neorientuotos arba orientuotos (pastaruoju atveju jos dažnai vaizduojamos rodyklėmis).
[[Matematika|Matematikoje]] bei [[Informatika|informatikoje]] grafas – tam tikrų objektų (''viršūnių''), sujungtų ''briaunomis'' ir/arba ''lankais'', rinkinys.
 
Neorientuoto grafo pavyzdžiu gali būti grupė žmonių, kurioje briauna sujungiame kiekvieną porą žmonių pažįstančių vienas kitą. Kadangi pažintis yra simetriškas sąryšis (žmogus A pažįsta žmogų B tada ir tik tada, kai žmogus B pažįsta žmogų A), šis grafas yra neorientuotas. Kita vertus, jei briaunomis laikytume sutvarkytas poras (A,B), kur žmogus A yra skolingas žmogui B, gautume orientuotą grafą, kadangi iš to, kad A skolingas žmogui B, neišplaukia, jog B skolingas žmogui A.[[Vaizdas:BekryptisGrafas.png|thumb|100px|right|Grafas su viršūnėmis V = {1,2,3,4,5} ir briaunomis E = <nowiki>{{1,2}, {1,3}, {1,5}, {2,3}, {3,4}, {3,5}, {4,5}}</nowiki>]]
Grafus tiria [[grafų teorija]].
[[Vaizdas:BekryptisGrafas.png|thumb|100px|right|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ėžimasGrafų apibrėžimai ==
 
GrafuAbstrakčiai vadinsimegrafas porą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ė (paprastai porose elementų tvarka nesvarbi). Aibės ''<math>V</math>'' 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.
 
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'''.
== Terminai ==▼
 
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ė.
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'''.
 
Galiausiai, kai kada patogu leisti briaunas ar lankus kurie jungia viršūnę su pačia savimi. Formaliai, šiuo atveju leidžiama briaunas pavidalo <math>\{v,v\}</math> ir lankus pavidalo <math>(v,v)</math>. Tokias briaunas ir lankus vadiname '''kilpomis''', o (di)grafus, kuriuose leidžiamos kilpos vadiname (di)grafais su kilpomis (angl. ''looped (di)graph, (di)graph with loops'').
 
▲== Terminai ==
 
Dvi grafo viršūnės yravadinamos gretimos'''gretimomis''' (angl. ''adjacent''), jeikai jas jungia briauna (lankas). Turėdami briauną <math>\{u, v\} (lanką\in E</math> (u,v)), sakome, kad viršūnės <math>u</math> ir <math>v</math> '''incidenčios''' (angl. ''incident'') briaunai <math>\{u, v\} (lankui (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.
Neorientuotas grafas vadinamas [[Pilnasis grafas|pilnuoju]], jei kiekviena jo viršūnė briaunomis sujungta su visomis likusiomis (n viršūnių pilnasis grafas paprastai žymimas K<sub>n</sub>). 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.
 
'''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'').
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.
 
Grafas <math>G' = (V',E')</math> vadinamas grafo <math>G = (V,E)</math> '''pografiu''' (angl. ''subgraph''), jei <math>V' \subseteq V</math> ir <math>E' \subseteq E</math>. Pografį <math>G'</math> vadiname '''indukuotuoju''', (angl. ''induced'') jei į <math>E'</math> įeina visos grafo <math>G = (V,E)</math> briaunos jungiančios aibės <math>V'</math> elementus. Kadangi kiekvieną indukuotą pografį vienareikšmiškai apibrėžia jo viršūnių aibė <math>V'</math>, todėl indukuotą pografis su viršūnių aibe <math>V'</math> žymime <math>G[V']</math>.
Grafo '''grandine''' vadinama briaunų (lankų) seka (v<sub>0</sub>, v<sub>1</sub>), (v<sub>1</sub>, v<sub>2</sub>), …, (v<sub>n-1</sub>, v<sub>n</sub>). 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.
 
Neorientuotas grafas yra '''jungus''' (angl. ''connected''), jei kiekvieną porą skirtingų viršūnių <math>u, v</math> jungia kelias (pastebėkime, kad grafas su viena viršūne taip pat yra jungus). Bet kurio grafo <math>G</math> viršūnių aibę galima vieninteliu būdu išskaidyti į netuščias aibes <math>V_1, \dots, V_n</math> taip, kad pografiai <math>G[V_1], \dots, G[V_n]</math> būtų jungūs. Šie pografiai vadinami grafo <math>G</math> '''jungiosiomis komponentėmis.'''
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.
 
Jei digrafe kiekvienai skirtingų viršūnių porai <math>u, v</math> egzistuoja orientuotas kelias iš <math>u</math> į <math>v</math>, toks digrafas vadinamas '''stipriai''' '''jungiuoju''' (angl. ''strongly connected'').
Neorientuotas grafas yra '''jungus''' (arba rišlus), jei kiekvieną jo viršūnių porą jungia grandinė.
Grafo G didžiausias indukuotas pografis (toks, kurio negalima praplėsti, taip, kad pografis liktų jungus) vadinamas jungiąja komponente.
 
Viršūnių aibė <math>U \subseteq V</math> vadinama '''nepriklausoma''' (angl. independent) arba '''stabilia''' (angl. stable), jei tarp viršūnių <math>U</math> nėra briaunų (t. y. <math>G[U]</math> briaunų skaičius lygus <math>0</math>). Neorientuotasis grafas vadinamas '''dvidaliu''' (angl. ''bipartite''), jei jo viršūnių aibę galima išskaidyti į dvi nepriklausomas aibes <math>V_1</math>, <math>V_2</math>. Bendriau, kiekvienam <math>k \ge 2</math> grafas vadinamas <math>k</math>-'''daliu''' (angl. <math>k</math>-''partite''), jei jei jo viršūnių aibę galima išskaidyti į nepriklausomas aibes <math>V_1, \dots, V_k</math>.
Orientuoti grafai gali būti '''stipriai''', '''vienakryptiškai''' ir '''silpnai jungūs''' arba nejungūs.
 
{{Commonscat|Graphs (graph theory)}}
Rodomas puslapis "https://lt.wikipedia.org/wiki/Grafas_(matematika)"