Phenquestions
Uzol v grafe sa nazýva vrchol (množné číslo - vrcholy). Niekedy sa stále nazýva uzol; dá sa to nazvať aj bodom. Odkaz v grafe sa nazýva okraj. Niekedy sa tomu hovorí odkaz; dá sa to nazvať aj čiara.
Graf s mnohými funkciami
Tento obrázok zobrazuje graf s mnohými funkciami:
Kruhy (disky) sú vrcholy. Akákoľvek rovná čiara alebo zakrivená čiara alebo slučka sú hranou.
Vlastnosti grafu
Vrchol
Vrchol je objekt. Môže to byť dom; môže to byť osoba; môže to byť abstraktné podstatné meno; môže to byť akýkoľvek objekt, na ktorý si spomeniete.
Hrana
Hrana je spojenie (vzťah) medzi dvoma vrcholmi; spojenie môže byť abstraktné.
Slučka
Smyčka je hrana, ktorá spája vrchol so sebou.
Šípková hrana
Zvážte dvoch ľudí: Jána a Petra. Ak Ján požičia Petrovi 100 dolárov a ak sú Ján a Peter vrcholy, potom pôžičková hrana bude smerovať k Petrovi. Ak obaja partneri zabudnú, že Peter dlhuje Johnovi, a Peter požičia Johnovi 100 dolárov, bude na druhom konci toho istého okraja ukazovať šípka smerom k Jánovi. Ak Peter požičal Johnovi iba 75 dolárov a nie 100 dolárov, potom by Petra a Jána spájala iná hranica. Táto druhá hrana bude mať šípku smerujúcu k Jánovi. V druhom prípade sú to dva okraje, z ktorých každý má jednu šípku smerujúcu do opačných smerov.
Vrchol, ku ktorému smeruje hrana, je vrchný vrchol pre túto hranu. Vrchol, z ktorého odchádza hrana, je chvostový vrchol.
Incident
Okraj spája dva vrcholy. Okraj sa hovorí, že dopadá na ktorýkoľvek vrchol. Okraj nemusí mať hrot šípky. Dva vrcholy sú známe ako koncové body okraja. Je možné mať graf, kde vrchol nepatrí k žiadnej hrane, ale na to sa v tomto tutoriále nebudeme venovať.
Neusmernený graf
Okrajom môže byť šípka, alebo nemôže. Graf, v ktorom žiadna hrana nie je šípkou, je neorientovaný graf. Okraj môže byť znázornený priamkou alebo krivkou alebo slučkou.
Nasmerovaný graf
Graf, v ktorom je každá hrana šípkou (smerom), je smerovaný graf. Okraj šípky môže byť reprezentovaný priamkou s hrotom šípky alebo krivkou s hrotom šípky alebo slučkou s hrotom šípky.
Absencia smeru na okraji neorientovaného grafu, znamená, že každá hrana neorientovaného grafu je obojsmerná.
Stupeň vrcholu
Počet hrán, ktoré dopadajú na vrchol, je stupeň vrcholu. Smyčka má na vrchole dva výskyty, takže sa počíta dvakrát.
Poradie grafu
Poradie grafu je počet vrcholov v grafe.
Multigraf
Multigraf je graf, kde pre niektoré páry vrcholov existuje viac ako jedna hrana. Neusmernený multigraf je taký graf, v ktorom okraje nemajú smery (nie sú šípky). Cielený multigraf je ten, kde každý okraj predstavuje šípku a pre páry vrcholov, ktoré majú viac ako jednu šípku, je jeden vrchol chvostom týchto šípok a druhý vrchol je hlavou rovnakých šípok. Nasledujúci diagram zobrazuje neorientovaný multigraf:
Viac ako jeden okraj (t.j.e. viac hrán) pre dvojicu vrcholov sa nazývajú aj rovnobežné hrany.
Toulec
Toulec je multigraf, ktorý umožňuje slučky (jednu alebo viac slučiek). Niektoré multigrafy neumožňujú cykly.
Jednoduchý graf
Jednoduchý graf je graf, v ktorom žiadne dva páry vrcholov nemajú viac okrajov. V jednoduchom grafe nie sú povolené slučky.
Prázdny graf
Prázdny graf je graf bez vrcholov a teda bez okrajov.
Zmiešaný graf
Zmiešaný graf je graf, v ktorom sú niektoré hrany šípky a iné nie; inými slovami: niektoré hrany majú smery a iné nie sú smerované.
Vážený graf
Je možné mať graf, v ktorom je každému okraju priradené číslo známe ako hmotnosť. Niektoré hrany majú rovnaké číslo, ale počty sa všeobecne líšia. Takýto graf sa nazýva vážený graf. Čísla pre konkrétny graf môžu predstavovať dĺžky alebo náklady (ceny) alebo veľkosť nejakého druhu, v závislosti od problému.
Indegree a Outgree
Slovná zásoba, indegree a outgree sú použiteľné iba pre smerovaný graf. Graf môže, ale nemusí byť multigraf. Graf môže, ale nemusí mať slučky.
Počet hrotov šípov pripojených k vrcholu je indegree daného vrcholu. Šíp s jediným hrotom šípu má predný a zadný koniec. Počet chvostov pripojených k vrcholu predstavuje vrchol tohto vrcholu.
Poznámka: V tomto výučbe sa nezaoberáme grafom s viacerými hranami pre pár vrcholov, kde sú viaceré hrany v opačných smeroch.
Softvérové znázornenie grafu
Graf je možné znázorniť v softvéri tak, ako je nakreslený na diagrame. Graf môže byť v softvéri znázornený aj matematickou maticou (dvojrozmerné pole). Jedna z takýchto matíc sa nazýva matica susednosti.
Matica susedstva
Matica susednosti je štvorcová matica. Nadpisy riadkov sú všetky vrcholy napísané vzostupne. Nadpisy stĺpcov sú stále rovnaké vrcholy napísané vzostupne. Počítanie riadkov alebo stĺpcov matice začína od 1 a nie od nuly ako pri poliach. Pri identifikácii prvku v matici sa číslo riadku napíše najskôr pred číslom stĺpca.
V prípade neusmerneného grafu je každá položka (prvok) v matici susedstva počet hrán spájajúcich dva zodpovedajúce vrcholy. Slučka by sa mala počítať dvakrát. Pre smerovaný graf je každá položka v matici susedstva buď počet hrán opúšťajúcich vrchol riadkov a vstupujúcich do zodpovedajúceho vrcholu stĺpca, alebo je počet hrán opúšťajúcich vrchol stĺpcov a vstupujúcich do zodpovedajúcich vrcholov riadkov. Voľba je na programátorovi. V tejto situácii (v obidvoch prípadoch) by sa slučka mala stále počítať raz.
Poznámka: Graf je diagram, ktorý predstavuje samostatnú dátovú štruktúru. Matica susednosti je tiež samostatná dátová štruktúra.
Neusmernený graf a matica susedstva
Nasledujúce diagramy zobrazujú neusmernený graf a zodpovedajúcu maticu susednosti:
Predná uhlopriečka matice je uhlopriečka zľava zhora doprava dole. Neusmernená matica je symetrická okolo prednej uhlopriečky. Položka matice pre riadok A a stĺpec C je 1, čo znamená, že existuje jedna hrana spájajúca vrchol A a vrchol C. Položka matice pre riadok C a stĺpec B je 3, čo znamená, že existujú 3 hrany spájajúce vrchol C a vrchol B. Podobne sú vysvetlené aj ďalšie záznamy.
Súčet položiek pre riadok udáva počet hrán (stupňov) pre zodpovedajúci vrchol. Súčet položiek pre riadok A je 2, čo znamená, že 2 hrany sú spojené s vrcholom A. Súčet položiek pre riadok B je 6, čo znamená, že 6 hrán je spojených s vrcholom B. Ostatné položky sú vysvetlené podobne.
Nasmerovaný graf a matica susedstva
Nasledujúce diagramy zobrazujú usmernený graf a zodpovedajúcu maticu susednosti:
Matica susednosti pre smerovaný graf nemusí byť nevyhnutne symetrická okolo prednej uhlopriečky. Položka matice pre riadok A a stĺpec C je 1, čo znamená, že jeden okraj odchádza z vrcholu A do vrcholu C. Položka matice pre riadok C a stĺpec B je 3, čo znamená, že 3 hrany zostávajú od vrcholu C po vrchol B. Podobne sú vysvetlené aj ďalšie záznamy.
Súčet položiek pre stĺpec dáva indegree pre vrchol (stĺpca). Súčet záznamov pre riadok dáva výsledok pre vrchol (riadku). Súčet položiek pre stĺpec A je 1, čo znamená, že jedna hrana je nasmerovaná na vrchol A. Súčet položiek pre riadok B je 2, čo znamená, že z vrcholu B zostávajú 2 hrany. Ostatné položky sú vysvetlené podobne.
Grafické operácie
Dátová štruktúra, napríklad graf, pozostáva z množiny údajových hodnôt alebo množiny objektov, plus vzťah medzi objektmi a operácie (funkcie) medzi objektmi. Vzťahy v grafe sú označené okrajmi. Graf by mal mať minimálne tieto operácie:
susedné (G, x, y)
G znamená graf. Táto operácia overuje, či hrana spája vrchol x a vrchol y. Hodnota a poloha záznamu v matici označujú spojenie hrany (a jej typ).
susedia (G, x)
Táto operácia vráti zoznam všetkých vrcholov, ktoré sú priamo spojené s vrcholom x. Hodnota a poloha záznamu v matici označujú spojenie hrany.
remove_vertex (G, x)
Táto operácia odstráni vrchol, x z grafu. Ak vrchol nemal hranu, nie je problém. Ak však vrchol mal odkazy, mali by sa tiež odstrániť odkazy (hrany). Hodnota a poloha záznamu v matici naznačujú prítomnosť konkrétneho vrcholu. Ak je vrchol odstránený, je potrebné maticu znova upraviť.
add_vertex (G, x)
Toto pridá vrchol, x bez pridania hrán alebo nahradí vrchol, ktorý mal hrany, ale bol odstránený. Hodnota a poloha záznamu v matici naznačujú prítomnosť konkrétneho vrcholu. Ak sa pridá vrchol, musí sa matica znovu upraviť.
add_edge (G, x, y)
Táto operácia pridá novú hranu medzi vrcholom x a vrcholom y, ak tam hrana nebola. Hodnota a poloha záznamu v matici indikujú prítomnosť konkrétnej hrany. Ak sa pridá hrana, musí sa matica znovu nastaviť.
remove_edge (G, x, y)
Táto operácia by odstránila hranu medzi vrcholom x a vrcholom y, ak by tam bola hrana. Hodnota a poloha záznamu v matici indikujú prítomnosť konkrétnej hrany. Ak je hrana odstránená, musí sa matica znovu nastaviť.
get_vertex_value (G, x)
Táto operácia vráti hodnotu v spojenú s vrcholom x. Aby ste to dosiahli, potrebujete výkonovú sadu podmnožín pre vrcholové štítky a ich hodnoty.
set_vertex_value (G, x, v)
Táto operácia dáva novú hodnotu v pre hodnotu spojenú s vrcholom, x. Aby ste to dosiahli, potrebujete výkonovú sadu podmnožín pre vrcholové štítky a ich hodnoty.
Niektoré grafy tiež spájajú hodnoty s ich okrajmi. Takéto grafy vyžadujú nasledujúce ďalšie operácie:
get_edge_value (G, x, y)
Táto operácia vráti hodnotu v spojenú s hranou (x, y). Aby ste to dosiahli, potrebujete výkonovú sadu podmnožín pre hrany a ich hodnoty.
set_edge_value (G, x, y, v)
Táto operácia dáva novú hodnotu v pre hodnotu spojenú s hranou (x, y). Aby ste to dosiahli, potrebujete výkonovú sadu podmnožín pre hrany a ich hodnoty.
Záver
Graf je množina vrcholov spojených s hranami. Graf môže byť nepresmerovaný alebo nasmerovaný. Okraje môžu byť nesmerové alebo smerové. Smyčky môžu byť v grafe prítomné alebo chýbať. Ďalej by ste sa mali naučiť sada, sada napájania a multiset súvisiace s grafmi. Potom by ste sa mali naučiť rôzne typy grafov, napríklad orientovaný graf, bežný graf, úplný graf, bipartitný graf, turnajový graf, graf toku siete atď.
Chrys
O autorovi
Chrysanthus Forcha
Objaviteľ integrácie matematiky z Prvých princípov a súvisiacich sérií. Magisterský titul v odbore technická výchova so špecializáciou na elektroniku a počítačový softvér. BSc Electronics. Mám tiež vedomosti a skúsenosti na magisterskej úrovni v odbore výpočtovej techniky a telekomunikácií. Z 20 000 spisovateľov som bol 37. najlepším spisovateľom devarticles.com. V týchto odboroch pracujem už viac ako 10 rokov.
Zobraziť všetky príspevky
