Ich las das Buch Algorithmus Design, Kapitel 1, es gab eine sehr kurze Beschreibung, wie Bipartite Matching zu Independent Set Problem konvertieren und ich verstehe es nicht.Wie konvertiert man Bipartite Matching zu Independent Set
Weiß jemand, dass detaillierte Matriel diesen Prozess beschreiben? Vielen Dank!
Ein maximaler bipartiter Matching ist eine Menge von Kanten in einem zweiteiligen Graphen, wobei keine zwei Kanten benachbart sind. Eine maximale unabhängige Menge ist eine Menge von Knoten (Vertices) in einem Graphen, wobei keine zwei Vertices benachbart sind.
So können Sie ein bipartites Übereinstimmungsproblem in unabhängige Mengen konvertieren, indem Sie jede Kante in Ihrem bipartiten Diagramm in einen Knoten konvertieren und dann eine Kante zwischen allen neu erstellten Knoten hinzufügen, die einen gemeinsamen Endpunkt im ursprünglichen Diagramm haben. Dann entspricht eine maximale unabhängige Menge in dem neuen Graphen einer maximalen zweiseitigen Übereinstimmung in dem ursprünglichen Problem.