Directed vs Undirected Graph
En graf er en matematisk struktur, der består af sæt af hjørner og kanter. En graf repræsenterer et sæt af objekter (repræsenteret ved toppunkter), der er forbundet via nogle links (repræsenteret af kanter). Ved hjælp af matematiske notationer kan en graf repræsenteres ved G, hvor G=(V, E) og V er sættet af hjørner og E er sættet af kanter. I en urettet graf er der ingen retning forbundet med de kanter, der forbinder hjørnerne. I en rettet graf er der en retning forbundet med de kanter, der forbinder hjørnerne.
Udirigeret graf
Som tidligere nævnt er en urettet graf en graf, hvor der ikke er nogen retning i kanterne, der forbinder hjørnerne i grafen. Figur 1 viser en urettet graf med et sæt af hjørner V={V1, V2, V3}. Sæt af kanter i ovenstående graf kan skrives som V={(V1, V2), (V2, V3), (V1, V3)}. Det kan også bemærkes, at der ikke er noget til hinder for at skrive sættet af kanter som V={(V2, V1), (V3, V2), (V3, V1)}, da kanterne ikke har en retning. Derfor er kanter i en urettet graf ikke ordnede par. Dette er hovedkarakteristikken for en urettet graf. Urettede grafer kan bruges til at repræsentere symmetriske forhold mellem objekter, der er repræsenteret af hjørner. For eksempel kan et tovejs vejnetværk, der forbinder et sæt byer, repræsenteres ved hjælp af en urettet graf. Byerne kan repræsenteres af hjørnerne i grafen, og kanterne repræsenterer tovejsvejene, der forbinder byerne.
Directed Graph
En rettet graf er en graf, hvor kanterne i grafen, der forbinder hjørnerne, har en retning. Figur 2 viser en rettet graf med sæt af hjørner V={V1, V2, V3}. Sæt af kanter i ovenstående graf kan skrives som V={(V1, V2), (V2, V3), (V1, V3)}. Kanter i en urettet graf er ordnede par. Formelt kan kant e i en rettet graf repræsenteres af det ordnede par e=(x, y), hvor x er det toppunkt, der kaldes oprindelsen, kilden eller startpunktet for kanten e, og toppunktet y kaldes terminus, afsluttende toppunkt eller terminalpunkt. For eksempel kan et vejnet, der forbinder et sæt byer ved hjælp af ensrettede veje, repræsenteres ved hjælp af en urettet graf. Byerne kan repræsenteres af hjørnerne i grafen, og de rettede kanter repræsenterer de veje, der forbinder byerne i betragtning af den retning, trafikken flyder i vejen.
Hvad er forskellen mellem Directed Graph og Undirected Graph?
I en rettet graf er en kant et ordnet par, hvor det ordnede par repræsenterer retningen af den kant, der forbinder de to toppunkter. På den anden side, i en urettet graf, er en kant et uordnet par, da der ikke er nogen retning forbundet med en kant. Urettede grafer kan bruges til at repræsentere symmetriske forhold mellem objekter. In-grad og ud-grad af hver node i en urettet graf er ens, men dette er ikke sandt for en rettet graf. Når du bruger en matrix til at repræsentere en urettet graf, bliver matrixen altid en symmetrisk graf, men dette er ikke sandt for en rettet graf. En urettet graf kan konverteres til en rettet graf ved at erstatte hver kant med to rettede kanter, der går i modsat retning. Det er dog ikke muligt at konvertere en rettet graf til en ikke-rettet graf.
