Gerigte vs Ongerigte grafiek
'n Grafiek is 'n wiskundige struktuur wat bestaan uit stel hoekpunte en rande. 'n Grafiek stel 'n stel voorwerpe voor (verteenwoordig deur hoekpunte) wat verbind is deur sommige skakels (voorgestel deur rande). Deur wiskundige notasies te gebruik, kan 'n grafiek deur G voorgestel word, waar G=(V, E) en V die stel hoekpunte is en E die stel rande is. In 'n ongerigte grafiek is daar geen rigting wat verband hou met die rande wat die hoekpunte verbind nie. In 'n gerigte grafiek is daar 'n rigting wat verband hou met die rande wat die hoekpunte verbind.
Ongerigte grafiek
Soos vroeër genoem, is 'n ongerigte grafiek 'n grafiek waarin daar geen rigting in die rande is wat die hoekpunte in die grafiek verbind nie. Figuur 1 beeld 'n ongerigte grafiek uit met stel hoekpunte V={V1, V2, V3}. Stel rande in die grafiek hierbo kan geskryf word as V={(V1, V2), (V2, V3), (V1, V3)}. Daar kan ook opgemerk word dat daar niks is wat verhoed om die stel rande as V={(V2, V1), (V3, V2), (V3, V1)} te skryf, aangesien die rande nie 'n rigting het nie. Daarom is rande in 'n ongerigte grafiek nie geordende pare nie. Dit is die hoofkenmerk van 'n ongerigte grafiek. Ongerigte grafieke kan gebruik word om simmetriese verwantskappe tussen voorwerpe wat deur hoekpunte voorgestel word, voor te stel. Byvoorbeeld, 'n tweerigting-padnetwerk wat 'n stel stede verbind, kan voorgestel word deur 'n ongerigte grafiek te gebruik. Die stede kan deur die hoekpunte in die grafiek voorgestel word en die rande verteenwoordig die tweerigtingpaaie wat die stede verbind.
Girigeerde grafiek
'n Gerigte grafiek is 'n grafiek waarin die rande in die grafiek wat die hoekpunte verbind, 'n rigting het. Figuur 2 beeld 'n gerigte grafiek uit met stel hoekpunte V={V1, V2, V3}. Stel rande in die grafiek hierbo kan geskryf word as V={(V1, V2), (V2, V3), (V1, V3)}. Rande in 'n ongerigte grafiek is geordende pare. Formeel kan rand e in 'n gerigte grafiek voorgestel word deur die geordende paar e=(x, y) waar x die hoekpunt is wat die oorsprong, bron of die beginpunt van die rand e genoem word, en hoekpunt y die terminus genoem word, eindpunt of eindpunt. Byvoorbeeld, 'n padnetwerk wat 'n stel stede verbind deur eenrigtingpaaie te gebruik, kan met 'n ongerigte grafiek voorgestel word. Die stede kan deur die hoekpunte in die grafiek voorgestel word en die gerigte rande verteenwoordig die paaie wat die stede verbind, met inagneming van die rigting waarin die verkeer in die pad vloei.
Wat is die verskil tussen gerigte grafiek en ongerigte grafiek?
In 'n gerigte grafiek is 'n rand 'n geordende paar, waar die geordende paar die rigting verteenwoordig van die rand wat die twee hoekpunte verbind. Aan die ander kant, in 'n ongerigte grafiek, is 'n rand 'n ongeordende paar, aangesien daar geen rigting met 'n rand geassosieer word nie. Ongerigte grafieke kan gebruik word om simmetriese verwantskappe tussen voorwerpe voor te stel. In-graad en uit-graad van elke nodus in 'n ongerigte grafiek is gelyk, maar dit is nie waar vir 'n gerigte grafiek nie. Wanneer 'n matriks gebruik word om 'n ongerigte grafiek voor te stel, word die matriks altyd 'n simmetriese grafiek, maar dit is nie waar vir 'n gerigte grafieke nie. 'n Ongerigte grafiek kan omgeskakel word na 'n gerigte grafiek deur elke rand te vervang met twee gerigte rande wat in teenoorgestelde rigting loop. Dit is egter nie moontlik om 'n gerigte grafiek na 'n ongerigte grafiek om te skakel nie.
