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