Voor de opleidingscommissie moeten er studenten verkozen worden om de studentengeleding te vertegenwoordigen. Niet elke student kan zich echter vinden in de meningen van elke andere student. We zijn dus op zoek naar een minimale verzameling studenten zodat elke student zich door minstens één van de geselecteerde ‘vertegenwoordigd’ voelt, of zelf een vertegenwoordiger is.

We modelleren het probleem aan de hand van een graaf waarbij studenten de toppen zijn (genummerd van \(0\) tot \(n\)), en er een boog is tussen elke twee studenten die zich kunnen vinden in elkaars standpunten. We gaan er dus vanuit dat dit een symmetrische relatie is.

Implementeer hiervoor de interface Vertegenwoordigers¹ in een klasse MyVertegenwoordigers. Deze vereist een methode Collection<Integer> optimaleSelectie(BitGraph graph), die een optimale vertegenwoordiging berekent voor de meegegeven graaf. Dat wil zeggen: een lijst met indices van de toppen in een optimale selectie. Eender welke selectie die het minimum bereikt volstaat. De graaf is van het type BitGraph², die adjacentie bijhoudt aan de hand van bitverzamelingen: de lijst van buren en niet-buren is voor elke top opgeslagen in een BitSet. Dit laat toe om op zeer efficiënte wijze unies, doorsnedes en verschillen te berekenen van deelverzamelingen van \(\{0,\dots ,n-1\}\). Zie de Java documentatie³ voor meer info.

Met behulp van SimpleTest⁴ kan je jouw oplossing lokaal uittesten.