samenhangende grafen
samenhangende grafen
Als je tussen elk paar knopen in een graaf een wandeling kunt bepalen, noemen we de graaf samenhangend.
In onderstaande graaf is dat duidelijk het geval. Twee cykels zijn er verbonden door de boog CE.
bruggen
Merk op dat je vanuit de knopen A, B of C de punten D, E en F enkel kunt bereiken via de boog tussen C en E. Verwijder je deze boog dan is de graaf niet meer samenhangend. Deze boog noemen we een brug.
Omdat de boog CE niet in een cykel ligt, is er geen alternatief: Een brug ligt nooit in een cykel.