Phenquestions
Graafi sõlme nimetatakse tipuks (mitmus - tipud). Mõnikord nimetatakse seda ikkagi sõlmeks; seda võib nimetada ka punktiks. Graafis olevat linki nimetatakse servaks. Mõnikord nimetatakse seda endiselt lingiks; seda võib nimetada ka jooneks.
Paljude funktsioonidega graafik
See joonis näitab paljude funktsioonidega graafikut:
Ringid (kettad) on tipud. Iga sirgjoon või kõverjoon või silmus on serv.
Graafiku omadused
Tipu
Tipp on objekt. See võib olla maja; see võib olla inimene; see võib olla abstraktne nimisõna; see võib olla ükskõik milline objekt, mida võite mõelda.
Edge
Serv on ühendus (suhe) kahe tipu vahel; seos võib olla abstraktne.
Loop
Silmus on serv, mis ühendab tipu iseendaga.
Nooleserv
Mõelgem kahele inimesele: Johannesele ja Peetrusele. Kui Johannes laenab Peetrusele 100 dollarit ja kui Johannes ja Peetrus on tipud, siis osutub laenamise serv Peetruse poole. Kui mõlemad partnerid unustavad, et Peter võlgneb Johnile võlgu, ja Peter laenab Johnile 100 dollarit, siis sama serva teises otsas osutab nooleots Johni poole. Kui Peter laenas Johnile 75 dollarit, mitte 100 dollarit, ühendaks Peterit Johannega hoopis teine serv. Sellel teisel serval on nooleots Johni poole. Teisel juhul on kaks serva, kummaski üks nooleots, mis on suunatud vastassuunas.
Tipp, millele serv osutab, on selle serva tiputipp. Tipp, millest serv lahkub, on sabatipp.
Intsident
Serv ühendab kahte tippu. Eeldatakse, et serv langeb mõlemale tipule. Serval ei pea olema nooleotsa. Neid kahte tippu nimetatakse serva lõpp-punktideks. Võimalik on graafik, kus tipp ei kuulu ühessegi serva, kuid seda selles õpetuses ei arvestata.
Suunamata graafik
Serv võib olla nool või mitte. Graaf, kus ükski serv pole nool, on suunamata graaf. Serva võib kujutada sirge või kõvera või silmusega.
Suunatud graafik
Graaf, kus iga serv on nool (suund), on suunatud graaf. Nooleserva võib kujutada noolepeaga sirgjoonega või noolepeaga kõveraga või noolepeaga silmusega.
Suuna puudumine suunamata graafi serval tähendab suunamata graafi iga serva kahesuunalist.
Tippu tipp
Tippu langevate servade arv on tipu aste. Silmusel on tipus kaks esinemissagedust, seega loetakse silmus kaks korda.
Graafiku järjekord
Graafiku järjestus on graafi tippude arv.
Multigraaf
Multigraaf on graafik, kus mõne tipupaari puhul on rohkem kui üks serv. Suunamata multigraaf on selline graafik, milles servadel pole suundi (pole nooli). Suunatud multigraaf on selline, kus iga serv on nool ja tippude paaride puhul, millel on rohkem kui üks nool, on üks tipp nende noolte saba ja teine tipp on samade noolte pea. Järgmine diagramm näitab suunamata multigraafi:
Rohkem kui üks serv (st.e. mitu serva) tippude paari puhul nimetatakse ka paralleelseteks servadeks.
Värisema
Värin on multigraaf, mis võimaldab silmusid (ühte või mitut silmust). Mõned multigraafid ei luba tsükleid.
Lihtne graafik
Lihtgraaf on graafik, kus kahel tipupaaril pole mitu serva. Silmused pole lihtsas graafikus lubatud.
Tühi graafik
Tühi graaf on graaf, millel pole tippe ja seega servi.
Segatud graafik
Segatud graaf on graafik, kus mõned servad on nooled ja teised mitte; teisisõnu: mõnel serval on suunad ja teised pole suunatud.
Kaalutud graafik
Võimalik on graafik, milles igale servale on määratud number, mida nimetatakse kaaluks. Mõnel serval on sama number, kuid numbrid on üldiselt erinevad. Sellist graafikut nimetatakse kaalutud graafiks. Konkreetse graafiku numbrid võivad sõltuvalt probleemist tähistada pikkust või kulusid (hindu) või mingisugust suurust.
Indegree ja Outdegree
Sõnavara, indegree ja outregree kehtivad ainult suunatud graafile. Graafik võib olla multigraaf või mitte. Graafikul võib olla silmuseid või mitte.
Tipuga ühendatud nooleotste arv on selle tipu astmevaba. Ühe nooleotsaga noolel on pea ja sabaots. Tipuga ühendatud sabade arv on selle tipu astmestik.
Märkus. Selles õpetuses ei käsitleta tipupaari jaoks mitme servaga graafikut, kus mitu serva on vastassuunas.
Graafiku tarkvara esitus
Graafikut saab tarkvaras kujutada nii, nagu see diagrammile joonistatakse. Graafikut saab tarkvaras kujutada ka matemaatilise maatriksiga (kahemõõtmeline massiiv). Üht sellist maatriksit nimetatakse külgnemismaatriksiks.
Adjacency Matrix
Külgnemismaatriks on ruutmaatriks. Ridade päised on kõik tipud, mis on kirjutatud kasvavas järjekorras. Veergude pealkirjad on endiselt samad tipud, mis on kirjutatud kasvavas järjekorras. Maatriksi ridade või veergude loendamine algab 1-st ja mitte nullist nagu massiivide puhul. Maatriksi elemendi tuvastamisel kirjutatakse rea number enne veeru numbrit.
Suunamata graafi puhul on iga külgnemismaatriksi kirje (element) kahe vastavat tippu ühendavate servade arv. Silmust tuleks lugeda kaks korda. Suunatud graafi korral on iga kirje külgnemismaatriksis kas servade arv, mis jätab rea tipu ja sisestab vastava veeru tipu, või on veergude tipust lahkuvate ja vastavasse rea tippu sisenevate servade arv. Valik on programmeerija oma. Selles olukorras (mõlemal juhul) tuleks silmus siiski üks kord kokku lugeda.
Märkus. Graaf on diagramm, mis on omaette andmestruktuur. Kõrvalmaatriks on ka omaette andmestruktuur.
Suunamata graafik ja kõrvalekalde maatriks
Järgmised diagrammid näitavad suunamata graafikut ja vastavat külgnemismaatriksit:
Maatriksi juhtdiagonaal on diagonaal ülevalt vasakult paremale alt paremale. Suunamata maatriks on sümmeetriline juhtdiagonaali suhtes. Rea A ja veeru C maatrikskirje on 1, mis tähendab, et tippu A ja tippu ühendab üks serv. Rea C ja veeru B maatrikskirje on 3, mis tähendab, et tippu C ja tippu B ühendavad kolm serva. Sarnaselt on selgitatud ka teisi kandeid.
Rea kirjete summa annab vastava tipu servade arvu (kraadi). Rea A kirjete summa on 2, mis tähendab, et tipuga A on ühendatud 2 serva. Rea B kirjete summa on 6, mis tähendab, et tipuga B on ühendatud 6 serva. Sarnaselt on seletatud ka ülejäänud kirjed.
Suunatud graafik ja adjacency maatriks
Järgmised diagrammid näitavad suunatud graafikut ja vastavat külgnemismaatriksit:
Suunatud graafi külgnemismaatriks ei pruugi juhtdiagonaali suhtes sümmeetriline olla. Rida A ja veeru C maatrikskirje on 1, mis tähendab, et üks serv lahkub tipust A tipuni C. Rida C ja veeru B maatriksikirje on 3, mis tähendab, et tipust C tipuni B lahkuvad 3 serva. Sarnaselt on selgitatud ka teisi kandeid.
Veeru kirjete summa annab (veeru) tipu indegree. Rea kirjete summa annab (rea) tipu outgree. Veeru A kirjete summa on 1, mis tähendab, et üks serv on suunatud tipule A. Rea B kirjete summa on 2, mis tähendab, et tipust B lahkub 2 serva. Sarnaselt on seletatud ka ülejäänud kirjed.
Graafiku toimingud
Andmestruktuur, näiteks graafik, koosneb andmeväärtuste komplektist või objektide komplektist, pluss objektide vaheline suhe, pluss objektide vahelised toimingud (funktsioonid). Graafiku seoseid tähistavad servad. Edasi peaks graafikul olema vähemalt järgmised toimingud:
külgnev (G, x, y)
G tähendab graafikut. Selle toiminguga kontrollitakse, kas serv ühendab tippu x ja tippu y. Maatriksi kirje väärtus ja asukoht näitavad serva (ja selle tüübi) ühendust.
naabrid (G, x)
See toiming tagastab loetelu kõigist tippudest, mis on otseselt ühendatud tipuga x. Maatriksi kirje väärtus ja asukoht näitavad serva ühendust.
remove_vertex (G, x)
See toiming eemaldab graafilt tipu x. Kui tipul polnud serva, pole probleemi. Kui tipul olid lingid, siis tuleks ka lingid (servad) eemaldada. Maatriksi sisestuse väärtus ja asukoht näitavad konkreetse tipu olemasolu. Kui tipp eemaldatakse, tuleb maatriksit uuesti reguleerida.
add_vertex (G, x)
See lisab tipu, x ilma servi lisamata, või asendab tipu, millel olid servad, kuid mis oli eemaldatud. Maatriksi kirje väärtus ja asukoht näitavad konkreetse tipu olemasolu. Kui lisatakse tipp, tuleb maatriksit uuesti reguleerida.
add_edge (G, x, y)
See toiming lisab tipu x ja tipu y vahele uue serva, kui seda serva ei olnud. Maatriksi sisestuse väärtus ja asukoht näitavad konkreetse serva olemasolu. Kui lisatakse serv, tuleb maatriksit uuesti reguleerida.
remove_edge (G, x, y)
See toiming eemaldaks tipu x ja tipu y vahelise serva, kui serv oleks olemas. Maatriksi sisestuse väärtus ja asukoht näitavad konkreetse serva olemasolu. Kui serv eemaldatakse, tuleb maatriksit uuesti reguleerida.
get_vertex_value (G, x)
See toiming tagastab tipuga seotud väärtuse v. Selle saavutamiseks vajate tippude siltide ja nende väärtuste jaoks alamhulkade komplekti.
set_vertex_value (G, x, v)
See toiming annab tipuga seotud väärtuse uue väärtuse v. Selle saavutamiseks vajate tippude siltide ja nende väärtuste jaoks alamhulkade komplekti.
Mõni graafik seob väärtused ka nende servadega. Sellised graafikud vajavad järgmisi täiendavaid toiminguid:
get_edge_value (G, x, y)
See toiming tagastab servaga seotud väärtuse v (x, y). Selle saavutamiseks vajate servade ja nende väärtuste alamhulkade komplekti.
set_edge_value (G, x, y, v)
See toiming annab uue väärtuse v servaga seotud väärtusele (x, y). Selle saavutamiseks vajate servade ja nende väärtuste alamhulkade komplekti.
Järeldus
Graaf on servadega ühendatud tippude kogum. Graafikut saab suunata või suunata. Servad võivad olla ühesuunas või suunata. Silmused võivad graafikus esineda või puududa. Mida peaksite järgmisena õppima, on graafikutega seotud komplekt, võimsus ja multiset. Pärast seda peaksite õppima erinevat tüüpi graafikuid, nagu orienteeritud graaf, tavaline graafik, täielik graafik, kahepoolne graafik, turniirigraafik, voogude graafik jne.
Chrys
Autori kohta
Chrysanthus Forcha
Matemaatika integreerimise avastaja esimestest põhimõtetest ja seonduvatest seeriatest. Tehnilise hariduse magistrikraad, spetsialiseerunud elektroonikale ja arvutitarkvarale. BSc Elektroonika. Samuti on mul teadmisi ja kogemusi magistriõppes arvutite ja telekommunikatsiooni alal. 20 000 kirjanikust olin devartiklite seas 37. parim kirjanik.com. Olen nendes valdkondades töötanud üle 10 aasta.
Kuva kõik postitused
