Kaartkleuren++

Status (25 April 2015)

Deze nadere (en uitgebreidere) advancedsectie van 'kaartkleuren' is geschreven met Heuristieken 2015a (mrt-apr 2015) voor Marten, Jenny en Jeroen.

Opdracht

Opdracht is het bepalen van het minimum aantal kleuren dat nodig is om een zekere graaf te kleuren. Het vermoeden is, dat er een verband is tussen het aantal kleuren, en sommige eigenschappen van de graaf, zoals de edgedichtheid en de cliquegrootte. Dit is een poging die relatie een gezicht te geven.

a) Maak een random grafen van 1000 vertices en edges van/tot [0,100,200,300 ... 499500]. Dit correspondeert met een edgedichtheid van 0% tot 100%. Kleur elke graaf en kijk hoeveel kleuren je nodig hebt. Meet in totaal vier gegevens: het gevonden minimumaantal kleuren, de rekentijd van je algoritme, maar ook het aantal aageroepen recursies en tenslotte de cliquegrootte. Doe het hele rijtje tien keer en maak van deze tien series één gecombineerde grafiek.

Als je dan nog fut hebt:

b) doe hetzelfde voor 2000 vertices met 200 edges. c) doe hetzelfde voor 5000 vertices met 500 edges. d) doe hetzelfde voor 10000 vertices met 1000 edges. e) doe hetzelfde voor 20000 vertices met 2000 edges. f) doe hetzelfde voor 50000 vertices met 5000 edges. g) doe hetzelfde voor 100000 vertices met 10000 edges.