Suunatud Ja Suunamata Graafiku Erinevus

2024 Autor: Mildred Bawerman | [email protected]. Viimati modifitseeritud: 2023-12-16 08:38

Suunatud vs suunamata graafik

Graaf on matemaatiline struktuur, mis koosneb tippude ja servade komplektist. Graafik tähistab objektide kogumit (mida tähistavad tipud), mis on ühendatud mõne lingi kaudu (mida tähistavad servad). Matemaatilisi tähistusi kasutades saab graafi esitada G-ga, kus G = (V, E) ja V on tippude hulk ja E on servade hulk. Suunamata graafil pole tippu ühendavate servadega seotud suunda. Suunatud graafil on tippudega seotud servadega seotud suund.

Suunamata graafik

Nagu varem mainitud, on suunamata graaf graaf, mille servades pole suunda, mis seoks graafi tippe. Joonisel 1 on kujutatud suunamata graaf tippude komplektiga V = {V1, V2, V3}. Ülaltoodud graafiku servade komplekti saab kirjutada järgmiselt: V = {(V1, V2), (V2, V3), (V1, V3)}. Samuti võib märkida, et miski ei takista servade komplekti kirjutamist V = {(V2, V1), (V3, V2), (V3, V1)}, kuna servadel pole suunda. Seetõttu ei ole suunamata graafi servad paarid. See on suunamata graafi peamine omadus. Suunamata graafikuid saab kasutada tippude abil kujutatavate objektide vaheliste sümmeetriliste seoste esitamiseks. Näiteks saab linnade komplekti ühendavat kahesuunalist teedevõrku kujutada suunamata graafi abil. Linnasid saab graafikul kujutada tippudega ja servad tähistavad linnu ühendavaid kahesuunalisi teid.

Suunatud graafik

Suunatud graaf on graafik, milles graafi tippe ühendavatel servadel on suund. Joonis 2 kujutab suunatud graafi tippude komplektiga V = {V1, V2, V3}. Ülaltoodud graafiku servade komplekti saab kirjutada järgmiselt: V = {(V1, V2), (V2, V3), (V1, V3)}. Suunamata graafi servad on järjestatud paaridena. Formaalselt saab suunatud graafi serva e kujutada järjestatud paariga e = (x, y), kus x on tipp, mida nimetatakse serva e alguseks, allikaks või algpunktiks, ja tippu y terminuseks, tiputipp või lõpp-punkt. Näiteks saab teedevõrku, mis ühendab linnade komplekti ühesuunaliste teede abil, suunamata graafi abil. Linnasid saab graafikul kujutada tippude abil ja suunatud servad tähistavad teid, mis ühendavad linnu, arvestades liikluse suuna suunda.

Mis vahe on suunatud graafil ja suunamata graafikul?

Suunatud graafis on serv järjestatud paar, kus järjestatud paar tähistab serva suunda, mis ühendab kahte tippu. Teisalt on suunamata graafis serv järjestamata paar, kuna servaga pole seotud suunda. Objektide sümmeetriliste seoste esitamiseks saab kasutada suunamata graafikuid. Suunamata graafi iga sõlme in- ja out-kraad 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 puhul. Suunamata graafi saab teisendada suunatud graafiks, asendades iga serva kahe vastassuunas kulgeva suunaga. Suunatud graafi suunamata graafiks teisendada pole siiski võimalik.