TU Wien:Diskrete Mathematik für Informatik VU (Gittenberger)/Prüfung 2016-04-28

1.) Beweis. Mittels Handshake Lemma beweisen, dass wenn kein Knoten eines Baums Grad 2 hat, dass dann mehr als die Hälfte der Knoten Blätter sind. (20 Pkt)

2.) Es waren 10 Statements gegeben und man musste ankreuzen: Muss ein Baum sein | Kann kein Baum sein | Man kann nicht sagen obs ein Baum sein muss oder nicht. (20 Pkt)

Ein Statement war zB: Der Graph G hat 10 Knoten und 11 Kanten --> Lösung: kann kein Baum sein

3.) Definition von "Tournament" eines gerichteten Graphen war gegeben. Man musste irgendwas mit Transitivität beweisen. Angabe war ungefähr "Wenn jedes Knotenpaar genau einen arc besitzt, ist das Tournament nicht transitiv --> beweise das" (30 Pkt)

4.) Five color theorem hinschreiben und die keypoints des Beweises dafür skizzieren (30 Pkt)