Home » Uncategorized » Wat is een gewogen graaf

Wat is een gewogen graaf

Berichten over gewogen graaf geschreven door The Kimchi Lover. Een graaf met gewichten noemt men een gewogen graaf. Wat dat eerste betreft zijn planaire grafen dan ook bij het grotere publiek bekend in de vorm van puzzeltjes zoals probeer drie huizen aan te sluiten op de gas-, water- en elektra-bronnen, zonder dat enige van de leidingen elkaar snijden. Voor een ongerichte, niet- gewogen graaf met n knopen en p bogen, is de incidentiematrix een n bij p matrix waarin het element op de i-de rij en j-de kolom gelijk is aan:. Ook worden wel gewichten aan de lijnen toegekend door middel van getallen, deze stellen dan bijvoorbeeld de afstand tussen twee punten voor.

De lijnen noemen we verbindingen. In de verbindingen kunnen pijltjes staan. Dan is het een gerichte graaf. Als er getallen bij de verbindingen staan, is het een gewogen graaf. Punten van een graaf kunnen van alles zijn.

Zoals: mensen, dieren, steden , . Meestal gaat het in een graaf er alleen om óf er verbinding is tussen twee knooppunten. Het simpelste voorbeeld is natuurlijk de verbindingen tussen een aantal steden. Je kunt aangeven óf er een directe verbinding is . Structuren die als grafen weergegeven kunnen worden zijn alomtegenwoordig en veel praktische problemen kunnen als een probleem op een graaf worden gemodelleerd.

Grafen worden bijvoorbeeld gebruikt om eindigetoestandsautomaten te modelleren of om . De verbindingsmatrix en een algemener graafbegrip 54. Wandelen in een graaf 58. Routes waarin elke lijn precies eenmaal voorkomt 68. Fase 2: het kortste-pad-probleem oplossen. Vertrek van een gewogen graaf – bijvoorbeeld één van de grafen hierboven, of maak er eentje met wat steden en verbindingswegen op: geef ook de afstanden die erbij horen.

Laat de leerlingen individueel of in kleine groepjes op die graaf een kortste pad zoeken tussen twee. Deze drie soorten grafen hadden we al gehad. Er zijn situaties waarbij in een graaf een directe weg loopt van een knooppunt naar datzelfde knooppunt.