Graafikute tüübid andmestruktuuris koos näidetega

Graaf on mittelineaarne andmestruktuur, mis koosneb tippudest ja servadest. Tippudes on teave või andmed ja servad toimivad ühenduslülina tippude paari vahel.

Graafikud võivad olla mitut tüüpi, olenevalt sõlmede ja servade asukohast. Siin on mõned olulised graafikute tüübid:

Suunatud graafik

Suunatud graafiku servad sisaldavad nooli, mis tähistavad suunda. Nool määrab, kuhu serv osutab või kus see lõpeb. Siin on näide suunatud graafikust.

Suunatud graafik

• Võime minna sõlmest A punkti D.
• Siiski ei saa me minna sõlmest D sõlme A, kuna serv osutab punktist A punkti D.
• Kuna graafikul pole kaalusid, maksab sõit tipust A punkti D sama palju kui sõitmine punktist D punkti F.

Suunamata graafik

Suunamata graaf sisaldab servi ilma pointeriteta. See tähendab, et me saame liikuda kahe tipu vahel vastupidi. Siin on lihtne näide suunamata graafist.

Suunamata graafik

Ülaltoodud graafikul

• Me saame liikuda punktist A punkti B.
• Samuti saame liikuda punktist B punkti A.
• Servad ei sisalda juhiseid.

See on näide suunamata graafist, millel on lõplik arv tippe ja servi ilma kaaludeta.

Kaalutud graafik

Graafi, mille servadel on kaalud või kulud, nimetatakse kaalutud graafiks. Numbriline väärtus esindab üldiselt ühest tipust teise liikumise kulu. Nii suunatud kui ka suunamata graafidel võivad olla servadel kaalud. Siin on näide kaalutud graafist (suunatud).

Suunatud graafik kaaluga

• Punktist A punkti B liikudes on eelis ja kaal on 5, mis tähendab, et punktist A punkti B liikumine maksab meile 5.
• A osutab B-le, aga selles graafikus pole B-l A suhtes otsest serva. Seega me ei saa reisida B-st A-sse.
• Kui aga tahame liikuda punktist A punkti F, on selleks mitu teed. Teed on ADF ja ABF. ADF maksab (10+11) ehk 21.
• Siin maksab tee ABF (5 + 15) ehk 20. Siin liidame iga tee serva kaalu.

Siin on näide suunamata graafist kaaludega:

Suunamata graafik kaaluga

Siin on serval kaal, kuid puudub suund. Niisiis, see tähendab, et reisimine tipust A punkti D maksab 10 ja vastupidi.

Kahesuunaline graafik

Kahesuunalistel ja suunamata graafikutel on üks ühine omadus. See on:

• Üldiselt võib suunamata graafil olla üks serv kahe tipu vahel.

Näiteks:

• Siin maksab A-st D-sse või D-sse A kolimine 10.
• Kahesuunalises graafikus võib kahe tipu vahel olla kaks serva.

Siin on näide:

Kahesuunaline graafik

Punktist A punkti D reisimine maksab meile 17, aga punktist D punkti A reisimine maksab meile 12. Seega ei saa me määrata kahte erinevat kaalu, kui tegemist on suunamata graafiga.

Lõputu graafik

Graafik sisaldab lõpmatut arvu servi ja sõlmi. Kui graaf on lõpmatu ja samal ajal ka ühendatud graaf, siis sisaldab see samuti lõpmatut arvu servi. Siin tähendavad laiendatud servad seda, et nende sõlmedega võib servade kaudu olla ühendatud rohkem servi. Siin on näide lõpmatust graafist:

Lõputu graafik

Nullgraafik

Nullgraaf sisaldab ainult sõlmi või tippe, kuid ilma servadeta. Kui on antud graaf G = (V, E), kus V on tipud ja E on servad, on see null, kui servade arv E on null. Siin on näide nullgraafist:

Nullgraafik

Triviaalne graafik

Graafi andmestruktuuri peetakse triviaalseks, kui sellel on ainult üks tipp või sõlm ja servad puuduvad. Siin on näide triviaalsest graafist:

Mitu graafikut

Graafi nimetatakse multigraafiks, kui kahe tipu vahel on mitu serva või kui tipus on tsükkel. Mõiste „tsükkel” graafi andmestruktuuris tähendab serva, mis osutab samale sõlmele või tipule. Multigraaf võib olla suunatud või suunamata. Siin on näide multigraafist:

Punktist B punkti A viib kaks serva. Lisaks on tipul E isesilmus. Ülaltoodud graaf on suunatud graaf, mille servadel pole raskusi.

Täielik graafik

Graaf on täielik, kui igal tipul on kõigi teiste tippudega suunatud või suunamata servad. Oletame, et tippude arv on kokku V ja igal tipul on täpselt V-1 serva. Siis nimetatakse seda graafi täielikuks graafiks. Seda tüüpi graafis on iga tipp kõigi teiste tippudega servade kaudu ühendatud. Siin on näide täielikust graafist, millel on viis tippu:

Pildilt on näha, et sõlmede koguarv on viis ja kõigil sõlmedel on täpselt neli serva.

Ühendatud graafik

Graafi nimetatakse ühendatud graafiks, kui see alustab ühest sõlmest või tipust ja saab sellest sõlmest liikuda kõikidesse sõlmedesse. Selleks peaks iga sõlmede või tippude paari vahel olema vähemalt üks serv. Siin on näide ühendatud graafist:

Siin on ülaltoodud ühendatud graafiku selgitus:

• Eeldades, et C ja F vahel pole serva, ei saa me liikuda punktist A punkti G. Serv C ja F vahel võimaldab meil aga reisida antud sõlmest mis tahes sõlme.
• Täielik graafik on ühendatud graafik, kuna saame liikuda antud graafiku sõlmest mis tahes teise sõlme.

Tsükliline graafik

Graafi nimetatakse tsükliliseks, kui selles on üks või mitu tsüklit. Siin on näide tsüklilisest graafist:

Siin moodustavad tipud A, B ja C tsükli. Graafi sees võib olla mitu tsüklit.

Suunatud atsükliline graafik (DAG)

Graafi nimetatakse suunatud atsükliliseks graafiks ehk DAG-iks, kui graafi sees pole tsükleid. DAG on oluline järgmiste toimingute tegemisel: Topoloogiline sortimine või täitmisjärjekorra leidmiseks. DAG on oluline ka ajastamissüsteemide loomiseks või ressursside sõltuvuse skaneerimiseks jne. Ülaltoodud graafik ei sisalda aga ühtegi sees olevat tsüklit. Siin on lihtne näide suunatud atsüklilisest graafist (DAG):

Tsükligraafik

Tsükligraaf ei ole sama mis tsükliline graaf. Tsükligraafis on igal sõlmel täpselt kaks ühendatud serva, mis tähendab, et igal sõlmel on täpselt kaks kraadi. Siin on näide tsükligraafist:

Kahepoolne graafik

Sellised Graafikud on spetsiaalsed graafitüübid, kus tipud on määratud kahte hulka. Kaheosaline graaf peab järgima reeglit:

• Kaks tippude komplekti peaksid olema erinevad, mis tähendab, et kõik tipud tuleb jagada kahte rühma või komplekti.
• Samasse hulpi kuuluvad tipud ei tohiks moodustada servi.

Euleri graafik

Graafi andmestruktuuri peetakse Euleri graafiks, kui kõigil tippudel on paarisarv aste. Termin "tippude aste" tähendab servade arvu, mis osutavad konkreetsele tipule või osutavad sellest välja. Siin on näide Euleri graafist:

Kõigil tippudel on paarisarv kraadi. Tippudel A, D, E ja H on kaks kraadi. Siin on sõlmel C neli kraadi, mis on paarisarv.

Hamiltoni graafik

Hamiltoni graaf on ühendatud graaf, kus saab külastada kõiki antud tipu tippe ilma sama sõlme uuesti külastamata või sama serva kasutamata. Sellist ühendatud graafi nimetatakse Hamiltoni graafiks. Tee, mida läbitakse, et kontrollida, kas antud graaf on Hamiltoni graaf või mitte, nimetatakse Hamiltoni teeks. Siin on lihtne näide Hamiltoni graafist:

Sellel pildil saame külastada kõiki tippe ülaltoodud graafiku mis tahes sõlmest. Üks teedest võib olla ADCHBESamuti on võimalik leida Hamiltoni tsükkel. Hamiltoni tsükkel algab ja lõpeb samas tipus. Seega on Hamiltoni tsükkel ADCHBEA.

KKK