Skirtumas tarp nukreipto ir netaikomo grafiko

Kryptis vs neviršytas grafikas

Grafikas yra matematinė struktūra, sudaryta iš viršūnių ir briaunų rinkinio. Diagrama žymi objektų, žymimų viršūnėmis, rinkinį, sujungtą per kai kurias nuorodas (pavaizduotas briaunomis). Naudojant matematinius ženklus, grafiką galima pavaizduoti G, kur G = (V, E) ir V yra viršūnių aibė, o E yra briaunų aibė. Nevadintame grafike nėra krypties, susijusios su kraštais, jungiančiais viršūnes. Nukreiptame grafike yra kryptis, susieta su kraštais, jungiančiais viršūnes.

Nukreiptas grafikas

Kaip minėta anksčiau, neorientuotas grafikas yra grafikas, kurio briaunose nėra krypties, susiejančios grafiko viršūnes. 1 paveiksle pavaizduotas nenukreiptas grafikas su viršūnių rinkiniu V = V1, V2, V3. Aukščiau pateiktoje diagramoje esančių kraštų 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ų rinkinį kaip V = (V2, V1), (V3, V2), (V3, V1), nes kraštai neturi krypties. Todėl nekreipto grafiko briaunos nėra išdėstytos poromis. Tai yra pagrindinė nenukreipto grafiko savybė. Nukreipti grafikai gali būti naudojami simetriškiems ryšiams tarp objektų, kuriuos vaizduoja viršūnės, atvaizduoti. Pvz., Dvipusis kelių tinklas, jungiantis miestų rinkinį, gali būti pavaizduotas naudojant nenuorotą diagramą. Miestus grafike gali pavaizduoti viršūnės, o kraštai - miestus jungiančius dviejų krypčių kelius.

Nukreiptas grafikas

Nukreiptas grafikas yra grafikas, kuriame briaunos, jungiančios viršūnes, turi kryptį. 2 paveiksle pavaizduotas nukreiptas grafikas su viršūnių rinkiniu V = V1, V2, V3. Aukščiau pateiktoje diagramoje esančių kraštų rinkinys gali būti parašytas kaip V = (V1, V2), (V2, V3), (V1, V3). Nukreipto grafiko kraštai išdėstomi poromis. Formaliai e kraštas nukreiptame grafike gali būti pavaizduotas eilės pora e = (x, y), kur x yra viršūnė, vadinama kraštinės e pradžia, šaltiniu arba pradiniu tašku, o viršūnė y vadinama galine. , galinė viršūnė arba galinis taškas. Pvz., Kelių tinklas, jungiantis miestų rinkinį vienpusiais keliais, gali būti pavaizduotas naudojant nenukreiptą schemą. Miestai gali būti pavaizduoti viršūnėmis grafike, o nukreiptos briaunos žymi miestus jungiančius kelius, atsižvelgiant į kryptį, kuria eismas teka keliu.

Kuo skiriasi „Directed Graph“ ir „Nedirected Graph“?

Nukreiptame grafike briauna yra užsakoma pora, kur užsakoma pora nurodo krašto, jungiančio dvi viršūnes, kryptį. Kita vertus, nekreiptame grafike briauna yra netvarkyta pora, nes su kraštu nėra susijusios krypties. Nesukreipti grafikai gali būti naudojami simetriškiems objektų santykiams pavaizduoti. Kiekvieno nenukreipto grafiko mazgo laipsniai ir laipsniai yra lygūs, tačiau tai netaikoma nukreiptam grafikui. Kai naudojama matrica, kad atvaizduotų nenukreiptą grafiką, ji visada tampa simetrine diagrama, tačiau tai negalioja nukreiptiems grafikams. Nukreiptą grafiką galima paversti nukreiptu grafiku, pakeičiant kiekvieną kraštą dviem nukreiptais kraštais, einančiais priešinga kryptimi. Tačiau neįmanoma konvertuoti nukreipto grafiko į nevestuotą grafiką.