Phenquestions
Vozlišče v grafu se imenuje oglišče (množina - oglišča). Včasih se še vedno imenuje vozlišče; lahko mu rečemo tudi točka. Povezava v grafu se imenuje rob. Včasih se še vedno imenuje povezava; lahko mu rečemo tudi črta.
Graf z veliko funkcijami
Ta slika prikazuje graf s številnimi funkcijami:
Krogi (diski) so oglišča. Vsaka ravna črta ali ukrivljena črta ali zanka je rob.
Značilnosti grafa
Vertex
Točka je objekt. Lahko je hiša; lahko je oseba; lahko je abstraktni samostalnik; lahko je kateri koli predmet, ki se ga spomnite.
Rob
Rob je povezava (relacija) med dvema točkama; povezava je lahko abstraktna.
Loop
Zanka je rob, ki povezuje točko s seboj.
Arrow Edge
Razmislite o dveh ljudeh: Janezu in Petru. Če John posodi Petru 100 ameriških dolarjev in če sta Janez in Peter točka, bo posojilni rob usmerjen proti Petru. Če oba partnerja pozabita, da je Peter dolžan Janezu, Peter pa mu posodi 100 dolarjev, bo na drugem koncu istega roba puščica usmerjena proti Janezu. Če bi Peter Janezu posodil le 75 dolarjev in ne 100 dolarjev, bi Peter z Johnom povezal drugačen rob. Ta drugi rob bo imel puščico usmerjeno proti Janezu. V drugem primeru sta dva roba, vsak s po eno puščico, usmerjen v nasprotni smeri.
Točka, na katero kaže rob, je glavna točka tega roba. Točka, iz katere zapusti rob, je repna točka.
Nezgoda
Rob povezuje dve točki. Rebel naj bi bil vpadljiv v obeh točkah. Na robu ni treba imeti puščice. Obe točki sta znani kot končni točki roba. Možno je, da imamo graf, kjer oglišče ne pripada nobenemu robu, vendar to ne bo upoštevano v tej vadnici.
Neusmerjeni graf
Rob je lahko puščica ali pa tudi ne. Graf, kjer noben rob ni puščica, je neusmerjen graf. Rob je lahko predstavljen z ravno črto ali krivuljo ali zanko.
Usmerjeni graf
Graf, kjer je vsak rob puščica (smer), je usmerjen graf. Rob puščice je lahko predstavljen z ravno črto s puščico ali krivuljo s puščico ali zanko s puščico.
Odsotnost smeri na robu neusmerjenega grafa pomeni, da je vsak rob neusmerjenega grafa dvosmeren.
Stopnja temena
Število robov, ki padajo na oglišče, je stopnja oglišča. Zanka ima dva vpada na oglišče, zato se zanka šteje dvakrat.
Vrstni red grafikona
Vrstni red grafa je število točk v grafu.
Multigraf
Multigraf je graf, kjer je za nekatere pare točk več robov. Neusmerjeni multigraf je tak graf, pri katerem robovi nimajo smeri (niso puščice). Usmerjeni multigraf je tisti, pri katerem je vsak rob puščica, pri parih točk, ki imajo več kot eno puščico, pa je ena točka rep teh puščic, druga točka pa glava istih puščic. Naslednji diagram prikazuje neusmerjen multigraf:
Več kot en rob (tj.e. več robov) za par točk imenujemo tudi vzporedni robovi.
Tobolec
Drhta je multigraf, ki omogoča zanke (eno ali več zank). Nekateri multigrafi ne dovoljujejo zank.
Preprost graf
Preprost graf je graf, pri katerem niti dva para točk nimata več robov. Zanke v preprostem grafu niso dovoljene.
Prazen graf
Prazen graf je graf brez oglišč in torej brez robov.
Mešani graf
Mešani graf je graf, kjer so nekateri robovi puščice, drugi pa ne; z drugimi besedami: nekateri robovi imajo smeri, drugi pa niso usmerjeni.
Uteženi graf
Možno je imeti graf, v katerem je vsakemu robu dodeljena številka, znana kot teža. Nekateri robovi imajo enako številko, vendar so številke na splošno različne. Tak graf imenujemo ponderirani graf. Številke za določen graf lahko predstavljajo dolžino ali stroške (cene) ali nekakšno velikost, odvisno od težave.
Nesoglasje in preseganje
Besedišče, stopnje in stopnje veljajo samo za usmerjeni graf. Graf je lahko multigraf ali pa tudi ne. Graf ima lahko zanke ali pa tudi ne.
Število puščic, povezanih z ogliščem, je stopnja te oglišča. Puščica z eno samo puščično glavo ima glavo in rep. Število repov, povezanih z ogliščem, je preseganje tega oglišča.
Opomba: Graf z več robovi za par točk, kjer so več robovi v nasprotnih smereh, v tej vadnici ni obravnavano.
Programska predstavitev grafa
Graf lahko v programski opremi predstavimo tako, kot je narisan na diagramu. Graf je lahko v programski opremi predstavljen tudi z matematično matriko (dvodimenzionalno polje). Ena od takih matrik se imenuje matrica sosednosti.
Matrika sosednosti
Matrika sosednosti je kvadratna matrica. Naslovi vrstic so vse točke, zapisane v naraščajočem vrstnem redu. Naslovi stolpcev so še vedno isti točki, napisani v naraščajočem vrstnem redu. Štetje vrstic ali stolpcev matrike se začne od 1 in ne od nič kot pri nizih. Ko identificiramo element v matriki, se številka vrstice zapiše najprej pred številko stolpca.
Za neusmerjeni graf je vsak vnos (element) v matrici sosednosti število robov, ki povezujejo dve ustrezni točki. Zanko je treba šteti dvakrat. Za usmerjeni graf je vsak vnos v matrici sosednosti bodisi število robov, ki zapustijo vrstico vrstice in vstopijo v ustrezno točko stolpca, ali je število robov, ki zapustijo točko stolpca in vstopijo v ustrezno vrstico vrstice. Izbira je programerja. V tem primeru (v obeh primerih) je zanko vseeno treba šteti enkrat.
Opomba: Graf je diagram je samostojna podatkovna struktura. Matrika sosednosti je tudi sama po sebi podatkovna struktura.
Neusmerjena grafika in matrica sosedstva
Naslednji diagrami prikazujejo neusmerjen graf in ustrezno matrico sosednosti:
Vodilna diagonala matrike je diagonala od zgoraj levo do spodaj desno. Neusmerjena matrica je simetrična glede vodilne diagonale. Vnos matrike za vrstico A in stolpec C je 1, kar pomeni, da obstaja en rob, ki povezuje oglišče A in oglišče C. Vnos matrike za vrstico C in stolpec B je 3, kar pomeni, da obstajajo 3 robovi, ki povezujejo točko C in točko B. Drugi vnosi so pojasnjeni podobno.
Vsota vnosov v vrstico določa število robov (stopinj) za ustrezno točko. Vsota vnosov za vrstico A je 2, kar pomeni, da sta dva roba povezana z ogliščem A. Vsota vnosov za vrstico B je 6, kar pomeni, da je 6 robov povezanih z ogliščem B. Preostali vnosi so pojasnjeni podobno.
Usmerjeni graf in matrica sosedstva
Naslednji diagrami kažejo usmerjeni graf in ustrezno matrico sosednosti:
Matrika sosednosti usmerjenega grafa ni nujno simetrična glede na vodilno diagonalo. Vnos matrike za vrstico A in stolpec C je 1, kar pomeni, da en rob zapusti točko A do točke C. Vnos matrike za vrstico C in stolpec B je 3, kar pomeni, da od roba C do oglišča B zapustijo 3 robovi. Drugi vnosi so pojasnjeni podobno.
Vsota vnosov v stolpec podaja stopnjo stopnje (stolpca). Vsota vnosov v vrstico določa preseg za (vrstico) oglišče. Vsota vnosov za stolpec A je 1, kar pomeni, da je en rob usmerjen v točko A. Vsota vnosov za vrstico B je 2, kar pomeni, da od roba B ostaneta 2 roba. Preostali vnosi so pojasnjeni podobno.
Grafične operacije
Podatkovna struktura, na primer graf, je sestavljena iz nabora podatkovnih vrednosti ali nabora predmetov, plus razmerja med predmeti in operacij (funkcij) med predmeti. Razmerja v grafu so označena z robovi. Pri tem bi moral graf imeti vsaj naslednje operacije:
sosednje (G, x, y)
G pomeni graf. Ta operacija preveri, ali rob povezuje oglišče x in oglišče y. Vrednost in položaj vnosa v matriki kažeta na povezavo roba (in njegovega tipa).
sosedje (G, x)
Ta operacija vrne seznam vseh točk, ki so neposredno povezane z točko x. Vrednost in položaj vnosa v matriki označujeta povezavo roba.
remove_vertex (G, x)
Ta operacija odstrani točko x iz grafa. Če oglišče ni imelo roba, ni problema. Če pa je imela oglišče povezave, je treba odstraniti tudi povezave (robove). Vrednost in položaj vnosa v matrici kažeta na prisotnost določene točke. Če je oglišče odstranjeno, je treba matriko prilagoditi.
add_vertex (G, x)
To doda točko x brez dodajanja robov ali nadomesti oglišče, ki je imelo robove, vendar je bilo odstranjeno. Vrednost in položaj vnosa v matriki kažeta na prisotnost določene točke. Če je dodana točka, je treba matriko prilagoditi.
add_edge (G, x, y)
Ta operacija doda nov rob med točko x in točko y, če roba ni bilo. Vrednost in položaj vnosa v matriki kažeta na prisotnost določenega roba. Če je dodan rob, je treba matriko prilagoditi.
remove_edge (G, x, y)
S to operacijo bi odstranili rob med točko x in točko y, če bi bil rob tam. Vrednost in položaj vnosa v matriki kažeta na prisotnost določenega roba. Če je rob odstranjen, je treba matriko prilagoditi.
get_vertex_value (G, x)
Ta operacija vrne vrednost, v, povezano z ogliščem, x. Da bi to dosegli, potrebujete nabor podnaborov za oznake oglišč in njihove vrednosti.
set_vertex_value (G, x, v)
Ta operacija daje novo vrednost, v za vrednost, povezano z ogliščem, x. Da bi to dosegli, potrebujete nabor podnaborov za oznake oglišč in njihove vrednosti.
Nekateri grafi tudi vrednosti povezujejo z njihovimi robovi. Takšni grafi potrebujejo naslednje dodatne operacije:
get_edge_value (G, x, y)
Ta operacija vrne vrednost, v, povezano z robom, (x, y). Da bi to dosegli, potrebujete nabor podnaborov moči za robove in njihove vrednosti.
set_edge_value (G, x, y, v)
Ta operacija daje novo vrednost, v za vrednost, povezano z robom, (x, y). Da bi to dosegli, potrebujete nabor podnaborov moči za robove in njihove vrednosti.
Zaključek
Graf je množica točk, povezanih z robovi. Graf je lahko usmerjen ali usmerjen. Robovi so lahko neusmerjeni ali usmerjeni. Zanke so lahko prisotne ali pa jih v grafikonu ni. Kar se morate naučiti, je nastavitev, nastavitev moči in večnabor v povezavi z grafi. Po tem se morate naučiti različnih vrst grafov, kot so usmerjeni graf, navadni graf, celoten graf, dvodelni graf, graf turnirjev, graf omrežja pretoka itd.
Chrys
O avtorju
Krizanta Forcha
Odkrivalec integracije matematike iz prvih načel in sorodnih serij. Magister tehničnega izobraževanja, specializiran za elektroniko in računalniško programsko opremo. Univ. Dipl. Elektronika. Imam tudi znanje in izkušnje na magistrski ravni iz računalništva in telekomunikacij. Od 20.000 pisateljev sem bil 37. najboljši pisatelj na devarticles.com. Na teh področjih delam že več kot 10 let.
Ogled vseh objav
