Directed vs Udirected Graph
En graf er en matematisk struktur som består av sett med hjørner og kanter. En graf representerer et sett med objekter (representert av toppunkter) som er koblet sammen gjennom noen lenker (representert av kanter). Ved å bruke matematiske notasjoner kan en graf representeres av G, der G=(V, E) og V er settet med toppunkter og E er settet med kanter. I en urettet graf er det ingen retning knyttet til kantene som forbinder toppunktene. I en rettet graf er det en retning knyttet til kantene som forbinder toppunktene.
Udirigert graf
Som nevnt tidligere, er en urettet graf en graf der det ikke er noen retning i kantene som forbinder toppunktene i grafen. Figur 1 viser en urettet graf med sett med toppunkter V={V1, V2, V3}. Sett med kanter i grafen ovenfor kan skrives som V={(V1, V2), (V2, V3), (V1, V3)}. Det kan også bemerkes at det ikke er noe i veien for å skrive settet med kanter som V={(V2, V1), (V3, V2), (V3, V1)} siden kantene ikke har en retning. Derfor er kanter i en urettet graf ikke ordnede par. Dette er hovedkarakteristikken til en urettet graf. Urettede grafer kan brukes til å representere symmetriske forhold mellom objekter som er representert av toppunkter. For eksempel kan et toveis veinett som forbinder et sett med byer representeres ved hjelp av en urettet graf. Byene kan representeres av toppunktene i grafen, og kantene representerer toveisveiene som forbinder byene.
Directed Graph
En rettet graf er en graf der kantene i grafen som forbinder hjørnene har en retning. Figur 2 viser en rettet graf med sett med toppunkter V={V1, V2, V3}. Sett med kanter i grafen ovenfor kan skrives som V={(V1, V2), (V2, V3), (V1, V3)}. Kanter i en urettet graf er ordnede par. Formelt sett kan kant e i en rettet graf representeres av det ordnede paret e=(x, y) hvor x er toppunktet som kalles origo, kilde eller startpunktet til kanten e, og toppunkt y kalles terminus, avsluttende toppunkt eller terminalpunkt. For eksempel kan et veinett som forbinder et sett med byer ved hjelp av enveisveier representeres ved hjelp av en urettet graf. Byene kan representeres av toppunktene i grafen og de rettede kantene representerer veiene som forbinder byene med tanke på retningen trafikken flyter i veien.
Hva er forskjellen mellom Directed Graph og Undirected Graph?
I en rettet graf er en kant et ordnet par, der det ordnede paret representerer retningen til kanten som forbinder de to toppunktene. På den annen side, i en urettet graf, er en kant et uordnet par, siden det ikke er noen retning knyttet til en kant. Urettede grafer kan brukes til å representere symmetriske forhold mellom objekter. In-grad og ut-grad for hver node i en urettet graf er lik, men dette er ikke sant for en rettet graf. Når du bruker en matrise for å representere en urettet graf, blir matrisen alltid en symmetrisk graf, men dette er ikke sant for en rettet graf. En urettet graf kan konverteres til en rettet graf ved å erstatte hver kant med to rettede kanter som går i motsatt retning. Det er imidlertid ikke mulig å konvertere en rettet graf til en urettet graf.
