ich häng grad an der Induktion und Valenzsequenz. wenn du da nen Tipp hast wo ich gut erklärte Beispiele finde, wär klasse.
Induktion werde ich nicht machen. Habe zwar verstanden, wie es geht, aber dass ist mir zu viel um-die-Ecke-denken.
Aber bei Valenzsequenzen könnte dir sicher hier geholfen werden.
Nimm mal die Aufgabe 3 aus Übungsklausur 8 (Datei 1142KW10).
Du bekommst bei so einer Aufgabe immer eine - geordnete(!) - Liste mit Knotengraden für Knoten (V) eines Graphen.
Erste Prüfung: Summe aller Knotengrade muss gerade sein (tatsächliche Summe nicht wichtig, es reicht, wenn die Anzahl aller ungeraden Knoten selbst wieder gerade ist). Wenn das stimmt geht's weiter, sonst ist es keine Valenzsequenz.
Am Beispiel der obigen Aufgabe: 10 Knoten (n= 10) Knotengrad des ersten Knotens = 9 (d = 9).
Es gilt für jede Zeile: d+1 <= n, sonst Abbruch.
In diesem Fall: 9+1 <= 10, also weiter.
Weiter heisst: ersten Knoten streichen, und die ersten d verbleibenden Knotengrade um 1 reduzieren.
In diesem Fall: alle 9 der verbleibenden 9 Knotengrade um 1 reduzieren.
Prüfe: 7 + 1 <= 9, also weiter
Ersten Knoten streichen, dann die ersten 7 der verbleibenden 8 Knotengrade um 1 reduzieren.
Dadurch ist die Liste nicht mehr sortiert, denn der 8. Knoten wurde nicht reduziert und hat nun einen höheren Grad als die Knoten 6 und 7.
Also: umsortieren
Dann: Prüfe: 4+1 <= 8, also weiter
Ersten Knoten streichen, dann die ersten 4 der verbleibenden 7 Knotengrade um 1 reduzieren.
Liste ist wieder nicht sortiert, also umsortieren
Dann: Prüfe: 3 + 1 <= 7, also weiter
Ersten Knoten streichen, dann die ersten 3 der verbleibenden 6 Knotengrade um 1 reduzieren.
Prüfe: 2 + 1 <= 6, also weiter
Ersten Knoten streichen, dann die ersten 2 der verbleibenden 5 Knotengrade um 1 reduzieren.
Jetzt: Abbruch, denn die Reduzierung führt zu negativen Knotengraden, was in diesem Universum nicht geht