Hausübung

[Shoggo]

Servus!

Was darf ich denn unter "keine unleserlichen, handschriftlichen Lösungen" verstehen?
Heisst das handschrfitlich ja, aber leserlich?
Oder generell nicht handschriftlich?

[SebFreutel]

Im Allgemeinen soll es nicht handschriftlich sein sondern gedruckt, die erste Hausübung darf aber handschriftlich sein, weil das Graphen-Zeichnen sonst so umständlich sei, wurde heute gesagt

[kechler]

Hallo zusammen,

ich habe auch eine Frage zur aktuellen Hausübung, Aufgabe 1.3 - Reflexive Transitive Closure:
Im Tutorial auf der Homepage werden beim Warshall-Algorithmus keine Wege der Länge 0 berücksichtigt. Diesbezüglich habe ich mal in den GDI2-Folien vom SS07 nachgeschaut, und dort wird folgendes gesagt:

Transitive Hülle
• Zu einem Graphen G definiere analog zur Erreichbarkeitsmatrix die Matrix A* wie folgt:
– A* i,j = 1 falls i=j oder zwischen vi und vj existiert ein Weg in G
– A* i,j = 0 sonst
• A* ist die reflexive, transitive Hülle von A.
• A* ist im wesentlichen die Erreichbarkeitsmatrix von G, wobei auch Wege der Länge 0 berücksichtigt werden.
• Aus A* kann man den Graphen G* bilden. Wir nennen G* die reflexive, transitive Hülle (kurz: transitive Hülle, oder Hülle) von G.

Kann mir jemand sagen, ob wir nun Wege der Länge 0, also Schlingen an jedem Knoten bzw. 1er auf der Diagonalen, mit berechnen sollen oder nicht?
Vielen Dank im voraus!

[kahler]

Soweit ich das in der letzten Veranstaltung verstanden habe:

Schlingen und Wege der Länge 0 sollen betrachtet werden, sofern sie im Graph auch vorhanden sind.
Man kann jedoch nicht davon ausgehen, dass jeder Knoten automatisch auch mit sich selbst verbunden ist (Schlinge) und diese Verbindung die Länge 0 hat.

[Christoph B]

wie kommst du denn darauf das diese wege nicht berücksichtig werden?
1. hab ich dazu nichs im tutorial gesehn (würde mich auch wundern)
2. Spielen doch gerade beim warshall algo die länge / gewichte der kanten keine rolle, sondern NUR das sie existieren (1 = weg existiert, 0 = weg existiert nicht)

[Red*Star]

Wie auch immer wir das in dieser Übung machen sollen, das online gestellte Beispiel ist in jedem Fall inkonsistent:
Eine "reflexive transitive Hülle", die nicht reflexiv ist, macht keinen Sinn (siehe S. 9 in den Informationen zum Floyd-Warshall-Algorithm auf der NCS-Homepage: Hier gehört eigentlich noch (3, 3) mit zur Hülle dazu, ist aber ausgelassen. Anders gesagt: Es ist tatsächlich die Erreichbarkeitsmatrix angegeben, nicht die rtH. Man müsste den Warshall-Algo eigentlich mit zusätzlichen Einsen auf der Hauptdiagonale der Adjazenzmatrix starten, um zur rtH zu kommen).

[Christoph B]

hmm, weiso? stimmt doch?
es gibt keinen weg von 3 nach 3, weil 3 keine ausgehenden Kanten hat
alle andren "schleifen" der ref.trasn. Hülle sin angegeben.

Oder meinst du nich das Beispiel auf Seite 9 des "Graphen Tutorials" ?

[js]

Hallo!

Ich hatte genau diese Problematik in der letzten Übung angesprochen und erklärt. Eine 1 existiert in der Matrix, wenn die jeweiligen Knoten mit Kanten, bzw. Schleifen verbunden sind. Falls eine Schleife an dem Knoten existiert, dann wird dieses durch eine 1 in der Matrix dargestellt. Falls auf der Diagonale eine 0 steht, so ist ein Knoten nicht wieder erreichbar, wenn man den selben Knoten als Startknoten gewählt hat.

Joachim

[baerchen]

die reflexive und transitive hülle würde aber schon per definition eine kante zum jeweiligen knoten selbst enthalten. in der aufgabenformulierung ist also vielleicht einfach ein unglücklicher begriff gewählt worden ...

[Tapion]

Im Kontext der Netzwerke kann man sich durchaus auch selber überlegen, dass es sinnvoll ist, keine Schlaufen mit der Länge 0 anzunehmen.

Eine solche (reflexive) transitive Hülle gibt sonst nämlich keine Antwort mehr darauf, wie lange es mindestens dauert, bis auf eine Anfrage an ein Netz eine Antwort kommt.

[Red*Star]

Oder meinst du nich das Beispiel auf Seite 9 des "Graphen Tutorials" ?

Doch meine ich.

Hallo!

Ich hatte genau diese Problematik in der letzten Übung angesprochen und erklärt. Eine 1 existiert in der Matrix, wenn die jeweiligen Knoten mit Kanten, bzw. Schleifen verbunden sind. Falls eine Schleife an dem Knoten existiert, dann wird dieses durch eine 1 in der Matrix dargestellt. Falls auf der Diagonale eine 0 steht, so ist ein Knoten nicht wieder erreichbar, wenn man den selben Knoten als Startknoten gewählt hat.

Joachim

Ihr könnt für den Algorithmus ja von mir aus definieren, was ihr wollt, aber dann nennt es bitte nicht "reflexive" transitive Hülle. Eine reflexive Relation ist nach wie vor eine, in der für alle a aus der Trägermenge immer (a, a) Element der Relation ist.
Insofern ist die in der Grafik auf S. 9 [Website-Beispiel] dargestellte Hülle nicht reflexiv, ganz unabhängig davon ob genau dies oder ob das Gegenteil nun in in der Praxis Sinn macht oder nicht.

[Edoat]

Ihr könnt für den Algorithmus ja von mir aus definieren, was ihr wollt, aber dann nennt es bitte nicht "reflexive" transitive Hülle. [...]
Insofern ist die in der Grafik auf S. 9 [Website-Beispiel] dargestellte Hülle nicht reflexiv, ganz unabhängig davon ob genau dies oder ob das Gegenteil nun in in der Praxis Sinn macht oder nicht.

die reflexive und transitive hülle würde aber schon per definition eine kante zum jeweiligen knoten selbst enthalten. in der aufgabenformulierung ist also vielleicht einfach ein unglücklicher begriff gewählt worden ...

Ich sehe das genau so, man sollte einfach transitive Hülle schreiben.

[Christoph B]

ah stimmt, sry leute, hatte wohl die genaue Definition aus GDI2 verdrängt.
nach bisserl reinlesen u.a. in die alten GDI2 folien stimm ich aba nu zu: falsche bezeichnung