Übungsblatt 7 - Aufgabe4

Hallo zusammen,

unser tutor meinte, wir können hier auch Fragen zum Übungsblatt stellen, die dann (hoffentlich) beantwortert werden. Darum eine Frage zur Aufgabe 4: Kann uns irgendjemand (vielleicht auch ein Tutor oder der Ersteller der Aufgabe!!) erklären, wie man am Besten anfängt, wir sind total planlos!!

Vielen Dank,

Christoph

In Aufgabe 4 soll gezeigt werden, dass die Funktion depth für einen gerichteten azyklischen Graphen immer ein eindeutiges Ergebnis liefert. Dazu zwei Tipps:

1. Welchen Zusammenhang gibt es zwischen der Tiefe eines Graphen (= Länge des längsten vorkommenden Pfades) über der Anzahl an Knoten?

2. Was ist mit der Tiefe der einzelnen Knoten in einem Graphen? Ist die wohldefiniert?


Gruß
Bettina


---------------------------
Wer lesen kann, ist klar im Vorteil.