Speciale gerichte grafen

Speciale gerichte grafen
Promotor: Gunnar Brinkmann
Gerichte grafen hebben vele toepassingen waarvan sommigen zeker minder voor de
hand liggen dan anderen. De volgende figuur toont bv. een toepassing in de scheikunde
waar gerichte grafen waar in elke top ten hoogste 2 bogen toekomen en vertrekken (en
geen twee gerichte bogen dezelfde toppen verbinden) modellen zijn van clusters van watermoleculen.
molecuul A
−−
+
vertaald:
A
+
molecuul B −−
+
B
+
Er bestaan heel snelle programma’s die alle isomorfieklassen van gerichte grafen met
een gegeven aantal toppen kunnen opsommen. Deze programma’s bepalen soms meer
dan 500.000.000 grafen per seconde. Maar als er beperkende voorwaarden aan de grafen
worden opgelegd (zoals: geen korte gerichte cykels) is het zeer ineffici¨ent alle grafen te
filteren en moeten gespecialiseerde algoritmen en programma’s ontwikkeld worden. En
dat is het onderwerp van dit project. . .
Meer uitleg kan natuurlijk aan de promotor gevraagd worden.

Download Report