Planarity

Kijk. Weer zo’n verslavend flash dingetje: Planarity! Je moet gewoon de knopen (edges) verslepen zodat de lijnen tussen de knopen (vertices) elkaar niet meer snijden. In het begin lijkt dat eenvoudig, maar het wordt al snel moeilijker.

Ondertussen zijn er zelfs mensen die een generische oplossing hebben bedacht voor dit probleem.

  1. Neem één knoop en maak met de kinderen van die knoop een planaire graaf.
  2. Breidt de graaf uit met een nieuwe knoop en zijn kinderen.
  3. Zorg ervoor dat de uitgebreide graaf planair is

Stappen één tot en met 3 te herhalen tot de volledige graaf planair is.

Heb ik al gezegd dat grafen cool zijn?

3 replies

Commentaar is gesloten