Tweedelige graaf

Hallo iedereen

Ik zit met een probleem bij het vak Discrete Wiskunde 1. In een oud examen komt de term 'tweedelige graaf' voor. Ik vind echter nergens wat dat zou kunnen betekenen. Misschien dat de graaf uit 2 niet-geconnecteerde componenten bestaat?

En de volgende vraag is dan: 'Is een boom met minstens 2 knopen altijd tweedelig?' Zo ja: bewijs. (Wat ik dus niet kan oplossen omdat ik niet weet wat tweedelig betekent)..

Alvast bedankt!

Jan De
Student universiteit België - dinsdag 12 augustus 2014

Antwoord

Een tweegedeelde/tweedelings/bipartiete graaf is er een waarvan je de punten in twee niet-lege onafhankelijke verzamelingen kunt opdelen.
Het antwoord op je tweede vraag is ja: kies een punt vast en verdeel de punten in twee groepen: die met een oneven afstand tot dat punt en die met een even afstand.

Zie Wikipedia: bipartite graph

kphart
woensdag 13 augustus 2014

©2001-2024 WisFaq