Guten Morgen und herzlich willkommen zur letzten und sechsten Übung.
Bei diesem Übungsblatt ging es um das Hoare-Trippel, mit dem man für
bestimmte Gramme beweisen kann, dass die korrekt sind.
Und der zweite Teil des Übungsblatts ging über Grafen, die auch noch
im späteren Verlauf des Studiums sehr wichtig sein werden.
Wir fangen jetzt gleich mal mit Aufgabe 1 an.
Die Aufgabe 1 war eine sehr einfache Ausgabe zu den Hoare-Kalkülen.
Man hat ein einfaches Programm gegeben, das hier aus drei Anweisungen
besteht und hat eine Nachbedingung gegeben.
Man soll jetzt in den Kalkülen eine schwächste Vorbedingung bestimmen.
Wenn man sich jetzt noch mal anguckt, wie ein Hoare-Trippel aufgebaut
ist, hat man eine Vorbedingung, die nennt man meistens P. Danach
kommen verschiedene Anweisungen, die S heißen und danach kommt eine
Nachbedingung Q.
Es ist ein Kalkül, deswegen hat man da auch bestimmte Axiome und kann
Schlussfolgerungen treffen und da haben wir verschiedene Regeln
kennengelernt.
Wie man das jetzt bei dieser Aufgabe macht, man handelt sich von der
Nachbedingung, Anweisungen für Anweisungen nach oben durch in diesem
Fall und leitet immer eine Vorbedingung her.
Und das wollen wir jetzt machen.
Das heißt, wir fangen mit der ersten Anweisung an.
Also hier wäre es so, die Nachbedingung ist x gleich a und als
Vorbedingung hat man zudem soll y Nachablauf des Programms b sein.
Jetzt hat man die Anweisung gegeben, das ist jetzt die letzte
Anweisung des Programmstücks, dass x gleich y minus x sein muss.
Man hat jetzt eine Riegel kennengelernt, wenn man so ein einfaches
Programmstück hat, dass man einfach substituieren kann.
Dafür war die Substitution auch gut, die man beim letzten Übungsblatt
kennengelernt hat.
Das heißt, man substituiert in der Nachbedingung das x durch y minus x
und schreibt dann hin, dass die Vorbedingung dann sein muss y minus x
ist gleich a und y gleich b.
Und diesen Schritt führt man jetzt einfach für alle drei Anweisungen
weiter durch und kommt dann auf eine Vorbedingung.
Und dann kann man noch überlegen, ob die Vorbedingung auch wirklich
die schwächste ist.
Wir machen das jetzt noch weiter.
Die nächste Anweisung wäre dann,
x wird x mal y zugewiesen und man verwendet die Vorbedingung von da
oben, schreibt die wieder hin.
Letztendlich verändert sich für das y über das ganze Programm nichts
und substituiert hier wieder.
Man substituiert jetzt das x mit der Zuweisung x mal y und bekommt
dann sowas wie y minus x mal y ist gleich a.
Und bei y gleich b hat sich nichts geändert.
Beim dritten, jetzt hat man noch die letzte Anweisung übrig, da wird x
plus x wird x zugewiesen, nimmt man wieder die Vorbedingung von hier
oben, die hier steht, substituiert das x.
Dann hat man sowas wie y minus x plus x, muss man hier Klammern
setzen, mal y gleich a und y gleich b.
Jetzt kann man sich noch überlegen, ob das wirklich die schwächste
Vorbedingung ist.
Also die schwächste Vorbedingung ist die Vorbedingung, die alle
anderen gültigen Vorbedingungen impliziert.
Andersrum, die schwächste Vorbedingung ist die, wenn man eine andere
gültige Vorbedingung hat, kann man diese Vorbedingung damit
implizieren, also daraus diese Vorbedingung folge.
Und es ist relativ klar, dass wenn am Ende des Programms y gleich b
ist und man das y nicht ändert, dass dann am Anfang des Programms y
auch b sein muss.
Und für das a muss man ein bisschen länger überlegen, aber
letztendlich die Schritte, die wir gemacht haben, daraus kann man
folgen, dass man...
Wir haben den Trick gemacht und die Vorbedingung stärker gemacht,
deswegen ist das auch die schwächste Vorbedingung.
Gut, das war es soweit zur Aufgabe 6.1, das war eine relativ einfache
Aufgabe zum Horarkalkül.
Ja, solange die Vorbedingung immer noch eine gültige Vorbedingung ist,
dann ja.
Also mehr oder weniger die mathematischen Regeln gelten da immer noch.
Sonst noch Fragen zu der Aufgabe?
Gut, dann geht es weiter mit Aufgabe 2.
Bei Aufgabe 2 bleiben wir jetzt immer noch im Horarkalkül, nur jetzt
betrachten wir auch IF-Anweisungen.
Und was jetzt hier die Ausgabe ist, dass man schon eine Nachbedingung
gegeben hat.
Am Ende soll die Variable x der Betrag von b-a sein und man hat auch
eine Vorbedingung gegeben.
Am Anfang soll x gleich a sein und y gleich b sein.
Und wir sollen jetzt beweisen, dass dieses hoare Triple ein gültiges
Triple ist.
Letztendlich, was man jetzt hier machen kann, man kann sich den IF
-Zweig einzeln angucken.
Man geht wieder von hinten aus vor, guckt sich den IF- und den ELS
-Zweig einzeln ein, macht dann die gleiche Substitution, wie wir das
bei der Aufgabe davor gemacht haben.
Jetzt kann man, was ihr nachher noch sehen werdet, dass wir die
Vorbedingungen noch immer stärker machen können.
Das war auch eine Regel, dann bleibt es immer noch ein gültiges
Triple.
Und wir müssen halt noch die Regel für IF und ELS anwenden.
Und das werden wir jetzt beim Lösen dieser Aufgabe machen.
Also wir bleiben bei Aufgabe 6.2.
Und ich schreibe jetzt erstmal auf die linke Seite den IF-Fall und auf
die rechte Seite den ELS-Fall.
Für beide Fälle soll die gleiche Nachbedingung gelten.
Die Nachbedingung ist,
dass der Betrag von B-A sein soll.
Jetzt gucken wir uns erstmal den IF-Fall an.
Im IF-Fall war es so, dass X-Y den X zugewiesen wird.
Das schreiben wir jetzt wie vorhin auf und substituieren dann einfach.
Das war genau der gleiche Schritt, den wir in der vorherigen Aufgabe
dreimal gemacht haben.
Dann steht als Vorbedingung sowas da wie X-Y ist der Betrag von B-A.
Das gleiche machen wir jetzt für den ELS-Zweig.
Beim ELS-Zweig hatten wir die gleiche Nachbedingung.
Die Anweisung war folgender X-Y-X zugewiesen.
Wir substituieren wieder, setzen Y-X ein für das X und haben die
folgende Vorbedingung.
Jetzt ist es so, die Vorbedingung bleibt immer noch gültig, wenn man
die Vorbedingung strenger macht.
Wir haben hier oben bei der Aufgabe gegeben, dass man beweisen will,
dass die Vorbedingung X-A und Y-B eine gültige Vorbedingung ist.
Was wir jetzt machen, wir wenden die Regel an, dass wir die
Vorbedingung stärker machen müssen, sodass sie immer noch gültig ist.
Das heißt, wir können jetzt erstmal sagen, dass X gleich A ist und Y
gleich B.
Und das ist jetzt eine Vorbedingung, die ist aber noch nicht gültig,
weil das A X-Y könnte zum Beispiel negativ sein und dann kommt man
nicht mehr auf die Vorbedingung.
Das heißt, wir müssen noch eine dritte Gleichung in die Vorbedingung
einbügen und das wäre in diesem Fall, wenn ich mich nicht ganz
täusche, dass das X größer als das Y sein muss.
Was wir jetzt damit gemacht haben, ist, dass hier der Betrag immer X-Y
immer positiv ist und wenn man jetzt diese Vorbedingungen hat, kann
man von dieser Vorbedingung direkt auf diese Bedingung schließen.
Das heißt, diese Vorbedingung ist stärker und ist restriktiver als die
Vorbedingung.
Das gleiche macht man jetzt für den Elszweig.
Wir fordern jetzt auch, machen die Vorbedingung stärker und fordern,
dass X gleich A ist und Y gleich B.
Jetzt ist wieder der Fall, wir müssen dafür sorgen, dass Y-X größer
gleich 0 ist.
Wie man das machen kann, man könnte zum Beispiel schreiben, Y ist
größer als X.
Da wir jetzt aber schon wissen, dass wir ein If-Elszweig haben und
nachher dann die If-Els-Regel anwenden wollen, können wir einfach
diese Vorbedingung, die wir im If-Zweig haben, negieren.
Wenn man diese Vorbedingung negiert, kommt praktisch raus, Y ist
größer gleich X.
Aber wir schreiben es, um es einfacher zu machen, es soll noch gelten,
dass X nicht größer als Y ist.
Und wie gesagt, das ist jetzt wieder eine stärkere und restriktivere
Vorbedingung als diese Vorbedingung, die wir am Anfang hatten.
Was wir jetzt machen können, wir haben die Regel für If kennengelernt.
Da das jetzt die komplizierteste Regel ist, die wurde im Skript HTI
genannt, schreibe ich die jetzt nochmal kurz hin.
Wenn man eine Vorbedingung P und B hat, dann ein Statement S1, dann
eine Nachbedingung Q hat und zusätzlich, wenn man die gleiche
Vorbedingung P, dazu aber nicht B hat, dann ein Statement S2.
Und dann Q.
Wenn diese beiden Vorbedingungen gelten und das Programmstück lautet,
If B, then S1.
Das ist jetzt nur die Regel HTI aus dem Skript abgeschrieben.
Wenn man so ein Programm hat, If B, then S1, else S2 und danach Q
gilt, kann man damit auch folgen, dass die Vorbedingung P gelten muss.
Jetzt haben wir in diesem Fall H genau die Situation, unser P ist
hier, hier oben ist auch das P, hier haben wir das B und hier haben
wir glücklicherweise nicht B.
Und unsere Nachbedingung ist hier bei beiden Programmstücken gleich.
Und wenn wir uns nochmal die Aufgabe 6.2 angucken, dann haben wir hier
auch H genau die Situation, die Nachbedingungen und Vorbedingungen
sind richtig und wir haben hier ein If, else, else Zweig in unserem
Programmstück.
Das heißt, was wir jetzt folgen können, ist, dass die Vorbedingung P X
gleich A und Y gleich B ist aus dieser HTI-Regel.
Damit haben wir auch bewiesen, dass das Hoare-Trippel ein gültiges
Trippel ist.
Gibt es zu der Aufgabe noch Fragen?
Ich glaube schon, ich müsste, meiner Meinung nach schon, aber um
sicher zu gehen, müsste ich nochmal nachgucken, aber ich habe nichts
gefunden, was dagegen sprechen würde.
Gibt es sonst noch Fragen zu dieser Aufgabe?
Dann kommen wir zu Graphen.
Es wurde wahrscheinlich schon motiviert, dass Graphen für viele Sachen
verwendet werden können, wie zum Beispiel, das einfachste Beispiel ist
Routenplanung.
Und deswegen ist es auch wichtig, dass man sich mit Graphen recht gut
auskennt.
Man kann es auch noch für Optimierungsprobleme und letztendlich viele
andere Sachen verwenden.
Das wird euch noch häufiger über den Weg laufen.
Hier geht es in der Aufgabe, die war jetzt sehr einfach, da geht es
jetzt mehr oder weniger erstmal darum, die Notationen von Graphen
kennenzulernen.
Was ein Eingangsgrad, was ein Ausgangsgrad ist, wie man einen Pfad
angibt, wie man die Länge eines Pfads berechnet und wie man sowas wie
eine Wegematrix angibt.
Und in Teilaufgabe D werden wir uns dann auch kurz mit Bäumen
beschäftigen.
Wir fangen jetzt mit der Aufgabe 6.3 an.
Wir haben jetzt hier einen Graph gegeben und man soll jetzt
erstmal die Knotenmenge und die Kantenmenge des Graphen angeben.
Die Knotenmenge V für Vertices ist eine Menge bestehend aus Elementen.
Die Elemente in diesem Graph heißen jetzt A, B, C und D.
Deswegen schreiben wir so hin.
Also unsere Knoten sind A, B, C und D.
Und die Kantenmenge geben wir auch an.
Wie gesagt, das ist wieder eine Menge von Kanten.
Was jetzt hier wichtig ist, dass man an diesem Graph sehen kann, es
ist ein gerichteter Graph.
Das heißt, es ist in dem Fall wichtig, dass die Kante von A nach B
geht und sie geht nicht von B nach A.
Deswegen, wenn wir Kanten von einem gerichteten Graphen angeben, dann
verwenden wir Tupeln, weil in Tupeln auch die Reihenfolge wichtig ist.
Wenn wir Kanten von einem ungerichteten Graphen angeben, würden wir
diese zum Beispiel als Mengen angeben.
Also hier geben wir jetzt einfach alle Kanten, die in diesem Graphen
vorkommen, an.
Das ist zum einen die Kante von A nach A, die Kante von A nach B, die
Kante von A nach D und die Kante von B nach C.
Dann bei der Aufgabe B geht es darum, den Eingangsgrad und
Ausgangsgrad des Quotens A zu bestimmen, also dieses Quotens.
Da ist jetzt letztendlich auch die einzige Schwierigkeit, dass man
eine Kante von A nach A drin hat und die letztendlich doppelt
mitzählen muss.
Dann bezeichnet man den Eingangsgrad als D minus D für Degree von A.
Also wie viele eingehende Kanten hat A?
Es gibt nur diese Kante, die eingehend ist, deswegen ist der
Eingangsgrad von A 1.
Der Ausgangsgrad, da kann man wieder die Kanten zählen.
Es gibt eine Kante nach B, eine Kante nach D und wieder diese Kante,
die von A ausgehend wieder zu A geht.
Deswegen ist der Ausgangsgrad, den wir hier mit Plus bezeichnen, 3.
Und wenn man den Grad des Quotens bestimmt, addiert man einfach den
Eingangsgrad und den Ausgangsgrad und kommt auf 4.
Ich habe es anders im Kopf, ich kann nochmal zur Sicherheit
nachgucken.
Also ich kann mich auch erinnern, dass bei ungerichteten Graphen auf
jeden Fall der Doppelt gezählt worden ist, nach der einen Definition
in der Vorlesung.
Ich gucke nochmal nach und wenn es anders ist, würde ich die
Unterlagen aktualisieren, die im ILEA sind.
Letztendlich ist es mehr oder weniger eine Definitionssache, die man
einmal definieren muss und dann muss man darauf achten und es
durchgängig so machen.
Es kann gut sein, dass ich hier einen kleinen Fehler gemacht habe.
Aber wenn es in der Vorlesung so definiert worden ist, sollte man sich
auch daran halten.
Letztendlich, wenn so eine Aufgabe in der Klausur drankommt, sollte
man schon die Definition der Vorlesung nehmen, sonst ist es eine
falsche Antwort.
Wahrscheinlich gibt es dann einen halben Punkt oder ein Abzug.
Das war es zur Aufgabe B.
Bei der Aufgabe C muss man jetzt den minimalen Pfad von den Knoten A
zum Knoten C angeben.
Von Knoten A zum Knoten C gibt es mehrere Pfade.
Es gibt z.B.
den Pfad, da es eine Kante von A nach A gibt, gibt es z.B.
den Pfad A-A, B-C.
Aber der kürzeste Pfad ist natürlich, wie man hier einfach sehen kann,
der Pfad von A nach B nach C.
Also der kürzeste Pfad wäre A-B-C.
Und wenn man die Länge eines Pfades angibt, dann zählt man die Kanten
auf diesem Pfad.
Das sind zwei Kanten hier, also die Länge dieses Pfades ist 2.
Und damit hat man die Aufgabe auch gelöst.
Bei Aufgabe D geht es jetzt darum, dass man einen Teilgrafen von
diesem Grafen G hier oben finden will, der ein Baum ist.
Wir haben jetzt in der Vorlesung die Definition von einem Baum
kennengelernt.
Wir haben gelernt, dass ein Baum immer eine eindeutige Wurzel hat.
Und von der Wurzel existiert zu jedem Knoten genau ein Pfad.
Also ich behaupte jetzt mal, dass es in diesem Fall am besten ist,
wenn man A als Wurzel setzt.
Wenn man jetzt A als Wurzel hat, existiert ein Pfad nach D, ein Pfad
nach B und ein Pfad nach C.
Wenn man sich jetzt diesen Graf anguckt, ist das kein Baum, weil es
diese Kante von A nach A gibt.
Und wenn man die Kante entfernt, dann hat man einen Baum und A ist die
Wurzel.
Das kann man sich jetzt auch nochmal kurz aufzeichnen.
Und dann hat man praktisch diesen Baum.
Man hat A, eine Kante nach D,
eine Kante nach B und dann von B noch eine Kante nach C.
Also erstens, es ist ein Baum, weil wir eine Wurzel haben.
Von der Wurzel existiert ein Pfad zu jedem anderen Knoten.
Ein Pfad kann auch die Länge Null haben, also existiert ein Pfad von A
nach A, ein Pfad von A nach D, nach B, nach C.
Es ist jetzt auch ein Teilgraf von den ursprünglichen Grafen, weil die
Knotenmenge, wie man hier leicht sehen kann, wir haben immer noch A,
B, C, D als Knoten.
Das ist eine Teilmenge, sogar in diesem Fall A genau die gleiche Menge
wie die Knotenmenge in unseren ursprünglichen Grafen.
Und die Kantenmenge ist auch eine Teilmenge, weil hier nur im
ursprünglichen Grafen war diese Kante bei A noch mit drin.
Deswegen ist es ein Teilgraf und es ist ein Baum und wir hatten noch
gefordert, dass die Knotenmenge des Baumes maximal sein soll.
Und das ist sie offensichtlich, weil wir alle Knoten aus den
ursprünglichen Grafen genommen haben.
Bei Aufgabe E war da noch gefragt, dass man E2 angeben soll und man
soll E2 von ursprünglichen Grafen, also diesen Grafen hier oben, mit
der Kante angeben.
Und zudem soll man den Grafen noch zeichnen und der Graf, den wir dann
G2 genannt haben, besteht aus der gleichen Knotenmenge und eben als
Kantenmenge E2.
Was ist jetzt E2?
E2 sind alle Kanten.
Es existiert jeweils eine Kante von den Knoten zu den anderen Knoten,
wenn es einen Weg gibt, der exakt die Länge 2 hat.
Das heißt, von A nach C existiert offensichtlich eine Kante, weil hier
man über B gehen kann und man hat von A nach C den Weg A, B, C.
Man hat aber auch von A nach A einen Weg der Länge 2, weil es auch
einfach den Weg gibt A, A, A und dieser Weg hat die Länge 2.
Das heißt, man kann jetzt sich den Grafen zeichnen.
Man hat jetzt A, von A wird der Weg der Länge 2 zu allen Knoten, zu
sich selber, zu B, C und D.
Ich gucke jetzt mal, dass ich das Format noch einigermaßen sinnvoll
hinbekomme.
Von A gibt es einen Weg der Länge 2 überall hin.
Deswegen hat man das.
Und man kann jetzt hier sehen, dass es keinen anderen Weg der Länge 2
von D, von B oder von C irgendwo anders hin gibt.
Deswegen ist das unser Graf G2.
Man sollte noch die Kantenmenge E2 angeben.
Darauf verzichte ich jetzt mal.
In der Lösung ist es drin, was jetzt hier an E2 und E3 auch noch eine
ganz coole Eigenschaft ist.
Wenn man E2, E3, E4 berechnet hat, hat man die Wege der Länge bei E
der Länge 1, bei E2 der Länge 2, bei E3 der Länge 3.
In einem Grafen, der längste Weg, der keinen Kreis enthält, kann
allerhöchstens die Länge n-1 haben, wobei n die Anzahl der Knoten ist.
Das heißt, wenn man jetzt die Erreichbarkeitsmatrix mit diesen E2, E3
berechnen will, kann man sowas machen wie,
man geht von i gleich 1 bis n-1 und summiert jeweils die e hoch i auf.
Dadurch hat man alle Wege der Länge 1, alle Wege der Länge 2 bis alle
Wege der Länge n hoch 1 und damit hat man die Erreichbarkeitsmatrix.
Das heißt, wenn man diese Matrix kennt, weiß man für jeden Knoten, für
welchen anderen Knoten es Wege gibt.
Gut, das war es jetzt zur Aufgabe 6.3.
Wo?
Oh, stimmt.
Es müsste, guter Einwand, das muss hier sogar e hoch 0 erlauben.
E hoch 0 ist ja die Einheitsmatrix und es gibt jeweils einen Weg von
den Knoten zu sich selber, der Weg hat halt die Länge 0.
Also wie gesagt, beim Grat muss man halt einfach die Definitionen mehr
oder weniger lernen und können und dann halt anwenden.
Wie man diesen Graphen zeichnet, also in diesem Graphen, man berechnet
e hoch 2 und in e hoch 2 sind alle Wege der Länge 2 drin.
Das heißt, man kann sich jetzt jede Kante einzeln angucken.
Also die Kante von A nach A ist drin, weil es den Weg der Länge 2 im
ursprünglichen Graphen, das ist der ursprüngliche Graph, der Weg der
Länge 2.
Ein Weg der Länge 2 von A nach A wäre A, A, A.
Das heißt, man nimmt hier zweimal diese Kante und bleibt dann bei A.
Und für alle weiteren Kanten kann man sich auch Wege der Länge
schauen, ob es Wege der Länge 2 gibt.
Da lernt man dann in Algorithmen auch noch Algorithmen dafür kennen,
wie das geht.
Aber hier hat man halt Weg der Länge 2 von A nach C über A, B, C.
Weg der Länge 2 von A nach B über A, diese Kante von A nach A und dann
nach B und so weiter.
Das kann man für jede Kante, die man in diesem Graph hat, so
argumentieren.
War das verständlich?
Wie man das was kann?
Wir suchen ja jetzt die Wege der Länge 2.
In E hoch 2 sind alle Pfade drin, die die Länge 2 haben.
Und es gibt eben eine Pfade Länge 2 von A über B nach C.
Das war die einfache Aufgabe zu den Graphen.
Es gab noch eine, zumindest ein bisschen anspruchsvollere, das war die
Aufgabe 6.4.
Die muss ich jetzt nur noch finden.
Ja, genau.
Die Aufgabe ist hier.
Also hier geht es jetzt um Bäume.
Bei Bäumen ist es nochmal wichtig, sich wirklich die Definitionen, die
wir von Bäumen gelernt haben, klar zu machen.
Wir reden jetzt hier nicht über Binärbäume, sondern über alle
möglichen Bäume.
Und ein Baum hat laut Vorlesung immer eine Wurzel, die nennen wir im
folgenden R.
Und von dieser Wurzel ist jeder andere Knoten erreichbar.
Und es gibt immer nur von der Wurzel zu jedem anderen Knoten genau
einen eindeutigen Pfad, genau einen Pfad.
Auf diese Definition bauen wir jetzt auf.
Und wir halten jetzt für diese Aufgabe im Hinterkopf.
Und was jetzt die Aufgabe 6.4a ist, man soll einen gerichteten Graphen
G angeben, der ein Baum ist und aus K-Knoten besteht.
Wir können uns jetzt mal überlegen, was ist der kleinste Baum, den es
gibt.
Ein Graph besteht immer aus mindestens einem Knoten.
Das wäre der kleinste Baum, den es gibt.
Wenn wir es uns jetzt einfach machen, sagen wir einfach jetzt 0,
bleibt im folgenden unsere Wurzel.
Wir machen einen größeren Baum, fügen einen Knoten hinzu.
Der Knoten heißt hier, der nächste Knoten, den nennen wir 1.
Das ist immer noch ein Baum, weil wir eine Wurzel haben und von der
Wurzel gibt es einen Pfad zu jedem anderen Knoten.
Und wir können jetzt einfach praktisch so eine Linie machen und immer
mehr Knoten und jeweils eine Kante hinzufügen.
Und was wir dann haben, ist ein Graph, der aus K-Knoten besteht und
ein Baum ist.
Das ist jetzt kein Binärbaum, aber es ist laut Definition ein Baum,
weil es eine Wurzel gibt und einen Pfad von der Wurzel zu jedem
anderen Knoten.
Man kann es sich bei der Aufgabe auch deutlich schwieriger machen und
einen Binärbaum aufbauen, das wäre dann aber schwieriger formal
aufzuschreiben.
Ja, das stimmt.
Deswegen müsste man hier von 1 anfangen.
Es war in der Aufgabe auch nicht gefordert, einen Graphen zu zeichnen,
sondern soweit ich weiß, geben Sie einen gerichteten Graphen an.
Und hier ist jetzt die Punkt-Punkt-Punkt-Notation und das Grafische
meiner Meinung nach eh nicht das Beste.
Deswegen kann man den Graphen auch noch schön formal angucken und in
der formalen Beschreibung des Graphen hat der Graph dann sogar genau K
-Knoten.
Also wir haben einen Graph bestehend aus einer Knoten- und einer
Kantenmenge.
Die Knotenmenge definieren wir so, dass da alle natürlichen Zahlen mit
0 sind.
Für die gilt, dass sie kleiner als K sind.
Also wie hier praktisch ausgezeigt, wir haben Knoten, die wir von 0
bis K-1 nennen und die Kantenmenge können wir auch noch recht einfach
definieren.
Also wieder, wir sollen einen gerichteten Baum angeben.
Das heißt, wir haben eine Kantenmenge Tupel.
Kanten sind immer Teilmenge des kathesischen Produkts der Knoten.
Und wir wollen jetzt, dass wir immer nur eine Kante von 0 nach 1
haben, von 1 nach 2 haben.
Das heißt, wir fordern noch, dass Y-X gleich 1 sein muss.
Damit haben wir diesen Graph beschrieben, weil hier ist zum Beispiel 1
-0 1 oder 2-1 1.
Und wie gesagt, damit haben wir den Graphen, der hier angegeben ist,
beschrieben.
Gibt es zu der Notation hier noch Fragen?
Gut.
Dann geht es mit der Aufgabe B weiter.
Bei der Aufgabe B soll man beweisen, dass ein gerichteter Baum mit K
-Knoten auch genau K-1 Kanten hat.
Wir haben jetzt hier schon gesehen, dass es für einen Graph mit K
-Knoten immer einen Baum dazu gibt, der genau K-1 Kanten hat, wenn man
sich das hier anguckt.
Und jetzt müssen wir noch beweisen, dass es nicht nur immer einen Baum
gibt, der K-1 Kanten hat, sondern dass, wenn es einen Baum mit K
-Knoten gibt, der auch immer genau K-1 Kanten hat.
Das werden wir im Folgenden wieder über einen induktiven Beweis
machen.
Da kommen wir dann endlich mal wieder zu einem induktiven Beweis
zurück, was auch ganz spaßig ist.
Was wir in dem Beweis jetzt aber verwenden, was ich in meinem Beweis
verwenden will, ist, dass ein Baum auch immer mindestens ein Blatt
hat.
Meines Wissens kam die Aussage nicht in der Vorlesung vor, deswegen
behaupten wir jetzt mal, dass in jedem gerichteten Baum mindestens ein
Blatt existiert.
Also jeder gerichtete Baum, den nennen wir jetzt im Folgenden,
GVE, hat mindestens ein Blatt.
Hier muss man sich jetzt erstmal die Definition von einem Blatt
angucken.
Ein Blatt ist ein Knoten, der keine ausgehenden Kanten hat.
Man kann das jetzt ganz elegant mit einem Widerspruchsbeweis beweisen.
Das heißt, wir behaupten, es gibt einen gerichteten Baum, der keinen
Blatt hat.
Also wir machen einen Widerspruchsbeweis, unsere Behauptung im
Folgenden, es existiert ein
Baum.
Ich schmier das jetzt ein bisschen hin, es ist noch recht ausführlich
erklärt in der Musterlösung.
Wenn ihr irgendwo Fragen habt, sagt Bescheid.
Es gibt, also existiert ein Baum, den wir wieder G mit VE nennen, ohne
Blatt.
Das heißt, im Umkehrschluss heißt das, wenn wir kein Blatt haben, hat
jeder Knoten des Baumes immer ausgehende Kanten.
Wir nennen jetzt im Folgenden die Wurzel unseres Baumes wieder R.
Und wenn jeder Knoten ausgehende Kanten hat, kann man, also auch die
Wurzel hat ausgehende Kanten, kann man folgenden Pfad konstruieren.
Wir haben einen Pfad von der Wurzel, den wir R nennen,
über einen beliebigen Knoten V0.
In der Behauptung habe ich einen kleinen Teil vergessen.
Wir sagen noch, dass unser Baum beliebig viele, aber eine feste Anzahl
an Knoten hat.
Das heißt, unsere Knotenanzahl im Baum, über den wir gerade reden, ist
N.
Grafen können auch nicht eine unendliche Anzahl an Knoten haben.
Deswegen können wir das hier einfach machen.
Dann konstruieren wir unseren Pfad und nennen die Knoten dem Pfad R,
V0, V1 bis VN.
Diesen Pfad muss es geben, weil wir haben behauptet, dass es kein
Blatt in unseren Grafen gibt.
Das heißt, jeder Knoten hat ausgehende Kanten.
Das heißt, die Wurzel hat eine ausgehende Kante, der Knoten V0 hat
eine ausgehende Kante, der Knoten V1 hat eine ausgehende Kante.
Was man jetzt, wenn man schon einen Pfad hat, folgen kann.
Der Pfad hat, ist blöderweise, auf dem Weg in diesem Pfad liegen mehr
Knoten, als wir in unserer Knotenmenge bei den Grafen haben.
Das heißt, wir können recht leicht folgen, dass mindestens für ein
paar dieser Knoten, die auf diesem Pfad liegen, existiert mindestens
ein Vi gleich Vj.
Wobei Vi bei der Index hier nicht dasselbe ist.
Das heißt, es muss mindestens ein paar geben, wo der Knoten hier der
gleiche ist.
Was passiert, wir nehmen jetzt mal, wir nennen diesen Knoten, der der
gleiche ist, hier oben mal X.
Wir haben hier unseren Pfad, irgendwann kommt ein X, dann kommen
weitere Knoten, irgendwann kommt noch ein X und dann kommt unser Ende
des Pfades.
Wir haben jetzt aber in der Behauptung gesagt, dass wir über einen
Baum reden.
Wenn wir über einen Baum reden, kann es keinen Kreis in unserem Baum
geben.
Und was man hier sehen kann, es gibt, wir haben einen Pfad gefunden,
in dem ein Kreis existiert.
Nämlich der Kreis von X über die Knoten Vi bis V, V was auch immer,
der wieder nach X zurückläuft und das ist ein Kreis.
Das heißt, wir haben einen Widerspruch zu unserer Behauptung hier oben
gefunden.
Und wir haben nur behauptet, über den Baum nur behauptet, dass er N
Knoten haben kann, wobei N beliebig ist.
Das heißt, mit diesem Widerspruchsbeweis haben wir bewiesen, dass es
kein Baum ohne Platt geben kann.
Habt ihr zu diesem Teil noch Fragen?
Und diese Behauptung werden wir dann in dem Beweis für Aufgabe B, dass
ein gerichteter Baum mit K Knoten genau K-1 Kanten hat.
Diese Aussage werden wir dann gleich verwenden.
Wir führen jetzt einen induktiven Beweis und gehen dabei über die
Anzahl der Knoten.
Im Folgenden wird unser Graph immer V E heißen und die Anzahl der
Kanten nennen wir N.
Und unser Induktionsanfang ist für einen Graph mit N gleich 1.
Ich schreibe es jetzt hier formal, vielleicht manchmal ein bisschen
schlamperchen.
Wie gesagt, wir merken uns, dass jeder Baum mindestens ein Platt hat
und nennen auch im Folgenden immer die Wurzel.
Die Wurzel heißt jetzt bei uns R.
Das heißt, bei einem Baum mit einem Knoten gibt es natürlich nur einen
Knoten und das muss die Wurzel sein.
Also haben wir als Knotenmenge R.
Die einzige Kante, die überhaupt möglich ist, ist eine Kante von R.
Also die beiden Möglichkeiten, die wir haben, ist, dass die
Kantenmenge leer ist oder dass die Kantenmenge besteht aus der Kante
von R nach R.
Und da es keine Kreise in einem Baum geben kann und da es immer nur
ein Pfad von der Wurzel zu allen anderen Knoten geben kann, kann es
diese Kante nicht geben.
Sonst gäbe es den Pfad der Länge 0 nach R, den Pfad der Länge 1 nach R
und so weiter.
Deswegen können wir diesen Fall ausschließen.
Das heißt, unsere Kantenmenge ist 0, ist die leere Menge.
Das heißt, wir haben für den Fall, dass wir eine Kante haben, äh einen
Knoten haben, natürlich hier für die Kardinalität der Menge der Knoten
1 und für die Kardinalität der Menge der Kanten 0 und wir haben den
Induktionsanfang.
Dann, das kann man noch ein bisschen ausformulieren, ist in der
Musterlösung auch ausformuliert, die Induktionsvoraussetzung mit IV
abgekürzt.
Das schreibe ich jetzt nochmal sauber hin.
Also in der Induktionsvoraussetzung haben wir für ein beliebiges, aber
festes n Element der natürlichen Zahlen gelte die Aussage und die
Aussage ist, dass ein gerichteter Baum mit n Knoten genau n-1 Kanten
hat.
Also für n Element n+, beliebig, aber fest.
Also es ist hier nochmal wichtig, ist auch in der Klausur wichtig, in
der Induktionsvoraussetzung nicht zu schreiben, es gilt für alle n.
Es gilt für ein beliebig, aber festes n.
Das ist unsere Induktionsvoraussetzung.
Wenn es für alle n gelten würde, bräuchten wir den Beweis gar nicht
mehr.
gilt Baum mit n Knoten hat n-1 Kanten.
Gut, jetzt kommt der schwierige Teil, der Induktionsschritt.
Beim Induktionsschritt haben wir vorhin schon bewiesen, dass jeder
Baum ein Blatt hat.
Das heißt, wir stellen uns jetzt mal einen beliebig großen Baum vor,
man hat hier einen Wurzelknoten, dann hat man hier weitere Knoten, die
in dem Baum sind und am Ende hat man ein Blatt.
Wir wissen, dass es dieses Blatt gibt, weil wir es vorhin bewiesen
haben und es muss auch ein Pfad von R zu dem Blatt geben.
Aus diesem Pfad kommen weitere Knoten.
Die weiteren Knoten nennen wir jetzt mal V.
Und von diesem Knoten V gibt es eine Kante nach B.
Also es gibt ein Pfad von R über V nach B.
Letztendlich kann dieser Knoten V, in der Zeichnung sieht man es jetzt
nicht, aber dieser Knoten V könnte auch der Knoten R sein, dann würde
es eine Kante geben, die direkt von R nach B gibt.
Das wäre in Kleingrafen auch möglich.
Gut, wenn man das jetzt hat, die Kante werden wir später benutzen.
Wir überlegen uns jetzt noch, ob es nur eine Kante von V zum Blatt
gibt.
Nochmal, ein Blatt hat keine ausgehenden Kanten.
Jetzt gehen wir mal davon aus, es gibt eine andere Kante von V' und
der Knoten V und V' sind verschiedene Knoten.
Wenn es den Knoten gibt und eine Kante von V' nach B gäbe, dann würde
es einen Pfad geben, der auch über V' geht.
Diesen Pfad, den ich jetzt gerade zeige, den gibt es, weil wir gerade
über einen Baum reden.
Und in einem Baum gibt es immer einen Pfad von der Wurzel, und zwar
genau einen Pfad von der Wurzel zu jeden anderen Knoten.
Also es muss einen Pfad von der Wurzel nach V geben, es muss einen
Pfad von der Wurzel nach V' geben.
Und wenn man diese beiden Kanten eingezeichnet hat, hat man einen
Widerspruch dazu, dass wir über einen Baum reden.
Weil wenn es diese beiden Kanten gäbe, dann hat man von R nach B
mindestens zwei Pfade, nämlich diesen Pfad über V und den Pfad über
V'.
Das heißt, wir wissen,
das schreibt man dann in der Lösung, die Begründung, die ich jetzt
mündlich gesagt habe, schreibt man in der Lösung auch hin.
Aber wir haben jetzt herausgefunden, es gibt die Kante von V nach B,
wobei B ein Pfad ist.
Ich gucke jetzt nochmal kurz die Lösung an, damit ich nachher nicht
mehr durcheinander komme.
Also wir wählen ein Pfad B, B Element V und eine Kante von den Knoten
V nach B.
Oder man kann hier gleich schreiben Element E und davon gibt es nur
eine Kante.
Das haben wir gerade hier mündlich begründet.
Ist es soweit klar, dass wir jetzt die Situation haben, dass wir eine
Wurzel haben, wir haben hier einen Pfad von der Wurzel zu den Knoten
V.
V kann hier auch gleich R sein.
Und danach haben wir noch eine Kante zu B.
Und diese Kante, es gibt auch nur eine Kante von der eingehenden Kante
zu B.
Ist es soweit für jeden verständlich?
Und was wir jetzt machen wollen, wir entfernen diese Kante B.
Wenn wir die Kante B entfernen, dann zerfällt unser Graph in zwei
nicht zusammenhängende Teilgraphen.
Nämlich den Graphen, der nur aus den Knoten B besteht und den
ursprünglichen Graphen ohne den Knoten B.
Der ursprüngliche Graph, der jetzt hier eingekreist ist, der hat jetzt
nicht die Eigenschaft verloren, dass er ein Baum ist.
Wir haben jetzt nur eine Kante entfernt, das war eine Kante zu einem
Pfad, also gibt es keinen Pfad mehr von R nach B.
B hat keine ausgehenden Knoten, deswegen zerstört das nicht die
Baumeigenschaft von ursprünglichen Graphen ohne den Knoten B.
Weil kein Weg von der Wurzel zu einem anderen Knoten über B führt.
Das kann nicht gehen, weil B keine ausgehenden Knoten hat.
Ist dieser Gedankenschritt soweit klar?
Gut, wenn man das hat,
wir entfernen die Kante VB und dann erhalten wir die zwei Teilgraphen.
Das wäre zum einen der Baum V1 E1,
wobei V1 gleich unser Platz ist und E1 die leere Menge ist.
Wir haben vorhin gesehen, dass das trotzdem ein Baum ist, weil ein
Graph bestehend aus einem Knoten ohne Kanten ein Baum ist.
Und wir haben noch den Baum V2 E2 mit V2 ist die Menge aller Knoten
ohne das B und E2 ist die Menge der Kanten ohne die Kante, die wir
gerade entfernt haben.
Und die Kante, die wir gerade entfernt haben, heißt VB.
Jetzt können wir ausrechnen, wie viele Kanten wir noch in den beiden
Teilgraphen haben.
Wir gehen jetzt in den Induktionsschritt davon aus, dass die Aussage
für alle Kanten mit Endknoten gilt.
Und wir betrachten jetzt einen Baum.
Hier oben muss man das noch erwähnen.
Wir betrachten jetzt einen Baum G V E mit V gleich N plus 1 Knoten.
Wir haben jetzt diesen Baum in zwei Teilgraphen zerlegt, wobei beide
Teilgraphen echt kleiner sind als der Baum mit N plus 1 Knoten.
Deswegen kann man jetzt schön unsere Induktionsvoraussetzungen
einsetzen.
Und wir rechnen jetzt die Kantenanzahl unseres Baumes mit.
Also erstmal, wir haben die Kante V von V zu unserem ausgewählten
Platt entfernt.
Das heißt, die war aber im ursprünglichen Baum drin.
Das heißt, wir haben erstmal eine Kante plus die Anzahl der Kanten vom
ersten Teilgraf plus die Anzahl der Kanten vom zweiten Teilgraf.
Was man jetzt hier hat, die Anzahl der Kanten vom ersten Teilgraf ist
recht einfach, denn keine, also null.
Und die Anzahl der Kanten vom zweiten Teilgraf, da kann man jetzt die
Induktionsvoraussetzung einsetzen.
Wir haben in der Induktionsvoraussetzung gesagt, für ein beliebiges
aber festes N gilt ein Baum mit N Knoten hat N minus 1 Kanten.
Das heißt, wir wissen jetzt, dass unser Baum ursprünglich N plus 1
Kanten hat.
Das haben wir hier gesagt.
Und jetzt ziehen wir da, N plus 1 Knoten hat, und jetzt ziehen wir da
von 1 ab, dann kommt man auf die Kantenanzahl.
Und da habe ich mich gerade verschrieben.
Also, das ist null.
Schreiben wir es nochmal langsam auf.
Bei E2, es ist ein Teilgraf mit N Knoten, das heißt, wir dürfen die
Induktionsvoraussetzung einsetzen.
Die Induktionsvoraussetzung ist V2 minus 1.
Das heißt,
man hat hier 1 plus die Anzahl der Knoten von V2 minus 1 ist gleich
die Anzahl der Knoten von V2.
Und die Anzahl der Knoten von unserem Teilgraf V2 ist genau, die
Anzahl der ursprünglichen Knoten war N plus 1.
Wir haben hier den Knoten B, also unser ausgewähltes Blatt entfernt.
Das heißt, wir haben N plus 1 minus 1, weil wir das Blatt entfernt
haben, Knoten.
Das heißt, hier kommt genau N raus.
Das heißt, wir haben bewiesen, wir haben einen Induktionsschritt
gezeigt, dass ein Baum mit N plus 1 Knoten genau N Kanten hat.
Und damit sind wir mit dem induktiven Beweis fertig.
Hat dazu noch jemand Fragen?
Man kann in diesem Fall auf alle kleineren Bäume das anwenden.
Ich habe jetzt in der Induktionsvoraussetzung, kann man auch fordern,
dass es für ein beliebig festes N gilt und alle kleineren Ns.
Und man muss halt für N plus 1 das dann zeigen.
Also für ein um eins größeres N.
Noch Fragen zu der Aufgabe?
Dann die einzige Aufgabe, die noch fehlt, ist die Aufgabe, die gerade
verschwunden ist.
Ich kann es nochmal kurz mündlich.
Ich glaube, es ging um die Aufgabe 6 von 5.
Da war die Frage, listen Sie die verschiedenen Möglichkeiten für
Repräsentation von binären Relationen auf, die Sie in der Vorlesung
kennengelernt haben.
Binäre Relationen kann man zum Beispiel repräsentieren in Form von
einer zweidimensionalen Matrix, in Form von einer Menge von Tupeln und
in Form von einem Graphen.
Und vielleicht auch noch mit anderen Möglichkeiten.
Auf die Aufgabe gab es drei Punkte.
Und da reicht auch für die Aufgabe jetzt drei Lösungen zu sagen.
Also eine Lösung ist, man kann eine binäre Relation als Graph
repräsentieren, eine als zweidimensionale Matrix und eine als Menge
von Tupeln.
Das war es soweit zur sechsten Übung.
Zum Bonusblatt gibt es keine Übung und ich lade nur die Musterlösung
hoch.
Und dann bedanke ich mich bei euch und wünsche euch allen viel Erfolg
für die Klausur und steckt auch ein bisschen Zeit ins Lernen.