Programmierpraktikum Diskrete Optimierung (Modul P2C1)

← Semesterübersicht

Thema: Graphenisomorphie

Abschlusspräsentation: Die Präsentation der Programme ist für Montag, den 6.7., 16:00 Uhr s.t. geplant. Jeder Teilnehmer soll dabei in 10 bis 15 Minuten das von ihm betrachtete Verfahren, seine Implementierung sowie experimentelle Ergebnisse vorstellen.

Terminplan für die Abschlusspräsentation:

• 16:00 Antonia Ellerbrock
• 16:15 Markus Kleinau
• 16:30 Linnea Leuze
• 16:45 Simon Blasinski
• 17:00 Timo Brand
• 17:15 Jan Sebastian Walter

Einstiegsaufgabe: Implementieren Sie einen Backtracking-Algorithmus, der Graphisomorphie testet. Der Algorithmus soll die jeweils ersten i Knoten des ersten Graphen auf die ersten i Knoten des zweiten Graphen abbilden und für die Wahl des i+1-ten Knoten die Adjazenz zu den bisherigen Knoten beachten. Mögliche, aber nicht notwendige Ausbaustufen: Geschickte Wahl des i+1-ten Knotens, Gradbedingungen etc.

Testinstanzen: Hier finden Sie einige Testinstanzen. Die Dateien enthalten in der ersten Zeile eine Knotenzahl n. In jeder weiteren Zeile wird genau eine Kante durch die Nummern ihrer Endknoten bestimmt, wobei alle Knoten von 0 bis n-1 nummeriert seien. Dieses Datenformat wurde bereits in der Vorlesung Algorithmische Mathematik I verwendet (siehe hier) und kann mit den dort eingeführten Einleseroutinen eingelesen werden.

• Instanz 1
• Instanz 2
• Instanz 3
• Instanz 4
• Instanz 5
• Instanz 6
• Instanz 7
• Instanz 8
• Instanz 9
• Instanz 10
• Instanz 11
• Instanz 12
• Instanz 13
• Instanz 14
• Instanz 15
• Instanz 16

• Aufgabe 1 (Antonia Ellerbrock): Isomorphie von Intervallgraphen
  Algorithmus von Lueker und Booth, wie in deren Arbeit beschrieben.
  Betreuer: Siad Daboul
• Aufgabe 2 (Markus Kleinau): Exakter Isomorphietest
  Algorithmus von Corneil und Gotlieb
  Betreuer: Siad Daboul
• Aufgabe 3 (Linnea Leuze): Local Weisfeiler Lehman Algorithmus
  Arbeit von Morris und Mutzel 2019, Vergleich k-dim vs local
  Betreuer: Benjamin Klotz
• Aufgabe 4 (Simon Blasinski): Erzeuge Liste aller nicht-isomorphen Graphen mit Eigenschaft Pi
  Arbeiten von Read sowie Colbourn+Read, Ergebnis sollte verglichen werden mit der sehr effizienten Implementierung von McKay (makeg)
  Betreuer: Stefan Rabenstein
• Aufgabe 5 (Timo Brand): Practical Graph Isomorphism
  Arbeit von McKay, in der die wesentliche Funktionsweise von Nauty beschrieben wird.
  Betreuer: Stefan Rabenstein
• Aufgabe 6 (Jan Sebastian Walter): Largest Common Subgraph
  Arbeit von Koch (via Clique Reduction) und Cuissart et al (direkter Ansatz)
  Betreuer: Benjamin Klotz