Wir haben Graphen als Modell für unser Problem gewählt. Da der Rechner schließlich die Berechnung übernehmen soll, brauchen wir noch eine Möglichkeit, Graphen im Rechner darzustellen. Wir verwenden dafür Adjazenzmatrizen. Eine Adjazenzmatrix ist eine "Tabelle", in der aufgeführt wird, welche Knoten "in Verbindung miteinander" stehen.
Genauer: Bei einer Adjazenzmatrix steht jeweils eine Zeile und Spalte für einen Knoten. Wenn von Knoten A zu Knoten B eine Kante verläuft, wird in der Matrix in der zu A gehörigen Zeile in der zu B gehörigen Spalte eine 1 eingetragen. Wenn von A nach B keine Kante verläuft, wird an dieser Stelle eine 0 eingetragen.
Finde selbst Eigenschaften der Adjazenzmatrizen anhand der verschiedenen Beispiele heraus. Probiere erst die ungerichteten Graphen aus.
©2005 Anne Geschke, Ulrich Kortenkamp, Dirk Materlik. Technische Universität Berlin, DFG-Forschungszentrum Matheon