Graphentheorie: Aufgaben mit Lösungen

Hier rechnest du mit Knoten, Kanten und Wegen. Wähle oben eine Aufgabenart oder lass sie gemischt. Mit „Neue Aufgaben“ entsteht ein neues Blatt.

Das brauchst du

• Handschlaglemma: Die Summe aller Knotengrade ist das Doppelte der Kantenzahl.
• Euler: Ein zusammenhängender Graph hat einen Euler-Kreis genau dann, wenn alle Grade gerade sind, und einen Euler-Weg genau dann, wenn höchstens zwei Knoten ungeraden Grad haben.
• Zählen: K_n hat n(n − 1)/2 Kanten, ein Baum mit n Knoten hat n − 1 Kanten, K_m,n hat m·n Kanten, K_n hat (n − 1)!/2 Hamilton-Kreise.
• Adjazenzmatrix: Der Eintrag (i, j) von A^k zählt die Wege der Länge k von i nach j.
• Dijkstra: Beginne beim Startknoten mit Abstand 0, setze immer den Knoten mit kleinstem vorläufigem Abstand endgültig und verbessere die Abstände seiner Nachbarn.

Alles steht auf der Seite Graphentheorie beim Handschlaglemma, bei Bäumen, Euler, den Hamilton-Kreisen und bei Dijkstra.