Directed vs Undirected Graph
Grafas yra matematinė struktūra, sudaryta iš viršūnių ir briaunų. Grafas vaizduoja objektų rinkinį (atvaizduojamus viršūnėmis), kurie yra sujungti tam tikromis nuorodomis (pavaizduoti briaunomis). Naudojant matematinius žymėjimus, grafą galima pavaizduoti G, kur G=(V, E) ir V – viršūnių aibė, o E – briaunų aibė. Nenukreiptame grafe nėra krypties, susietos su briaunomis, jungiančiomis viršūnes. Nukreiptame grafe yra kryptis, susieta su briaunomis, jungiančiomis viršūnes.
Nenukreiptas grafikas
Kaip minėta anksčiau, nenukreiptas grafikas yra grafikas, kurio kraštinėse, jungiančiose grafo viršūnes, nėra krypties.1 paveiksle pavaizduotas nenukreiptas grafikas su viršūnių rinkiniu V={V1, V2, V3}. Aukščiau pateikto grafiko briaunų rinkinys gali būti parašytas kaip V={(V1, V2), (V2, V3), (V1, V3)}. Taip pat galima pastebėti, kad niekas netrukdo parašyti briaunų aibės kaip V={(V2, V1), (V3, V2), (V3, V1)}, nes briaunos neturi krypties. Todėl nenukreipto grafo briaunos nėra sutvarkytos poros. Tai yra pagrindinė neorientuoto grafo savybė. Nenukreiptus grafikus galima naudoti simetriniams ryšiams tarp objektų, kurie yra vaizduojami viršūnėmis, pavaizduoti. Pavyzdžiui, dvipusis kelių tinklas, jungiantis miestų rinkinį, gali būti pavaizduotas naudojant nenukreiptą grafiką. Miestus galima pavaizduoti grafiko viršūnėmis, o kraštai – dvipusius kelius, jungiančius miestus.
Režisuota diagrama
Kreiptas grafikas yra grafikas, kuriame grafo briaunos, jungiančios viršūnes, turi kryptį. 2 paveiksle pavaizduotas nukreiptas grafikas su viršūnių rinkiniu V={V1, V2, V3}. Aukščiau pateikto grafiko briaunų rinkinys gali būti parašytas kaip V={(V1, V2), (V2, V3), (V1, V3)}. Nenukreipto grafiko briaunos yra sutvarkytos poros. Formaliai kraštą e nukreiptame grafe galima pavaizduoti sutvarkyta pora e=(x, y), kur x yra viršūnė, vadinama krašto e pradžia, š altiniu arba pradiniu tašku, o viršūnė y vadinama galu., baigiamoji viršūnė arba galinis taškas. Pavyzdžiui, kelių tinklas, jungiantis miestų rinkinį naudojant vienpusius kelius, gali būti pavaizduotas naudojant nenukreiptą grafiką. Miestus galima pavaizduoti grafiko viršūnėmis, o nukreiptos briaunos – kelius, jungiančius miestus, atsižvelgiant į eismo srauto kryptį.
Kuo skiriasi nukreiptas grafikas ir neorientuotas grafikas?
Nukreiptame grafe briauna yra sutvarkyta pora, kur sutvarkyta pora reiškia briaunos, jungiančios dvi viršūnes, kryptį. Kita vertus, nenukreiptame grafe briauna yra netvarkinga pora, nes su briauna nėra susietos krypties. Nenukreiptus grafikus galima naudoti simetriniams objektų santykiams pavaizduoti. Kiekvieno nenukreipto grafiko mazgo laipsnis ir išorinis laipsnis yra lygūs, tačiau tai netinka nukreiptam grafikui. Naudojant matricą nenukreiptam grafikui pavaizduoti, matrica visada tampa simetrišku grafiku, tačiau tai netinka nukreiptiems grafams. Nenukreiptą grafą galima paversti nukreiptu grafu, kiekvieną briauną pakeičiant dviem nukreiptomis briaunomis, einančiomis priešinga kryptimi. Tačiau neįmanoma nukreipto grafiko konvertuoti į neorientuotą.
