Lernfabrik
Übung

Aufgaben und Übungen

Vertiefe dein Wissen zur Graphentheorie und zum Traveling-Salesman-Problem mit vier praxisnahen Aufgaben – von einfach bis anspruchsvoll.

Aufgabe 1 · Graphen und Routenberechnung

Einfach

Gegeben sei folgender Graph:

Graph zur Aufgabe 1
  1. a Erstelle zugehörig zum Graphen die entsprechende Adjazenzmatrix.
  2. b Schreibe alle möglichen Touren mit Hilfe einer Baumstruktur auf und berechne deren Länge.
  3. c Gib die allgemeine Formel zur Berechnung der Anzahl aller möglichen Rundreisen an und führe die Berechnung für die Anzahl der Routen aus der obigen Aufgabenstellung durch.
  4. d Zeige auf, welche Route nach der Nearest-Neighbour-Methodik gewählt werden würde.
Bearbeitungszeit ca. 15–20 Minuten

Aufgabe 2 · Adjazenzmatrix und Graphen

Mittel

Gegeben sei folgende Adjazenzmatrix:

Adjazenzmatrix zur Aufgabe 2
  1. a Erstelle zur Adjazenzmatrix auf dem Blatt den entsprechenden Graphen.
  2. b Schreibe alle möglichen Touren mit Hilfe einer Baumstruktur auf und berechne die Länge der Touren.
  3. c Gib die allgemeine Formel zur Berechnung der Anzahl aller möglichen Rundreisen an und führe die Berechnung für die Anzahl der Routen aus der obigen Aufgabenstellung durch.
  4. d Schreibe die Route nach der Nearest-Neighbour-Methodik auf dem Blatt auf (markiere die Strecke mit einer anderen Farbe).

Aufgabe 3 · TSP Solver

Fortgeschritten

Einsatz des Excel-Solvers zur Lösung des TSP.

  1. 1 Hinweis: Wie aktiviere ich den Solver in Excel? Lernvideo
  2. 2 Hinweis: TSP mit Excel-Solver lösen – Lernvideo
  3. 3 Nutze folgende Vorlage tsp_solver.xlsx und berechne eine zumindest suboptimale Route mit Hilfe des Excel-Solvers.

Aufgabe 4 · Rundreise Bonn

Anspruchsvoll

Gegeben sei folgende Adjazenzmatrix:

Adjazenzmatrix zur Aufgabe 4
  1. a Versuche, eine möglichst kurze Rundreise mit Start- und Zielort Bonn zu finden. Bestimme auch die Gesamtlänge der Rundreise.
  2. b Wie lang ist die optimale Tour?
  3. c Berechne die Anzahl der möglichen Rundreisen.
Knobelaufgabe – hier ist Kombinationsgabe gefragt!