Maksimum bire çok eşleme

Question

İzin Vermek $G = (X+Y,E)$ iki parçalı bir grafik olmak ve $k\geq 1$Bir tam sayı. bir maksimum$k$-matching bir alt kümesidir$E$ her köşesinde $X$ en fazla bitişiktir $k$ kenarları ve her tepe noktası $Y$ en fazla bitişiktir $1$ kenar.

Maksimum kardinalite $k$-Eşleşme aşağıdaki algoritma ile bulunabilir:

• Oluşturmak $k$ her tepe noktasının kopyaları $x\in X$, öyle ki her kopyanın tüm komşularına bitişik olması $x$ içinde $Y$.
• Ortaya çıkan grafikte bir maksimum eşleşme bulun.

Bir grafik için çalışma zamanı karmaşıklığı $n$ köşeler ve $m$ Hopcroft-Karp algoritmasını kullanan kenarlar $O(k m\sqrt{k n}) =O(k^{3/2}\cdot m\sqrt{n})$.

Aşağıdaki alternatif algoritmayla ilgileniyorum:

• Tekrar et $k$ zamanlar:

  • Maksimum eşleşme bul $G$.
  • Eşleşen köşelerini kaldırın $Y$ grafikten.

Çalışma zamanı karmaşıklığı $O(k \cdot m\sqrt{n})$.

Ancak bu algoritma her zaman bir maksimum $k$-eşleştirme?

Answer 1

Hayır. İşte bir karşı örnek: $X=\{a,b\}, Y=\{c,d,e,f\}, E=\{ac, ad, ae, be, bf\}, k=2$. Algoritmanızın ilk yinelemesi seçebilir$\{ae,bf\}$ (özellikle kenar $ae$), mevcut olmasına rağmen bir çözüm bulunmasını engellemek: $\{ac, ad, be, bf\}$.