Onafhankelijke verzameling van maximale grootte

Hoi,

Met behulp van puntkleuringen in een graaf is het mogelijk wiskundige problemen op te lossen. Bij zulke problemen wordt gezocht naar onafhankelijke verzamelingen van maximale grootte of een puntkleuring met een minimaal aantal verschillende kleuren. Nu vroeg ik mij af: Wat houdt een onafhankelijke verzameling van maximale grootte in?

renate
Leerling bovenbouw havo-vwo - zaterdag 28 november 2009

Antwoord

Precies wat de term zegt: het is

1. een onafhankelijke verzameling in de graaf; staat die definitie niet ergens opgeschreven? (Ik vermoed dat het een verzameling punten is die onderling niet verbonden zijn door een tak.)

2. van maximale grootte: er is geen onafhenkelijke verzameling met meer punten.

kphart
vrijdag 4 december 2009

©2001-2024 WisFaq