Grafas (matematika)

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

Matematikoje, tiksliau grafų teorijoje, grafas – 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).

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.

Grafas su viršūnėmis V = {1,2,3,4,5} ir briaunomis E = {{1,2}, {1,3}, {1,5}, {2,3}, {3,4}, {3,5}, {4,5}}

Grafų apibrėžimai

redaguoti

Abstrakčiai grafas apibrėžiamas kaip pora  , kur   – kokia nors aibė, o   – aibės   elementų porų aibė. Aibės   elementai vadinami grafo G viršūnėmis, o aibės E elementai – briaunomis.

Dažnai naudinga briaunoms priskirti kryptis, t. y., briauną   pakeisti sutvarkyta pora  , kurią vadiname lanku (angl. arc).[1] Šiuo atveju gauname struktūrą vadinamą orientuotuoju grafu arba digrafu.

Grafo sąvoką galima apibendrinti leidžiant kartotines briaunas. Multigrafu vadinama pora  , kur   yra   elementų porų multiaibė. Analogiškai   yra multidigrafas, jei   yra sutvarkytų porų iš   multiaibė.

Galiausiai, kai kada patogu leisti briaunas ar lankus kurie jungia viršūnę su pačia savimi. Formaliai, šiuo atveju leidžiama briaunas pavidalo   ir lankus pavidalo  . 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).

Svoriniu grafu vadinamas toks grafas, kurio kiekvienai briaunai priskirta kažkokia skaitinė reikšmė (svoris).

Terminai

redaguoti

Dvi grafo viršūnės vadinamos gretimomis (angl. adjacent), kai jas jungia briauna. Turėdami briauną   , sakome, kad viršūnės   ir   incidenčios (angl. incident) briaunai  .

(Multi)grafo viršūnės   laipsnis (angl. degree), žymimas  , yra briaunų, incidenčių viršūnei  , skaičius. Digrafe   išėjimo laipsniu (angl. out-degree)   vadinamas skaičius lankų vedančių iš   (t. y.,  ); analogiškai įėjimo laipsniu (angl. in-degree)   vadinamas skaičius lankų vedančių į   (t. y.,  ). Grafas vadinamas reguliariuoju (angl. regular), jei jo visų viršūnių laipsniai yra lygūs.

Keliu (angl. walk) (multi)grafe vadinama seka  , kurioje   yra viršūnės, o   yra briaunos, kur briauna   jungia viršūnes   ir   (jei digrafe reikalaujame, kad   yra lankas iš   į  , tokį kelią vadiname orientuotuoju keliu, angl. oriented walk). Jei grafe nėra kartotinių briaunų, kiekvieną kelią vienareikšmiškai apibrėžia viršūnių seka  . Kelias, kuriame nesikartoja briaunos, vadinamas grandine (angl. trail). Grandinė, kurioje nesikartoja viršūnės, vadinama taku (angl. path).

Grafas   vadinamas grafo   pografiu (angl. subgraph), jei   ir  . Pografį   vadiname indukuotuoju, (angl. induced) jei į   įeina visos grafo   briaunos jungiančios aibės   elementus. Kadangi kiekvieną indukuotą pografį vienareikšmiškai apibrėžia jo viršūnių aibė  , todėl indukuotą pografis su viršūnių aibe   žymime  .

Neorientuotas grafas yra jungus (angl. connected), jei kiekvieną porą skirtingų viršūnių   jungia kelias (pastebėkime, kad grafas su viena viršūne taip pat yra jungus). Bet kurio grafo   viršūnių aibę galima vieninteliu būdu išskaidyti į netuščias aibes   taip, kad pografiai   būtų jungūs. Šie pografiai vadinami grafo   jungiosiomis komponentėmis.

Jei digrafe kiekvienai skirtingų viršūnių porai   egzistuoja orientuotas kelias iš   į  , toks digrafas vadinamas stipriai jungiuoju (angl. strongly connected).

Viršūnių aibė   vadinama nepriklausoma (angl. independent) arba stabilia (angl. stable), jei tarp viršūnių   nėra briaunų (t. y.   briaunų skaičius lygus  ). Neorientuotasis grafas vadinamas dvidaliu (angl. bipartite), jei jo viršūnių aibę galima išskaidyti į dvi nepriklausomas aibes  ,  . Bendriau, kiekvienam   grafas vadinamas  -daliu (angl.  -partite), jei jei jo viršūnių aibę galima išskaidyti į nepriklausomas aibes  .

Šaltiniai

redaguoti