Beispielgraphen

Beispielgraphen für die Praktika:

  • Ein kleiner, zwei mittlere, und drei große Graphen als Kantenliste.
    Format: Erste Zeile: Knotenanzahl; folgende Zeilen: Kanten (i->j, Nummerierung: 0 ... Knotenanzahl-1)
    Zur Kontrolle Ihrer Algorithmen: Graph 2 und 3 haben jeweils 4 Zusammenhangskomponenten, der große 222, der ganzgroße 9560 und der ganzganzgroße 306.
  • Gewichtete Graphen als Kantenliste für die Algorithmen von Prim und Kruskal:
    Format: Erste Zeile: Knotenanzahl; folgende Zeilen: Kanten und Gewicht (Nummerierung 0 ... Knotenanzahl-1)
    (G_x_y.txt ist ein Graph mit x tausend Knoten und y tausend Kanten)
  • Vollständige gewichtete Graphen als Kantenliste.
    Die Gewichte erfüllen die Dreiecks-Ungleichung.
    Format: Erste Zeile: Knotenanzahl; folgende Zeilen: Kanten und Gewicht (Nummerierung 0 ... Knotenanzahl-1)
    (K_x.txt ist ein vollständiger Graph mit x Knoten; bei K_xe sind die Daten Entfernungen von Punkten in der Ebene)
    Bei den kleinen Graphen stehen in Klammern die Längen der optimalen Rundreisen und meine Laufzeiten.