Wie finde ich die maximale unabhängige Menge eines gerichteten Graphen?

7

Ich versuche dieses Problem zu lösen .

Problem : Gegebenn Bei positiven ganzen Zahlen müssen Sie eine maximale Anzahl von ganzen Zahlen auswählen, damit keine zwei Zahlen vorhanden sind ein,b in welchem ein ist teilbar durch b.

Ich muss den maximalen unabhängigen Satz und die Größe dieses Satzes finden. Die Größe ergibt sich aus dem Satz von König . Aber wie kann ich die maximale unabhängige Menge finden (dh welche Scheitelpunkte Teil der Menge sind)?

Ich habe auch gesucht und hier etwas gefunden :

If removing a vertex does not change minimum path cover then I can get the desired result without that vertex.

Aber ich verstehe den zugrunde liegenden Satz nicht. Jede Hilfe wird sehr hilfreich sein.

Palatok
quelle
Warum denkst du, dass es ein zweiteiliger Graph ist?
Joe
Dies ist nicht der Fall, aber es ist möglich, eine minimale Pfadabdeckung in einem gerichteten Diagramm anzuwenden.
Palatok
2
Cross-posted unter: stackoverflow.com/questions/15211918/… . Bitte posten Sie nicht mehrere SE-Sites gleichzeitig. Wenn Sie einige Tage lang keine zufriedenstellende Antwort auf den ursprünglichen Beitrag erhalten, können Sie an einer anderen Stelle im Netzwerk posten. Fügen Sie in einem solchen Fall in jedem Ihrer Beiträge einen Link zu dem anderen Beitrag hinzu, damit die Leute wissen, wo Sie stehen, und vermeiden Sie Doppelarbeiten.
Paresh

Antworten:

6

Sie versuchen, die Breite des Posets zu ermitteln, die durch die angegebene Teilmenge von Ganzzahlen und die Teilbarkeitsrelation definiert ist. Die Breite ist die maximale Anzahl von Anti-Ketten, die der maximalen Anzahl von unvergleichlichen Elementen im Poset entspricht.

Dies entspricht genau der maximalen unabhängigen Menge im Vergleichbarkeitsdiagramm , wobei jede Ganzzahl ein Scheitelpunkt ist und es eine Kante von gibtu zu v dann und nur dann, wenn u teilt v.

Das Finden der maximalen unabhängigen Menge im Allgemeinen ist ein schwieriges Problem, aber Vergleichbarkeitsgraphen sind ein Sonderfall, für den effiziente Algorithmen existieren.

Der Satz von Dilworth charakterisiert die Breite eines Posets als Teilung des Posets in Ketten (Pfade von Quelle zu Senke im gerichteten Vergleichbarkeitsgraphen). Der Satz von Dilworth entspricht dem Satz von König über Bipartite Matching , der, wie Sie vorgeschlagen haben, zu einem Algorithmus führt. Der zweigliedrige Graph, den Sie erstellen, um den Satz von Konig zu verwenden und die maximale unabhängige Menge über einen zweigliedrigen Abgleich zu finden, wird einfach im obigen Wikipedia-Link beschrieben. Der Vollständigkeit halber fügen wir es hier ein (in kommentierter Form):

"Definieren Sie einen zweiteiligen Graphen G=(U.,V.,E.) wo U.=V.=S. [die Menge von ganzen Zahlen] und wobei (u, v) eine Kante in ist G wann u<vS. [ganze Zahl u teilt die ganze Zahl v]. Nach dem Satz von König gibt es eine ÜbereinstimmungM. im Gund eine Reihe von Eckpunkten C. im G, so dass jede Kante im Diagramm mindestens einen Scheitelpunkt in enthält C. und so dass M. und C. haben die gleiche Kardinalität m.

"Lassen EIN sei die Menge der Elemente von S, die keinem Scheitelpunkt in entsprechen C.;; dannEIN hat zumindest n- -m Elemente (möglicherweise mehr wenn C.enthält Eckpunkte, die auf beiden Seiten der Bipartition demselben Element entsprechen). LassenP. eine Familie von Ketten sein, die durch Einschließen gebildet werden x und y in der gleichen Kette, wenn es eine Kante gibt (x,y) in M.;;thenP.heinsn - m $ Ketten. Deshalb haben wir eine Antichain und eine Partition in Ketten mit derselben Kardinalität konstruiert. "

Die Menge der unterschiedlichen Scheitelpunktbezeichnungen (Ganzzahlen) in EIN ist die Antwort auf Ihre Frage.

In Abschnitt 3 des Dokuments Online-Algorithmen für die Kettenpartition von Dilworth von Ikiz und Garg werden zwei verschiedene Offline-Algorithmen zur Berechnung der Kettenpartition und damit der von Ihnen gesuchten unabhängigen Menge beschrieben. Einer der Algorithmen basiert auf der Bipartite Matching-Methode.

Joe
quelle
1
In dem speziellen Fall, in dem der Eingabesatz alle Ganzzahlen in einem bestimmten Bereich enthält [1,N.]], können Sie möglicherweise en.wikipedia.org/wiki/Abouabdillah%27s_theorem#Number_theory
Joe