Gerichte versus niet-gerichte grafiek
Een grafiek is een wiskundige structuur die bestaat uit een reeks hoekpunten en randen. Een grafiek vertegenwoordigt een set objecten (vertegenwoordigd door hoekpunten) die zijn verbonden via enkele links (vertegenwoordigd door randen). Met behulp van wiskundige notaties kan een grafiek worden weergegeven door G, waarbij G = (V, E) en V de set hoekpunten is en E de set randen. In een ongerichte graaf is er geen richting geassocieerd met de randen die de hoekpunten verbinden. In een gerichte graaf is er een richting geassocieerd met de randen die de hoekpunten verbinden.
Ongerichte grafiek
Zoals eerder vermeld, is een ongerichte graaf een grafiek waarin er geen richting is in de randen die de hoekpunten in de grafiek met elkaar verbinden. Figuur 1 toont een ongerichte grafiek met een reeks hoekpunten V = {V1, V2, V3}. De set randen in de bovenstaande grafiek kan worden geschreven als V = {(V1, V2), (V2, V3), (V1, V3)}. Er kan ook worden opgemerkt dat niets het schrijven van de reeks randen als V = {(V2, V1), (V3, V2), (V3, V1)} verhindert, aangezien de randen geen richting hebben. Daarom zijn randen in een ongerichte graaf geen geordende paren. Dit is het belangrijkste kenmerk van een ongerichte graaf. Ongerichte grafieken kunnen worden gebruikt om symmetrische relaties weer te geven tussen objecten die worden weergegeven door hoekpunten. Een tweerichtingswegennet dat een reeks steden met elkaar verbindt, kan bijvoorbeeld worden weergegeven met een ongerichte grafiek. De steden kunnen worden weergegeven door de hoekpunten in de grafiek en de randen vertegenwoordigen de tweerichtingswegen die de steden met elkaar verbinden.
Gerichte grafiek
Een gerichte graaf is een grafiek waarin de randen in de grafiek die de hoekpunten verbinden een richting hebben. Figuur 2 toont een gerichte grafiek met een reeks hoekpunten V = {V1, V2, V3}. De set randen in de bovenstaande grafiek kan worden geschreven als V = {(V1, V2), (V2, V3), (V1, V3)}. Randen in een ongerichte grafiek zijn geordende paren. Formeel kan rand e in een gerichte graaf worden weergegeven door het geordende paar e = (x, y) waarbij x het hoekpunt is dat de oorsprong, de bron of het beginpunt van de rand e wordt genoemd, en het hoekpunt y het eindpunt wordt genoemd., eindpunt of eindpunt. Een wegennetwerk dat een reeks steden met elkaar verbindt via eenrichtingswegen, kan bijvoorbeeld worden weergegeven met een ongerichte grafiek. De steden kunnen worden weergegeven door de hoekpunten in de grafiek en de gerichte randen vertegenwoordigen de wegen die de steden met elkaar verbinden gezien de richting waarin het verkeer op de weg stroomt.
Wat is het verschil tussen Directed Graph en Undirected Graph?
In een gerichte graaf is een rand een geordend paar, waarbij het geordende paar de richting vertegenwoordigt van de rand die de twee hoekpunten verbindt. Aan de andere kant is een rand in een niet-gerichte graaf een ongeordend paar, aangezien er geen richting is gekoppeld aan een rand. Ongerichte grafieken kunnen worden gebruikt om symmetrische relaties tussen objecten weer te geven. In-graad en uit-graad van elk knooppunt in een ongerichte graaf is gelijk, maar dit geldt niet voor een gerichte graaf. Als je een matrix gebruikt om een ongerichte graaf weer te geven, wordt de matrix altijd een symmetrische graaf, maar dit geldt niet voor een gerichte graaf. Een ongerichte graaf kan worden geconverteerd naar een gerichte graaf door elke rand te vervangen door twee gerichte randen die in tegengestelde richting lopen. Het is echter niet mogelijk om een gerichte graaf naar een niet-gerichte graaf te converteren.
