Minimaliseren van het aantal kruisingen in een multi-level graaf

In deze scriptie bestuderen we het aantal kruisingen in een graaf waarbij de knopen in verschillende horizontale levels verdeeld zijn, ook wel het MLCM (Multi-Level Crossing Minimization) probleem genoemd. Vaak wordt een gerichte graaf afgebeeld als een multi-level graaf. We bekijken een voorbeeld van een gerichte graaf: de stamboom van TU Delft medewerkers bij de afdeling Toegepaste Wiskunde, die ontwikkeld is door Kees Roos. In deze stamboom zitten veel kruisingen waardoor de graaf niet heel goed leesbaar is. Door het aantal kruisingen te minimaliseren zal dit verbeterd worden. Dit doen we door de knopen in nieuwe horizontale levels te verdelen en de knopen in de levels in een andere volgorde te zetten. Om een ordening van de knopen in de levels te vinden waardoor het aantal kruisingen minimaal is, zullen we het probleem omschrijven als een semi-definiet programma (SDP). Maar voordat we zover zijn stellen we eerst een integer lineair programma (ILP) op waarop onze SDP is gebaseerd. Voor het SDP moeten we een kostenmatrix defini ëren die het aantal kruisingen tussen twee levels weergeeft. Daarnaast moeten we voorwaarden opstellen zodat de ordening in de levels ook toegelaten is. Omdat het SDP erg moeilijk op te lossen is, gaan we kijken naar een relaxatie. Deze relaxatie is nog erg zwak en zullen we versterken met meer voorwaarden. Uiteindelijk krijgen we een relaxatie die sterker is dan de lineaire relaxatie van het ILP. Na het vinden van de sterke SDP-relaxatie willen we het probleem natuurlijk oplossen. We gebruiken hierbij twee verschillende oplossingsmethoden om alle voorwaarden mee te kunnen nemen. Ten slotte wordt dit allemaal gebruikt om de stamboom beter leesbaar te maken.Electrical Engineering, Mathematics and Computer ScienceDelft Institute of Applied Mathematics (DIAM