Erinevus suunatud ja suunamata graafiku vahel

Suunatud või suunamata graafik

Graafik on matemaatiline struktuur, mis koosneb tippude ja servade komplektist. Graafik kujutab objektide kogumit (mida esindavad tipud), mis on ühendatud mõne lingi kaudu (tähistatud servadega). Matemaatilisi märkusi kasutades saab graafi tähistada G-ga, kus G = (V, E) ja V on tippude kogum ja E on servade kogum. Suunamata graafil pole tippe ühendavate servadega suhet. Suunatud graafikul on tipp, mis ühendavad servi, mis ühendavad tippe.

Suunamata graafik

Nagu varem mainitud, on suunamata graaf graaf, milles servades puudub suund, mis ühendab graafi tippe. Joonis 1 kujutab suunamata graafi tippude komplektiga V = V1, V2, V3. Ülaltoodud graafiku servade komplekt võib olla kirjutatud kujul V = (V1, V2), (V2, V3), (V1, V3). Samuti võib märkida, et miski ei takista servade komplekti kirjutamist kujul V = (V2, V1), (V3, V2), (V3, V1), kuna servadel puudub suund. Seetõttu ei ole suunamata graafi servad järjestatud paarid. See on suunamata graafi peamine omadus. Suunamata graafikuid saab kasutada sümmeetriliste suhete esitamiseks objektide vahel, mida tähistavad tipud. Näiteks saab kahesuunalist teedevõrku, mis ühendab linnade komplekti, suunamata graafiku abil. Linnade tähistamiseks tuleb graafikul kasutada tippe ja servad tähistavad kahesuunalisi teid, mis ühendavad linnu.

Suunatud graafik

Suunatud graaf on graaf, milles tippe ühendavatel graafi servadel on suund. Joonis 2 kujutab suunatud graafi tippude komplektiga V = V1, V2, V3. Ülaltoodud graafiku servade komplekt võib olla kirjutatud kujul V = (V1, V2), (V2, V3), (V1, V3). Suunamata graafi servad on järjestatud paaridena. Formaalselt saab serva e suunatavas graafis tähistada järjestatud paariga e = (x, y), kus x on tipp, mida nimetatakse serva e lähtekohaks, lähteks või lähtepunktiks, ja tippu y nimetatakse lõppuks , otsa- või lõpp-punkt. Näiteks saab teedevõrku, mis ühendab linnade komplekti ühesuunaliste teede abil, suunamata graafiku abil. Linnu saab graafikus näidata tippude abil ja suunatud servad tähistavad teid ühendavaid teid, arvestades suunda, kus liiklus maanteel voolab.

Mis vahe on suunatud graafikul ja suunamata graafil??

Suunatud graafikus on serv järjestatud paar, kus järjestatud paar tähistab serva suunda, mis ühendab kahte tippu. Teisest küljest on suundumata graafil serv järjestamata paar, kuna servaga pole ühtegi suunda seotud. Suunamata graafikuid saab kasutada objektide vaheliste sümmeetriliste suhete tähistamiseks. Suunamata graafiku iga sõlme kraadi ja välja aste on võrdsed, kuid see ei kehti suunatud graafi kohta. Kui maatriksit kasutatakse suunamata graafi esitamiseks, muutub maatriks alati sümmeetriliseks graafiks, kuid see ei kehti suunatud graafide kohta. Suunamata graafi saab teisendada suunatud graafiks, asendades iga serva kahe vastassuunas liikuva suunaga. Suunatud graafiks pole aga võimalik teisendada suunamata graafi.