Ich glaube, ich habe eine bestimmte Situation wie unten beschrieben verstanden, aber mir fehlt das theoretische Wissen, um einen Beweis zu führen, und ich konnte keine Quelle finden, die es erwähnt. Wenn mein Verständnis stimmt, kann ich die Hälfte des Platzes in meiner Adjazenzmatrix einsparen. Wenn nicht, habe ich wahrscheinlich ziemlich komische Käfer. Also würde ich gerne sicher sein, und ich würde es begrüßen, wenn jemand mit einem solideren Hintergrund meine Argumentation überprüfen könnte.
Angenommen, ich repräsentiere ein DAG von n Knoten in einer n * n Adjazenzmatrix, so dass der Eintrag i,j 1 ist, wenn es eine Kante vom Knoten i zum Knoten j , 0 gibt. Da der Graph gerichtet und azyklisch ist, folgt, dass, wenn i,j = 1 , dann j,i = 0 . Wenn ich nun die Knoten in der Matrix so sortiere, dass die topologische Ebene des Knotens bei i n
Vielleicht bin ich genau richtig, aber gibt es eine formelle Möglichkeit, das zu überprüfen?
Sei adj [i] [j] der Adjazenz-Eintrag von Knoten i zu Knoten j und du hast ihn so sortiert, dass für alle Knoten i & lt; j, Knoten I ist höher als der Knoten j in der topologischen Hierarchie.
Nehmen wir einen Moment an, dass Ihre Annahme falsch war: dass wir ein Gegenbeispiel haben, für das adj [i] [j] == 1 für i & gt; j (d. h. eine Eins in der oberen rechten Hälfte Ihrer Matrixdarstellung). Dies impliziert, dass es einen Zyklus geben muss, der i und j enthält, da unsere Sortierung garantiert, dass der Knoten j höher ist als der Knoten i, aber wir adj [i] [j] == 1 implizieren, dass wir die Hierarchie "hinaufklettern" können. Dies ist ein Widerspruch, da wir wissen, dass wir eine DAG haben. Deshalb haben wir bewiesen, dass Ihre Annahme richtig ist.
Dies ist nur korrekt, wenn Ihre Adjazenzmatrix mit den graph Labels in sortierter Reihenfolge erstellt wird. Für ein Gegenbeispiel konstruiere die Adjazenzmatrix für B- & gt; C- & gt; A.
Wenn Sie einen Hash des wahren Knotens zu seiner topologischen Sortierposition behalten und daraus die Adjazenzmatrix konstruieren, könnten Sie Platz auf einer großen Matrix sparen, da Sie den O (n2) -Raum in der Matrix mit einem O speichern (n) Größe Hashtabelle.
Tags und Links graph-theory