Skillnaden Mellan Riktad Och Ostyrd Graf

2024 Författare: Mildred Bawerman | [email protected]. Senast ändrad: 2023-12-16 08:42

Riktad vs ej riktad graf

En graf är en matematisk struktur som består av en uppsättning hörn och kanter. En graf representerar en uppsättning objekt (representerade av hörn) som är anslutna genom vissa 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 kanter. I en oriktad graf finns ingen riktning associerad med kanterna som förbinder topparna. I en riktad graf finns en riktning associerad med kanterna som förbinder topparna.

Oriktad graf

Som tidigare nämnts är en oriktad graf en graf i vilken det inte finns någon riktning i kanterna som länkar hörn i grafen. Figur 1 visar en oriktad graf med uppsättningen av hörn V = {V1, V2, V3}. Uppsättning av kanter i ovanstående diagram kan skrivas som V = {(V1, V2), (V2, V3), (V1, V3)}. Det kan också noteras att det inte finns något som hindrar att skriva uppsättningen kanter som V = {(V2, V1), (V3, V2), (V3, V1)} eftersom kanterna inte har någon riktning. Därför är kanterna i ett oriktat diagram inte ordnade par. Detta är den huvudsakliga egenskapen hos en oriktad graf. Oriktade grafer kan användas för att representera symmetriska förhållanden mellan objekt som representeras av hörn. Exempelvis kan ett tvåvägs vägnätverk som förbinder en uppsättning städer representeras med en icke-riktad graf. Städerna kan representeras av hörnpunkterna i diagrammet och kanterna representerar de tvåvägsvägar som förbinder städerna.

Regisserad graf

En riktad graf är en graf i vilken kanterna i diagrammet som länkar topparna har en riktning. Figur 2 visar en riktad graf med uppsättningen av hörn V = {V1, V2, V3}. Uppsättning av kanter i ovanstående diagram kan skrivas som V = {(V1, V2), (V2, V3), (V1, V3)}. Kanter i ett oriktat diagram är ordnade par. Formellt kan kant e i en riktad graf representeras av det ordnade paret e = (x, y) där x är toppunkten som kallas ursprung, källa eller initialpunkten för kanten e, och toppunkt y kallas terminalen, avslutande toppunkt eller terminalpunkt. Till exempel kan ett vägnätverk som ansluter en uppsättning städer med envägsvägar representeras med hjälp av en icke-riktad graf. Städerna kan representeras av hörnpunkterna i diagrammet och de riktade kanterna representerar de vägar som förbinder städerna med tanke på den riktning som trafiken flyter i 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 den riktning på kanten som länkar de två topparna. Å 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 förhållanden mellan objekt. In-grad och ut-grad av 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 riktade grafer. 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.