Forskellen Mellem Rettet Og Ikke-rettet Graf

2024 Forfatter: Mildred Bawerman | [email protected]. Sidst ændret: 2023-12-16 08:37

Directed vs Undirected Graph

En graf er en matematisk struktur, der består af et sæt 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 af kanter). Ved hjælp af matematiske notationer kan en graf repræsenteres af G, hvor G = (V, E) og V er sæt af hjørner, og E er sæt af kanter. I en ikke-rettet 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 ikke-rettet graf en graf, hvor der ikke er nogen retning i kanterne, der forbinder hjørnerne i grafen. Figur 1 viser en ikke-rettet graf med sæt af hjørner V = {V1, V2, V3}. Sæt med 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, 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 ordnede par. Dette er hovedkarakteristikken for en ikke-rettet graf. Ikke-dirigerede grafer kan bruges til at repræsentere symmetriske forhold mellem objekter, der er repræsenteret ved hjørner. For eksempel kan et tovejs vejnetværk, der forbinder et sæt byer, repræsenteres ved hjælp af en ikke-rettet graf. Byerne kan repræsenteres af hjørnerne i grafen, og kanterne repræsenterer de tovejsveje, der forbinder byerne.

Regisseret graf

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 med kanter i ovenstående graf 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 repræsenteres af det ordnede par e = (x, y) hvor x er toppunktet, der kaldes oprindelsen, kilden eller begyndelsespunktet for kanten e, og toppunktet y kaldes terminalen, afsluttende toppunkt eller terminalpunkt. For eksempel kan et vejnetværk, der forbinder et sæt byer ved hjælp af envejsveje, repræsenteres ved hjælp af en ikke-rettet 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, som trafikken strømmer 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 kanten, der forbinder de to hjørner. På den anden side er en kant i en ikke-rettet graf et uordnet par, da der ikke er nogen retning forbundet med en kant. Ikke-dirigerede grafer kan bruges til at repræsentere symmetriske forhold mellem objekter. In-grad og ud-grad af hver node i en ikke-rettet graf er lige, men dette gælder ikke 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 gælder ikke for en rettet graf. En ikke-rettet graf kan konverteres til en rettet graf ved at erstatte hver kant med to rettet kanter, der går i modsat retning. Det er imidlertid ikke muligt at konvertere en rettet graf til en ikke-rettet graf.