Transcript
Graphentheorie
Pru ¨ fungsstoff
1. Du verstehst den Begriff des ungerichtete Graphen: Eine ungerichteter Graph besteht aus einer Menge von Knoten V (oder Ecken) und eine Menge von Kanten E, die jeweils zwei Knoten aus der Knotenmenge verbinden. Die Symbolik ist zugegebenermassen etwas verwirrend, da traditionellerweise die englischen Bezeichnungen V (f¨ ur vertices=Ecken) und E (f¨ ur edges=Kanten) verwendet werden. Du kannst ferner Graphen zeichnerisch darstellen und weisst, dass die konkrete Darstellung eines Graphen (durch Kreise und Verbindungsstrecken) nicht eindeutig ist. 2. Zur Abgrenzung solltest du auch den Begriff des gerichteten Graphen kennen, wo die Kante von Knoten A nach Knoten B nicht dasselbe ist, wie die Kante von Knoten B zum Knoten A. In der der zeichnerischen Darstellung werden die Kanten nicht durch Strecken sondern durch Pfeile dargestellt. Jeder ungerichtete Graph kann als Spezialfall eines gerichteten Graphen angesehen werden, in dem es zu jeder gerichteten Kante auch noch die Kante in der Gegenrichtung gibt. Vorl¨aufig werden wir im Unterricht aber nur ungerichtete Graphen behandeln. 3. Du kannst mindestens drei Beispiele aus verschiedenen Bereichen unserer t¨aglichen Lebens angeben, die man mit Hilfe von Graphen vereinfacht darstellen und untersuchen kann. 4. Du kannst geeignete Graphen u ¨berschneidungsfrei darstellen; d. h. pl¨atten. 5. Du kannst die zwei Spezialf¨alle bei Kanten beschreiben: • Reflexive Kante (oder Schlinge): Eine Kante, die einen Knoten mit sich selbst verbindet. • Parallelkante (oder Mehrfachkante): mehrere Kanten, die dieselben zwei Knoten verbinden. Wenn nichts anderes vorausgesetzt wird, haben die betrachteten Graphen jedoch weder Parallelkanten noch reflexive Kanten. 6. Du kennst den Begriff des Pfads in einem Graphen und kannst seine L¨ange (die Anzahl der Kanten vom ersten zum letzten Knoten) bestimmen. Bemerkung: Der Pfadbegriff wird in der Literatur nicht immer einheitlich definiert, weshalb in der Pr¨ ufung keine spitzfindigen Fragen zum Pfadbegriff vorkommen werden. 7. Du kannst einfache Zyklen in einem Graphen erkennen. 8. Du kannst die Zusammenhangskomponenten eines Graphen angeben und weisst, was isolierte Knoten sind. 9. Du kannst den Grad eines Knoten und den Grad eines Graphen angeben. Du kennst insbesondere den Zusammenhang zwischen dem Grad und er Kantenzahl eines Graphen ohne reflexive und parallele Kanten angeben. 10. Du kannst beschreiben, was in der Graphentheorie ein Baum und was ein Wald ist.
11. Du kannst beschreiben, was ein Spannbaum und was ein Spannwald ist. 12. Du kannst einen Graphen ohne Parallelkanten als Adjazenzmatrix darstellen. 13. Du kannst einen Graphen als Adjazenzliste darstellen. 14. Du weisst, was ein vollst¨andiger Graph ist und kannst seinen Grad berechnen. 15. Du kannst die Dichte eines (nicht zu grossen) Graphen bestimmen. 16. Du kannst den Code unserer Python-Klasse Graph interpretieren. 17. Du kannst mit dem Algorithmus von Jarnik, Prim und Dijkstra minimale Spannb¨aume in einem Graphen mit Kantengewichten bestimmen. 18. Du kannst mit dem Algorithmus von Kruskal minimale Spannb¨aume in einem Graphen mit Kantengewichten bestimmen. 19. Du kannst aufgrund einer Adjazenzliste und ausgehend von einem Startknoten den Ablauf einer Tiefensuche beschreiben und den dazu geh¨orenden Spannbaum zeichnen. 20. Du kannst aufgrund einer Adjazenzliste und ausgehend von einem Startknoten den Ablauf einer Breitensuche beschreiben und den dazu geh¨orenden Spannbaum zeichnen.
