Gerichte versus ongerichte grafiek
Een grafiek is een wiskundige structuur die bestaat uit een reeks hoekpunten en randen. Een grafiek vertegenwoordigt een reeks objecten (weergegeven door hoekpunten) die zijn verbonden via enkele koppelingen (weergegeven door randen). Met behulp van wiskundige notaties kan een grafiek worden weergegeven door G, waarbij G=(V, E) en V de reeks hoekpunten is en E de reeks 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 graaf waarin er geen richting is in de randen die de hoekpunten in de graaf verbinden. Figuur 1 toont een ongerichte grafiek met een reeks hoekpunten V={V1, V2, V3}. Reeks randen in de bovenstaande grafiek kan worden geschreven als V={(V1, V2), (V2, V3), (V1, V3)}. Er kan ook worden opgemerkt dat er niets is dat 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 graaf waarin de randen in de graaf die de hoekpunten verbinden een richting hebben. Figuur 2 toont een gerichte grafiek met een reeks hoekpunten V={V1, V2, V3}. Reeks randen in de bovenstaande grafiek kan worden geschreven als V={(V1, V2), (V2, V3), (V1, V3)}. Randen in een ongerichte graaf 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, bron of het beginpunt van de rand e wordt genoemd, en hoekpunt y het eindpunt wordt genoemd, eindigend hoekpunt 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 verbinden, rekening houdend met de richting waarin het verkeer op de weg stroomt.
Wat is het verschil tussen gerichte grafiek en ongerichte grafiek?
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, in een ongerichte graaf, is een rand een ongeordend paar, omdat 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. Wanneer een matrix wordt 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 omgezet in een gerichte graaf door elke rand te vervangen door twee gerichte randen die in tegengestelde richting gaan. Het is echter niet mogelijk om een gerichte graaf om te zetten in een ongerichte graaf.
