Riktad vs oriktad graf
En graf är en matematisk struktur som består av en uppsättning av hörn och kanter. En graf representerar en uppsättning objekt (representerade av hörn) som är sammankopplade via några länkar (representerade av kanter). Med hjälp av matematiska notationer kan en graf representeras av G, där G=(V, E) och V är uppsättningen av hörn och E är uppsättningen av kanter. I en oriktad graf finns ingen riktning associerad med kanterna som förbinder hörnen. I en riktad graf finns en riktning associerad med kanterna som förbinder hörnen.
Oriktad graf
Som nämnts tidigare är en oriktad graf en graf där det inte finns någon riktning i kanterna som länkar samman hörn i grafen. Figur 1 visar en oriktad graf med uppsättning av hörn V={V1, V2, V3}. Uppsättning kanter i grafen ovan kan skrivas som V={(V1, V2), (V2, V3), (V1, V3)}. Det kan också noteras att det inte finns något som hindrar att man skriver uppsättningen av kanter som V={(V2, V1), (V3, V2), (V3, V1)} eftersom kanterna inte har en riktning. Därför är kanter i en oriktad graf inte ordnade par. Detta är den huvudsakliga egenskapen hos en oriktad graf. Oriktade grafer kan användas för att representera symmetriska relationer mellan objekt som representeras av hörn. Till exempel kan ett tvåvägsvägnät som förbinder en uppsättning städer representeras med hjälp av en oriktad graf. Städerna kan representeras av hörnen i grafen och kanterna representerar de tvåvägsvägar som förbinder städerna.
Directed Graph
En riktad graf är en graf där kanterna i grafen som länkar hörnen har en riktning. Figur 2 visar en riktad graf med uppsättning av hörn V={V1, V2, V3}. Uppsättning kanter i grafen ovan kan skrivas som V={(V1, V2), (V2, V3), (V1, V3)}. Kanter i en oriktad graf är ordnade par. Formellt kan kant e i en riktad graf representeras av det ordnade paret e=(x, y) där x är den vertex som kallas origo, källa eller startpunkten för kanten e, och vertex y kallas terminus, avslutande vertex eller terminalpunkt. Till exempel kan ett vägnät som förbinder en uppsättning städer med enkelriktade vägar representeras med en oriktad graf. Städerna kan representeras av hörnen i grafen och de riktade kanterna representerar vägarna som förbinder städerna med tanke på riktningen som trafiken flyter på vägen.
Vad är skillnaden mellan Directed Graph och Undirected Graph?
I en riktad graf är en kant ett ordnat par, där det ordnade paret representerar riktningen på kanten som länkar samman de två hörnen. Å andra sidan, i en oriktad graf, är en kant ett oordnat par, eftersom det inte finns någon riktning associerad med en kant. Oriktade grafer kan användas för att representera symmetriska relationer mellan objekt. In-grad och ut-grad för varje nod i en oriktad graf är lika men detta är inte sant för en riktad graf. När du använder en matris för att representera en oriktad graf, blir matrisen alltid en symmetrisk graf, men detta är inte sant för en riktad graf. En oriktad graf kan konverteras till en riktad graf genom att ersätta varje kant med två riktade kanter som går i motsatt riktning. Det är dock inte möjligt att konvertera en riktad graf till en oriktad graf.
