Nukreiptas ir nenukreiptas grafikas
Grafikas yra matematinė struktūra, kurią sudaro viršūnių ir kraštų rinkinys. Grafikas nurodo objektų rinkinį (vaizduojamą viršūnių), kurie yra sujungti per kai kurias nuorodas (kurias žymi kraštai). Naudojant matematinius žymėjimus, grafikas gali būti pavaizduotas G, kur G = (V, E) ir V yra viršūnių rinkinys, o E yra briaunų rinkinys. Nenukreiptame grafike nėra krypties, susijusios su kraštais, jungiančiais viršūnes. Nukreiptame grafike yra kryptis, susieta su kraštais, jungiančiais viršūnes.
Nenukreiptas grafikas
Kaip minėta anksčiau, nenukreiptas grafikas yra grafikas, kuriame briaunose nėra krypties, jungiančios grafo viršūnes. 1 paveiksle pavaizduotas nenukreiptas grafikas su viršūnių rinkiniu V = {V1, V2, V3}. Briaunų rinkinį aukščiau pateiktame grafike galima užrašyti kaip V = {(V1, V2), (V2, V3), (V1, V3)}. Taip pat galima pažymėti, kad niekas netrukdo rašyti kraštų rinkinio kaip V = {(V2, V1), (V3, V2), (V3, V1)}, nes kraštai neturi krypties. Todėl nenukreipto grafiko kraštai nėra sutvarkytos poros. Tai yra pagrindinė nenukreipto grafiko charakteristika. Nenukreipti grafikai gali būti naudojami simetriškiems santykiams tarp objektų, kuriuos vaizduoja viršūnės, pavaizduoti. Pavyzdžiui, dviejų krypčių kelių tinklas, jungiantis miestų rinkinį, gali būti pavaizduotas naudojant nenukreiptą grafiką. Miestai gali būti pavaizduoti diagramoje esančiomis viršūnėmis, o kraštai - dvipusiais keliais, jungiančiais miestus.
Kryptinis grafikas
Nukreiptas grafikas yra grafikas, kuriame diagramos kraštai, jungiantys viršūnes, turi kryptį. 2 paveiksle pavaizduotas nukreiptas grafikas su viršūnių rinkiniu V = {V1, V2, V3}. Briaunų rinkinį aukščiau pateiktame grafike galima užrašyti kaip V = {(V1, V2), (V2, V3), (V1, V3)}. Nenukreipto grafiko kraštai yra išdėstyti poromis. Formaliai kraštą e nukreiptame grafike 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, baigianti viršūnę arba galinį tašką. Pavyzdžiui, kelių tinklas, jungiantis miestų rinkinį vienpusiais keliais, gali būti pavaizduotas naudojant nenukreiptą grafiką. Miestai gali būti pavaizduoti viršūnėmis diagramoje, o nukreiptos briaunos rodo kelius, jungiančius miestus, atsižvelgiant į eismo srauto kryptį.
Koks skirtumas tarp nukreipto grafiko ir nenukreipto grafiko?
Nukreiptame grafike briauna yra sutvarkyta pora, kur sutvarkyta pora reiškia krašto, siejančio abi viršūnes, kryptį. Kita vertus, nekreiptame grafike kraštas yra netvarkyta pora, nes nėra krypties, susijusios su kraštu. Nenukreipti grafikai gali būti naudojami simetriškiems objektų santykiams vaizduoti. Kiekvieno nenukreipto grafo mazgo laipsnis ir laipsnis yra lygūs, tačiau tai netiesa nukreiptam grafui. Naudojant matricą nenukreiptam grafikui vaizduoti, matrica visada tampa simetrišku grafiku, tačiau tai nėra tiesa nukreiptiems grafikams. Nenukreiptą grafiką galima paversti nukreiptu grafu, pakeičiant kiekvieną kraštą dviem nukreiptais kraštais, einančiais priešinga kryptimi. Tačiau neįmanoma konvertuoti nukreipto grafiko į nenukreiptą grafiką.
