Pencocokan berat maksimum dan fungsi submodular

Diberikan grafik bipartit $G = (U \cup V, E)$ dengan bobot positif, biarkan $f: 2^U \rightarrow \mathbb{R}$ dengan $f(S)$ sama dengan pencocokan berat maksimum dalam grafik $G[S\cup V]$ .

Benarkah $f$ adalah fungsi submodular?

matching submodularity George Octavian Rabanca
sumber

Bagaimana menurut anda? Sudahkah Anda mencoba membuktikan / menolaknya?

Yuval Filmus

Secara intuitif sepertinya memang benar tetapi saya tidak bisa membuktikannya. Juga saya pikir jika itu benar itu harus menjadi hasil yang terkenal tetapi saya tidak dapat menemukan referensi.

George Octavian Rabanca

Ini berlaku untuk kasus tanpa bobot, karena dapat dikurangi menjadi pemotongan minimum. Tidak jelas bagaimana cara membuktikan versi berbobot ...

Chao Xu

Pertimbangkan

K_{2, 2}

$K_{2,2}$ dengan bobot tepi 1,1,1,2.

András Salamon

@ AndrásSalamon Sepertinya pada langkah terakhir Anda menganggap bahwa

f

$f$ adalah aditif, yang tidak benar. Pencocokan maksimum

S \cap T

$S\cap T$ mungkin menggunakan simpul yang telah digunakan oleh kedua pencocokan

S ∖ T

$S \setminus T$ dan

T ∖ S

$T \setminus S$ . Saya punya bukti untuk ini sekarang tetapi jelas lebih terlibat dari ini.

George Octavian Rabanca

Definisi . Untuk himpunan terbatas , fungsi himpunan adalah submodular jika untuk menyatakan bahwa: $A$ $f:2^A \rightarrow \mathbb{R}$ $X, Y \subseteq A$

f (X) + f (Y) \geq f (X \cup Y) + f (X \cap Y) .

$f(X) + f(Y) \geq f(X \cup Y) + f(X \cap Y).$

Lemma Diberikan grafik bipartit dengan bobot tepi positif, misalkan menjadi fungsi yang memetakan dengan nilai pencocokan berat maksimum dalam . Kemudian adalah submodular. $G = (A \cup B, E)$ $f: 2^A \rightarrow \mathbb{R}^+$ $S\subseteq A$ $G[S \cup B]$ $f$

Bukti. Perbaiki dua set dan biarkan dan menjadi dua pencocokan untuk grafik dan . Untuk membuktikan lemma sudah cukup untuk menunjukkan bahwa dimungkinkan untuk mempartisi tepi dalam dan untuk grafik $X, Y \subseteq A$ $M_\cap$ $M_\cup$ $G[(X\cap Y) \cup B]$ $G[(X \cup Y) \cup B]$ $M_\cap$ menjadi dua pencocokan terpisah dan $M_\cup$ $M_X$ $M_Y$ dan masing-masing. $G[X\cup B]$ $G[Y\cup B]$

Tepi dan membentuk kumpulan jalur dan siklus bolak-balik. Biarkan menunjukkan koleksi ini dan amati bahwa tidak ada siklus mengandung simpul dari $M_\cap$ $M_\cup$ $\mathcal{C}$ $\mathcal{C}$ $X\setminus Y$ atau . Ini berlaku karena tidak cocok dengan simpul tersebut. $Y\setminus X$ $M_\cap$

Biarkan menjadi himpunan jalur di dengan setidaknya satu simpul dalam dan biarkan menjadi himpunan jalur di $\mathcal{P}_X$ $\mathcal{C}$ $X \setminus Y$ $\mathcal{P}_Y$ dengan setidaknya satu titik di . Dua jalur seperti itu digambarkan dalam gambar di bawah ini. $\mathcal{C}$ $Y \setminus X$

Klaim 1. . $\mathcal{P}_X \cap \mathcal{P}_Y = \emptyset$

Asumsikan oleh kontradiksi bahwa ada jalan . Biarkan menjadi simpul di di jalan dan juga membiarkan menjadi titik di di jalan . Perhatikan bahwa karena atau bukan milik mereka tidak termasuk dalam pencocokan $P \in \mathcal{P}_X \cap \mathcal{P}_Y$ $x$ $X\setminus Y$ $P$ $y$ $Y \setminus X$ $P$ $x$ $y$ $X \cap Y$ dengan definisi, dan karena itu mereka adalah titik akhir dari jalur . Apalagi sejak dan $M_\cap$ $P$ $x$ berada di , jalur memiliki panjang genap dan karena merupakan jalur bolak-balik, baik tepi pertama atau terakhir milik . Oleh karena itu cocok dengan atau , yang bertentangan dengan definisi dan membuktikan klaim. $y$ $A$ $P$ $M_\cap$ $M_\cap$ $x$ $y$

Misalkan dan Jelas bahwa

M_{X} = (P_{X} \cap M_{\cup}) \cup ((C ∖ P_{X}) \cap M_{\cap})

$M_X = (\mathcal{P}_X \cap M_\cup) \cup ( (\mathcal{C} \setminus \mathcal{P}_X) \cap M_\cap)$

M_{Y} = (P_{X} \cap M_{\cap}) \cup ((C ∖ P_{X}) \cap M_{\cup}) .

$M_Y = (\mathcal{P}_X \cap M_\cap) \cup ( (\mathcal{C} \setminus \mathcal{P}_X) \cap M_\cup).$

M_{X} \cup M_{Y} = M_{\cap} \cup M_{\cup}

$M_X \cup M_Y = M_\cap\cup M_\cup$ dan

. Untuk membuktikan teorema, tetap menunjukkan bahwa

dan

adalah pasangan yang cocok untuk

dan

. Untuk melihat bahwa

adalah pencocokan yang valid untuk

karena

tidak memotong

dengan Klaim 1, dan

tidak berpotongan

M_{X} \cap M_{Y} = M_{\cap} \cap M_{\cup}

$M_X \cap M_Y = M_\cap \cap M_\cup$

M_{X}

$M_X$

M_{Y}

$M_Y$

G [X \cup B]

$G[X\cup B]$

G [Y \cup B]

$G[Y\cup B]$

M_{X}

$M_X$

perhatikan terlebih dahulu bahwa tidak ada simpul

dicocokkan oleh

G [X \cup B]

$G[X\cup B]$

Y ∖ X

$Y \setminus X$

M_{X}

$M_X$

P_{X}

$\mathcal{P}_X$

Y ∖ X

$Y \setminus X$

M_{\cap}

$M_\cap$

Y ∖ X

$Y \setminus X$ menurut definisi. Oleh karena itu,

hanya menggunakan simpul dari

. Kedua amati bahwa setiap simpul

dicocokkan oleh paling banyak satu tepi

karena jika tidak

milik dua tepi

atau dua tepi

, yang bertentangan dengan definisi. Ini membuktikan bahwa

M_{X}

$M_X$

X \cup B

$X \cup B$

x \in X

$x\in X$

M_{X}

$M_X$

x

$x$

M_{\cup}

$M_\cup$

M_{\cap}

$M_\cap$

M_{X}

$M_X$ adalah pencocokan yang valid untuk

; menunjukkan bahwa

adalah matchings berlaku untuk

mirip.

G [X \cup B]

$G[X\cup B]$

M_{Y}

$M_Y$

G [Y \cup B]

$G[Y\cup B]$

George Octavian Rabanca
sumber

Ini terlihat hebat! Sebagai saran kecil: definisi

M_{X}

$M_X$ dan

tidak simetris, jadi klaim akhir Anda bahwa "

... serupa" tidak langsung. Lebih jelas (saya pikir) jika Anda membiarkan

menunjukkan komponen yang terhubung tidak menyentuh titik di

, dan kemudian mengatur

M_{Y}

$M_Y$

M_{Y}

$M_Y$

C^{'} ≐ C ∖ P_{X} ∖ P_{Y}

$\mathcal{C'} \doteq \mathcal{C} \setminus \mathcal{P}_X \setminus \mathcal{P}_Y$

X Δ Y

$X \Delta Y$

dan

menjadi sama dengan

dan

bertukar dan kemudian

berubah menjadi

M_{X} = (P_{X} \cap M_{\cup}) \cup (P_{Y} \cap M_{\cap}) \cup (C^{'} \cap M_{\cap})

$M_X = (\mathcal{P}_X \cap M_\cup) \cup (\mathcal{P}_Y \cap M_\cap) \cup (\mathcal{C'} \cap M_\cap)$

M_{Y}

$M_Y$

X

$X$

Y

$Y$

M_{\cap}

$M_\cap$

M_{\cup}

$M_\cup$

Andrew Morgan

Pencocokan berat maksimum dan fungsi submodular

Jawaban: