Iliyoelekezwa dhidi ya Grafu Isiyoelekezwa
Grafu ni muundo wa hisabati unaoundwa na seti ya vipeo na kingo. Grafu inawakilisha seti ya vitu (vinawakilishwa na wima) ambavyo vimeunganishwa kupitia baadhi ya viungo (vinavyowakilishwa na kingo). Kwa kutumia nukuu za hisabati, grafu inaweza kuwakilishwa na G, ambapo G=(V, E) na V ni seti ya vipeo na E ni seti ya kingo. Katika grafu isiyoelekezwa hakuna mwelekeo unaohusishwa na kingo zinazounganisha wima. Katika grafu iliyoelekezwa kuna mwelekeo unaohusishwa na kingo zinazounganisha wima.
Grafu Isiyoelekezwa
Kama ilivyotajwa awali, grafu ambayo haijaelekezwa ni grafu ambayo hakuna mwelekeo katika kingo zinazounganisha wima kwenye grafu. Kielelezo cha 1 kinaonyesha grafu ambayo haijaelekezwa na seti ya wima V={V1, V2, V3}. Seti ya kingo katika grafu iliyo hapo juu inaweza kuandikwa kama V={(V1, V2), (V2, V3), (V1, V3)}. Inaweza pia kuzingatiwa kuwa hakuna kitu kinachozuia kuandika seti ya kingo kama V={(V2, V1), (V3, V2), (V3, V1)} kwani kingo hazina mwelekeo. Kwa hivyo kingo kwenye grafu isiyoelekezwa hazijaagizwa jozi. Hii ndiyo sifa kuu ya grafu isiyoelekezwa. Grafu ambazo hazijaelekezwa zinaweza kutumika kuwakilisha uhusiano wa ulinganifu kati ya vitu ambavyo vinawakilishwa na vipeo. Kwa mfano, mtandao wa barabara wa njia mbili unaounganisha seti ya miji unaweza kuwakilishwa kwa kutumia grafu isiyoelekezwa. Miji inaweza kuwakilishwa na wima kwenye grafu na kingo zinawakilisha njia mbili zinazounganisha miji.
Grafu Iliyoelekezwa
Grafu iliyoelekezwa ni grafu ambayo kingo za jedwali zinazounganisha wima zina mwelekeo. Mchoro wa 2 unaonyesha grafu iliyoelekezwa yenye seti ya vipeo V={V1, V2, V3}. Seti ya kingo katika grafu iliyo hapo juu inaweza kuandikwa kama V={(V1, V2), (V2, V3), (V1, V3)}. Kingo katika grafu isiyoelekezwa ni jozi zilizoagizwa. Rasmi, makali e katika grafu iliyoelekezwa inaweza kuwakilishwa na jozi iliyoagizwa e=(x, y) ambapo x ni kipeo kinachoitwa asili, chanzo au ncha ya mwanzo ya ukingo e, na kipeo y kinaitwa kipeo., kusitisha kipeo au sehemu ya mwisho. Kwa mfano, mtandao wa barabara unaounganisha seti ya miji kwa kutumia njia moja ya barabara inaweza kuwakilishwa kwa kutumia grafu isiyoelekezwa. Miji inaweza kuwakilishwa na wima kwenye grafu na kingo zilizoelekezwa zinawakilisha barabara zinazounganisha miji kwa kuzingatia mwelekeo ambao trafiki inapita barabarani.
Kuna tofauti gani kati ya Grafu Iliyoelekezwa na Grafu Isiyoelekezwa?
Katika grafu iliyoelekezwa ukingo ni jozi iliyopangwa, ambapo jozi iliyopangwa inawakilisha mwelekeo wa ukingo unaounganisha wima mbili. Kwa upande mwingine, katika grafu isiyoelekezwa, makali ni jozi isiyopangwa, kwa kuwa hakuna mwelekeo unaohusishwa na makali. Grafu ambazo hazijaelekezwa zinaweza kutumika kuwakilisha uhusiano wa ulinganifu kati ya vitu. Kiwango cha ndani na nje cha kila nodi kwenye grafu isiyoelekezwa ni sawa lakini hii si kweli kwa grafu iliyoelekezwa. Wakati wa kutumia matrix kuwakilisha grafu isiyoelekezwa, matriki huwa ni grafu linganifu kila mara, lakini hii si kweli kwa grafu iliyoelekezwa. Grafu isiyoelekezwa inaweza kubadilishwa kuwa grafu iliyoelekezwa kwa kubadilisha kila ukingo na kingo mbili zilizoelekezwa kwenda kinyume. Hata hivyo, haiwezekani kubadilisha grafu iliyoelekezwa hadi grafu isiyoelekezwa.
