Verschil tussen Gerichte en niet-gerichte grafiek

Gericht versus niet-geleide grafiek

Een grafiek is een wiskundige structuur die bestaat uit een verzameling hoekpunten en randen. Een grafiek vertegenwoordigt een reeks objecten (vertegenwoordigd door hoekpunten) die zijn verbonden via enkele links (weergegeven door randen). Met behulp van wiskundige notaties kan een grafiek worden weergegeven met G, waarbij G = (V, E) en V de verzameling hoekpunten is en E de reeks randen is. In een niet-gerichte grafiek is er geen richting aan de randen die de hoekpunten verbinden. In een gerichte graaf is er een richting geassocieerd met de randen die de hoekpunten verbinden.

Niet-gerichte grafiek

Zoals eerder vermeld, is een niet-gerichte grafiek een grafiek waarin er geen richting in de randen is die de hoekpunten in de grafiek met elkaar verbindt. Figuur 1 geeft een niet-gerichte grafiek weer met een set hoekpunten V = V1, V2, V3. De 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 verhindert als V = (V2, V1), (V3, V2), (V3, V1) omdat de randen geen richting hebben. Daarom zijn randen in een niet-gerichte grafiek geen geordende paren. Dit is het belangrijkste kenmerk van een ongerichte grafiek. Niet-gerichte grafieken kunnen worden gebruikt om symmetrische relaties tussen objecten weer te geven die worden vertegenwoordigd door hoekpunten. Een tweerichtingswegennetwerk dat een reeks steden 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 grafiek is een grafiek waarin de randen in de grafiek die de hoekpunten verbinden, een richting hebben. Figuur 2 geeft een gerichte grafiek weer met set van hoekpunten V = V1, V2, V3. De reeks randen in de bovenstaande grafiek kan worden geschreven als V = (V1, V2), (V2, V3), (V1, V3). Randen in een niet-gerichte grafiek zijn geordende paren. Formeel kan rand e in een gerichte grafiek worden weergegeven door het geordende paar e = (x, y) waarbij x de vertex is die de oorsprong, bron of het beginpunt van de rand e wordt genoemd, en hoekpunt y de terminus wordt genoemd , eindigende vertex of eindpunt. Een wegennetwerk dat een reeks steden met eenrichtingswegen verbindt, kan bijvoorbeeld worden weergegeven met een ongerichte grafiek. De steden kunnen worden weergegeven door de hoekpunten in de grafiek en de gerichte randen geven de wegen weer die de steden met elkaar verbinden gezien de richting waarin het verkeer in de weg stroomt.

Wat is het verschil tussen Directed Graph en Undirected Graph?

In een gerichte grafiek is een rand een geordend paar, waarbij het geordende paar de richting van de rand vertegenwoordigt die de twee hoekpunten met elkaar verbindt. Aan de andere kant is een rand in een niet-gerichte grafiek een ongeordend paar, omdat er geen richting aan een rand is gekoppeld. Niet-gerichte grafieken kunnen worden gebruikt om symmetrische relaties tussen objecten weer te geven. In-graden en out-graden van elk knooppunt in een niet-gerichte grafiek is gelijk, maar dit is niet het geval voor een gerichte grafiek. Wanneer een matrix wordt gebruikt om een ​​niet-gerichte grafiek weer te geven, wordt de matrix altijd een symmetrische grafiek, maar dit is niet het geval voor gerichte grafieken. Een niet-gerichte grafiek kan worden geconverteerd naar een gerichte grafiek door elke rand te vervangen door twee gerichte randen die in tegenovergestelde richting gaan. Het is echter niet mogelijk om een ​​gerichte grafiek naar een niet-gerichte grafiek om te zetten.