Maximal eins zu vieler Übereinstimmung

Question

lass $ g= (x + y, e) $ Seien Sie ein zweifacher Diagramm und $ k \ geq 1 $ eine ganze Zahl. Ein Maximum $ K $ -matching ist eine Teilmenge von $ E $ in welche jeder Scheitelpunkt von $ x $ angrenzt, um höchstens $ K $ Kanten und jedem Scheitelpunkt von $ y $ ist angrenzend an höchstens $ 1 $ Rand.

Eine Maximalkardinalität $ K $ -matching kann vom folgenden Algorithmus gefunden werden:

.
• erstellen $ K $ Kopien jedes Scheitelpunkts $ x \ in x $ , so dass jede Kopie ist neben allen Nachbarn von $ x $ in $ y $ .
• Finden Sie in der resultierenden Grafik ein maximales Anpassen.

seine Laufzeitkomplexität für ein Diagramm mit $ N $ Ecken und $ M $ Kanten, Verwenden des Hopcroft-Karp-Algorithmus, ist $ O (KM \ SQRT {KN})= o (k ^ {3/2} \ cdot m \ sqrt {n}) $ .

Ich interessiere mich für den folgenden alternativen Algorithmus:

.

• wiederholen $ k $ mal:

  .
  • Finden Sie eine maximale Übereinstimmung in $ g $ .
  • Entfernen Sie die übereinstimmenden Scheitelpunkte von $ y $ aus der Grafik.

seine Laufzeitkomplexität ist $ o (k \ cdot m \ sqrt {n}) $ .

findet jedoch dieser algorithmus immer einen maximalen $ k $ -matching?

Answer 1

nein.Hier ist ein Gegenexample: $ x={a, b \}, y= {c, d, e, f \}, e={ac, ad, ae,BE, BF \}, k= 2 $ .Die erste Iteration Ihres Algorithmus könnte $ \ {AE, BF \} $ (insbesondere der Kante $ AE $) wählen), wobei verhindert wird, dass eine Lösung gefunden wird, obwohl man existiert: $ \ {AC, AD, BE, BF \} $ .