Wiskunde 123

Zoeken


Grafentheorie

Moeilijkheidsgraaad:

Een graaf is een verzameling punten waarvan er sommige met elkaar verbonden kunnen zijn door verbindingen (lijnen). De verbinding tussen 2 punten noemen we een weg. (bijv. de lijn tussen punt C en punt D)

De graad van een punt is het aantal wegen dat verbonden is met dat betreffende punt. Vb. B is verbonden met 2 punten, nl. A en D. De graad van B is dus 2.

Het maximum van de graden van de punten van de graaf is de graad van de graaf.

Vb. De graad van de graaf is hier 3. C is met 2 punten verbonden. (A en D) B is ook met 2 punten verbonden (A en D). A (C,B,D) is met 3 punten verbonden en D (A,B,C) ook. Dus de hoogste graad (3 bij A en D) is de graad van de graaf.

Een volledige graaf bestaat uit een aantal punten en bovendien alle mogelijke wegen tussen die punten. Dit is een volledige graaf want alle punten zijn met elkaar verbonden, dmv rechtstreekse lijnen.

Een samenhangende graaf is een graaf waarbij ieder tweetal punten door middel van een wandeling met elkaar verbonden is. Deze graaf is samenhangend want je kunt vanaf ieder punt via de wegen bij elk ander punt komen.

Twee grafen zijn isomorf als het dezelfde grafen zijn alleen op een verschillende manier getekend. Deze grafen zijn isomorf want ze hebben evenveel punten en evenveel wegen die allemaal naar dezelfde punten gaan.

Een graaf noemen we planair als hij zodanig in het platte vlak getekend kan worden dat de wegen elkaar alleen in de punten van de graaf snijden.

Een Eulerwandeling is een wandeling die iedere weg precies 1 keer bevat. (hier vanaf A > B > C > D > B > E > A > D > E.

Reacties

Ga naar de pagina met reacties bij dit artikel om meningen van anderen te bekijken en zelf je mening te geven over dit artikel.