Etikettengruppen von Scheitelpunkten in einem Diagramm auf effiziente Weise ohne BFS / DFS

Question

Ich habe ein Diagramm mit einem Satz von Scheitelpunkten $ \ Mathcal {v} $ und ein Satz von Kanten $ \ Mathcal {E} $ . Es gibt einen Pfad zwischen allen 2 Scheitelpunkten in der Grafik. Zu jeder Kante gibt es ein zugehöriges Gewicht $ W (E), E \ in \ Mathcal {E} $ . Ich definiere einen (globalen) Schwellenwert $ t $ so, dass, wenn $ w ((u, v)) Die beiden Scheitelpunkte $ u, v \ in \ mathcal {v} $ sind in derselben Gruppe: $ g \ in \ matcal {v} \ rightarrow \ mathbb {z}, g (v_1)= g (v_2) $ . Dieses Verhalten ist transitiv. Ziel ist es, die verschiedenen Gruppen abzunehmen (die Reihenfolge der Gruppen ist irrelevant). Ich weiß, dass dies trivial mit BFS oder DFS erreicht werden kann, aber ich möchte nicht mit denen vermeiden.

Die Idee, mit der ich kam, ist, über den Ecken zu iterieren, über ihre 1-Ring-Nachbarschaft zu gehen, und erstellen Sie jedes Mal eine neue Gruppe, wenn $ W ((u, v) ) für eine der Kanten und weder $ u $ noch $ v $ wurden einer Gruppe zugewiesen (z. B. $ g (u)= g (v)= -1 $ ). Zusätzlich wird jede Gruppe ein Etikett zugewiesen, das anfänglich dem Index der Gruppe entspricht: $ h: \ mathbb {n} \ Rightarrow \ mathbb {n}, H (G ( u))= g (u) $ . Wenn irgendwann $ W ((x, y)) und $ w ((y, z)) , aber $ g (x) \ ne g (z) $ dann $ h ( g (x)) \ lindearrow \ min (h (g (x)), h (g (z)) $ und $ h (g (z)) \ lindearrow h (g (x)) $ . Nach diesem Verfahren sollte es sich halten: $ h (g (u))= h (g (v)), u, v \ in \ matcal {v} $ Wenn es einen Pfad von $ U $ auf $ V $ gibt : $ \ pi= E_1, ..., e_n $ so, dass $ w (e_i) . Ist der Algorithmus, den ich richtig gemacht habe oder habe ich etwas vermissen? Wie es ist derzeit erforderlich, ist es $ | \ Mathcal {v} | $ Speicher Für jedes Array $ g, H $ . Gibt es eine Möglichkeit, dies weiter zu optimieren?

Answer 1

Wie Sie in

Answer 2

Ich glaube, mein Algorithmus ist richtig. Eine Skizze des Beweises wird unten dargestellt:

Es gibt 2 Fälle: entweder $ u \ ne v \ in \ matcal {v} $ müssen von derselben Gruppe sein oder sie müssen von sein Unterschiedliche Gruppen (je nachdem, ob ein Pfad zwischen ihnen vorhanden ist, so dass $ w (e) ). Es muss gezeigt werden, dass der Algorithmus die resultierenden Gruppen erzeugt (der Beweis für jeden Fall wird durch Widerspruch erfolgen).

.

1. Fall 1: Let $ u, v \ in \ mathcal {v} $ und es gibt einen Pfad von $ u $ an $ V $ : $ \ pi= E_1, ..., E_N $ so, dass $ w (e_i) . Dann $ h (g (u)) $ sollte gleiche $ h (g (v)) $ für der Algorithmus ist richtig.

2. Annahme von Algorithmus Unrichtig: Angenommen, dies ist nicht der Fall, und dieser $ u $ , $ V $ gehören zu verschiedenen Gruppen, die auf dem Ergebnis des Algorithmus basieren. Für Einfachheit halber geht es an, dass $ \ pi=pi_1, x, y, z, \ pi_2; \, x, y, z \ in \ matcal {v} $ solcher dass alle Scheitelpunkte von $ \ pi_1, x $ gehören zu $ h (g (u)) $ und Alle Scheitelpunkte auf $ y, z, \ pi_2 $ gehören zu $ h (g (v)) $ basierend auf dem Algorithmus. Der Fall nach der obigen Annahme wird nachgewiesen, aber es sollte klar sein, dass das gleiche durch Induktion hält, auch wenn $ \ pi $ in mehr Gruppen aufgeteilt wird, basierend auf der Algorithmus.

Beweis durch Widerspruch: von (1) folgt er $ w (x, y) und von (2) Es folgt: $ h (g (x)) \ ne h (g (z)) $ . Aus der Definition des Algorithmus folgt, dass er niemals Gruppen aufteilt, und es geht zwei Gruppen, wenn $ w (x, y) aber $ h (g (x)) \ ne h (g (z)) $ . Da der Algorithmus über alle Kanten übergeht, sollte es $ H (g (x)) $ und $ H (G (g ( z)) $ .

3. Fall 2: $ u, v \ in \ matcal {v} $ und es gibt keinen Pfad $ \ pi $ von $ u $ bis $ v $ so, dass $ w (e) , dann $ h (g (u))= h (g (v)) $ .

4. Annahme von Algorithmus Unrichtig: Angenommene $ h (g (u))= h (g (v)) $ .

Nachweis des Widerspruchs: Sowohl bei der Gruppenerstellung als auch bei der Gruppenfindung (die einzigen zwei Möglichkeiten für die Ecke, um in derselben Gruppe zu enden), muss ein Pfad zwischen $ u $ vorhanden sein und $ V $ so, dass $ w (e) . (3) gibt an, dass kein solcher Pfad vorhanden ist, dann $ h (g (u)) \ ne h (g (v)) $ .

Natürlich ist der Beweis ziemlich informell, daher habe ich vielleicht etwas verpasst. Ich werde die Frage für eine Weile auflassen, denn 1) Jemand kann mit einem besseren und mehr optimierten Algorit kommen, und 2) Ich habe möglicherweise einen Fehler in meinem Beweis.