Transitive Hülle einer Relation |
| 14.04.2010, 15:14 | Hellboy256 | Auf diesen Beitrag antworten » | ||||
| Transitive Hülle einer Relation Sei M := {a,b, c,d} und R := {(a,a), (a, c), (b,b), (b,d), (c,b), (c,d), (d, c)} die Relation Anhand des Algorithmus von Warshall war dann die transitive Hülle zu Berechnen: Warshall-Algo: A[i][j] => Adjazenzmatrix N[i][j]=A[i][j] for (r=0; r<n; r++) for (i=0; i<n; i++) for (j=0; j<n; j++) if (a[i][j]=0 && a[i][r] && a[r][j]) N[i][j]=1; 1111 0111 0111 0111 T={ (a,a),(a,b),(a,c),(a,d),(b,a),(b,b),(b,c),(b,d),(c,a),(c,b),(c,c),(c,d),(d, a),(d,b),(d,c),(d,d)} Nur hab ich jetzt keine Ahnung was bei den letzten beiden Teilaufgaben rauskommt?? Wie kann man die Einträge der in Iteration r berechneten Matrix anschaulich interpretieren? Demonstrieren Sie die allgemeine Interpretation in einem Spezialfall! |
||||||
| 14.04.2010, 22:56 | Mystic | Auf diesen Beitrag antworten » | ||||
Dein Posting wirft für mich eine Menge Fragen auf... 
Zunächst einmal, von wem stammt untenstehende Implementierung des Warshall-Algorithmus? Von dir oder ist sie Teil der Aufgabe? Meiner Meinung nach ist sie nämlich klar falsch, da es 1-Einträge in der Matrix nur dann gibt, wenn sie schon vorher da waren (von der Zuordnung N=A zu Beginn) oder es einen Weg vom Knoten i zum Knoten j über genau einen Zwischenknoten r gibt. Mit anderen Worten, wenn ein Weg von i nach j mehrere Zwischenknoten erfordert, so wird das bei dieser Implementierung nicht berücksichtigt. Zufälligerweise tritt aber in diesem Beispiel dieser Fall gar nicht auf, sodass das Endergebnis mit der 4x4-Matrix dann doch wieder stimmt. Du hast aber seltsamerweise diese Matrix dann auch gar nicht zur Bildung der transitiven Hülle herangezogen, oder soll das am Ende gar T sein??? Wie gesagt, da ist eine ganze Menge unklar... 
Edit: Wenn obige fehlerhafte Implementierung von dir stammt, wie ich mal vermute, dann wäre es sehr hilfreich, wenn du zum Vergleich den Original Warshall-Algorithmus, wie ihr ihn in der Vorlesung gehört habt, hier reinstellst... |
||||||
| 15.04.2010, 12:55 | Hellboy256 | Auf diesen Beitrag antworten » | ||||
Also der exakte Wortlaut des Algorithmus aus dem Skriptum: N = Matrix A= Adjazenzmatrix Für r von 0 bis n-1 wiederhole: Setze N=A Für i von 0 bis n-1 wiederhole: Für j von 0 bis n-1 wiederhole: Falls A(ij)=0 und A(ir)=1 und A(rj)=1, setze N(ij)=1 Setze A=N Die Matrix 1111 0111 0111 0111 wäre meine berechnete N-Matrix und das T T={ (a,a),(a,b),(a,c),(a,d),(b,a),(b,b),(b,c),(b,d),(c,a),(c,b),(c,c),(c,d),(d, a),(d,b),(d,c),(d,d)} wäre meine transitive Hülle |
||||||
| 15.04.2010, 13:22 | Mystic | Auf diesen Beitrag antworten » | ||||
Aha, da haben wir's ja schon, genau wie ich vermutet hatte, hast du einen ganz wesentlichen Teil (nämlich den von mir rot unterlegten) bei deiner im ersten Posting angegebenen Implementierung glatt vergessen, sodass das Ganze dann nicht mehr stimmt... Natürlich muss A immer das aktuelle N sein... Meiner Meinung nach könnte man sogar mit A allein arbeiten, indem man einfach die Einträge von A[i,j] in der Weise aktualisiert, so wie du das jetzt für N[i,j] machst...
Hm, hast du trotz meines Hinweises oben noch immer nicht gesehen, dass dein T falsch ist? Wieso kommen darin die von mir farblich hervorgehobenen Paare vor, obwohl die entsprechenden Einträge in der resultierenden Matrix 0 sind?
|
||||||
| 15.04.2010, 13:34 | Hellboy256 | Auf diesen Beitrag antworten » | ||||
Kann ich als Interpretation folgendes sagen: Dass ich die Erreichbarkeit von zwei Knoten von i nach j prüfen will und r meine Zwischenknoten wären? Der Spezialfall könnte dann sein das der Graph azyklisch ist oder? |
||||||
| 15.04.2010, 13:55 | Mystic | Auf diesen Beitrag antworten » | ||||
In jedem Durchgang der äußersten Schleife, wo also r die Werte von 1 bis n durchläuft, wird auf potenziellen Wegen von Knoten i nach Knoten j ein Zwischenknoten mehr zugelassen, also im ersten Durchgang nur der Zwischnenknoten 1, im 2.Durchgang zusätzlich der Zwischenknoten 2 usw., bis dann am Ende alle Zwischenknoten auf einem Weg von i nach j zugelassen sind...Ist dann der Eintrag A[i,j] immer noch 0, so gibt es überhaupt keinen Weg von i nach j... Was denn Spezialfall betrifft solltest du meiner Meinung nach einfach für die gegebene Aufgabe an einem konkreten Beispiel aufzeigen wie der Wert von A[i,j] bei einem Duchgang der r-Schleife für einen speziellen Wert von r von 0 auf 1 springt... Z.B. könntest da i=1, j=4, r=3 dafür wählen... |
||||||
| Anzeige | ||||||
|
|
||||||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
