Prüfungsvorbereitung Graphentheorie?
Ich schreibe am Dienstag eine Prüfung Grundlagen Graphentheorie (Informatik, 5. Semester, FH).
Ich bin an sich gut vorbereitet, kann eigentlich den ganzen behandelten Stoff und hab mir auch Übungsblätter angeschaut und konnte die lösen.
Mein Problem ist, dass unser Dozent gerne richtig exotische Beweise dran nimmt als Aufgabe (oder Aufgaben, wo man irgendwelche Dinge zeigen muss). Allerdings ist es bei solchen Aufgaben oft so, dass man die ohne den richtigen Ansatz nicht lösen kann. Und ich komme da nie auf den Ansatz, außer wenn es irgendein Induktionsbeweis ist vielleicht.
Kennt jemand vielleicht ein Buch / eine PDF oder andere Quelle, wo das allerwichtigste zu Graphentheorie irgendwie zusammengefasst ist? Oder wo man so grundlegende Beweise hat mit Erklärung?
Beispielaufgabe vom Übungsblatt:
Zeigen Sie: Hat ein Graph mindestens eine Kante, so ist die Summe der Koeffizienten seines chromatischen Polynoms gleich Null.
Ich würde da keinen Ansatz finden, außer halt rumprobieren und bspw. für einen Graphen sagen können, dass es gilt.
1 Antwort
Ich hatte vor 5 Minuten keine Ahnung von dem Problem und 2 Ideen
1. Es müsste aus dem Reduktionssatz induktiv folgen.
2..die Interpretation von P(1) . Meine Idee ist das Polynom P(n) liefert mir die Anzahl der Färbung mit n Farben ?