Forskel mellem retning og udirigeret graf

Directed vs Undirected Graph

En graf er en matematisk struktur, der består af et sæt af hjørner og kanter. En graf repræsenterer et sæt objekter (repræsenteret ved hjørner), der er forbundet via nogle links (repræsenteret ved kanter). Ved hjælp af matematiske notationer kan en graf repræsenteres af G, hvor G = (V, E) og V er sæt af vertices og E er sætet af kanter. I en ikke-rettet graf er der ingen retning forbundet med kanterne, der forbinder toppunktene. I en rettet graf er der en retning, der er forbundet med kanterne, der forbinder toppunktene.

Udirigeret graf

Som nævnt tidligere er en ikke-rettet graf en graf, hvori der ikke er nogen retning i kanterne, der forbinder toppunktene i grafen. Figur 1 viser en ikke-rettet graf med sæt af vertikaler V = V1, V2, V3. Kantsæt i ovenstående graf kan skrives som V = (V1, V2), (V2, V3), (V1, V3). Det kan også bemærkes, at der ikke er noget, der forhindrer skrivning af kantsættet som V = (V2, V1), (V3, V2), (V3, V1), da kanterne ikke har en retning. Derfor er kanter i en ikke-rettet graf ikke bestilte par. Dette er den vigtigste egenskab ved en ikke-rettet graf. Ukorrigerede grafer kan bruges til at repræsentere symmetriske forhold mellem objekter, der er repræsenteret af vertikater. For eksempel kan et tovejs vejnet, der forbinder et sæt byer, repræsenteres ved hjælp af en ikke-rettet graf. Byerne kan repræsenteres med vertikaterne i grafen, og kanterne repræsenterer de to veje, der forbinder byerne.

Retningslinie

En rettet graf er en graf, hvor kanterne i grafen, der forbinder vertikaterne, har en retning. Figur 2 viser en rettet graf med sæt af vertikaler V = V1, V2, V3. Kantsæt i ovenstående graf kan skrives som V = (V1, V2), (V2, V3), (V1, V3). Kanter i en ikke-rettet graf er parret. Formelt kan kant e i en rettet graf være repræsenteret af det bestilte par e = (x, y), hvor x er det toppunkt, der kaldes oprindelsen, kilden eller det oprindelige punkt på kanten e, og toppunktet y kaldes terminalen , afslutning af toppunkt eller terminalpunkt. For eksempel kan et vejnetværk, der forbinder et sæt byer ved hjælp af envejsveje, være repræsenteret ved hjælp af en ikke-rettet graf. Byerne kan være repræsenteret med vertikaterne i grafen, og de dirigerede kanter repræsenterer veje, der forbinder byerne i betragtning af retningen, som 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 bestilte par repræsenterer retningen på kanten, der forbinder de to hjørner. På den anden side i en ikke-rettet graf er en kant et uordnet par, da der ikke er nogen retning forbundet med en kant. Ikke-rettede grafer kan bruges til at repræsentere symmetriske forhold mellem objekter. In-grad og out-grad af hver knude i en ikke-rettet graf er lige, men dette er ikke tilfældet for en rettet graf. Når du bruger en matrix til at repræsentere en ikke-rettet graf, bliver matrixen altid en symmetrisk graf, men dette er ikke tilfældet for en rettet graf. En ikke-rettet 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.