Pencocokan bipartit dengan dominasi gelar

Diberikan grafik bipartit tanpa bobot . Apakah benar bahwa selalu ada pencocokan non (belum tentu maksimal), sehingga untuk setiap dengan cocok dan cocok , ia memegang ? Di sini tidak dipesan, yaitu, bisa berada di kedua sisi. $G=(V, E)$ $M\subseteq E$ $(i,j)\in E$ $i$ $j$ $\deg(i)>\deg(j)$ $(i,j)$ $i$

Intuisi saya tentang mengapa ini benar adalah, ketika setiap simpul dalam memiliki derajat yang sama, selalu ada pencocokan sempurna yang merupakan pencocokan yang kami butuhkan. Untuk beberapa struktur grafik sederhana seperti pohon atau grafik unicyclic pencocokan maksimal diinginkan karena tingkat daun selalu lebih kecil dari induknya. $V$

Saya mencoba membuktikannya dari teorema Hall tetapi gagal. Bagian dari kompleksitas masalah ini adalah bahwa solusinya tidak selalu cocok secara maksimal. Misalnya, mengingat grafik yang terdiri dari dua 4-siklus dan . Maka dan pencocokan simetris adalah satu-satunya solusi, yang tidak maksimal. $abcd$ $defg$ $M=\{ab,cd\}$

graph-theory matching Willard Zhan
sumber

@Gamow dua simpul yang Anda berikan tidak membentuk keunggulan dalam

E

$E$

Willard Zhan

@AndrewMorgan Dalam contoh terakhir saya

karena muncul di kedua siklus. Dan kendala hanya untuk tepi tersebut dengan tepat satu titik akhir yang cocok. Jadi kami tidak mempertimbangkan

jika

maupun

tidak cocok.

\deg (d) = 4

$\deg(d)=4$

(u, v)

$(u,v)$

u

$u$

v

$v$

Willard Zhan

Bisakah Anda menunjukkan contoh di mana properti Anda tidak berlaku untuk grafik non-bipartit?

JimN

@JimNastos segitiga harus melakukan trik

Yonatan N

Anda mengatakan dalam pertanyaan bahwa

adalah "... belum tentu maksimal ..." ... sehingga hanya mengandung satu sisi, bukan? Bagaimana dengan siklus panjang genap?

M

$M$

Marzio De Biasi

Jawaban:

Tidak selalu ada kecocokan dengan properti Anda dalam grafik bipartit.

Perhatikan misalnya grafik mana $G = (V, E)$

dan $V = \{a_1, a_2, a_3, b_1, b_2, b_3, c_1, c_2, d_1, d_2, x\}$
$E = \{a_1, a_2\} \times \{c_1, c_2, x\} \cup \{b_1, b_2\} \times \{d_1, d_2, x\} \cup \{(a_3, c_1), (a_3, d_2), (a_3, x), (b_3, d_1), (b_3, c_2), (b_3, x)\}$

Grafik ini adalah bipartit (dengan sebagai salah satu bagian dan seperti yang lainnya). Setiap simpul dalam grafik ini kecuali memiliki derajat . Vertex memiliki derajat . $V_1 = \{a_1, a_2, a_3, b_1, b_2, b_3\}$ $V_2 = \{c_1, c_2, d_1, d_2, x\}$ $x$ $3$ $x$ $6$

Misalkan, demi kontradiksi, ada huruf cocok dengan properti Anda. Pertimbangkan setiap dua simpul yang berdekatan dan yang memiliki derajat yang sama. Ternyata kondisi pada menyiratkan bahwa kedua simpul ini memiliki status yang sama atau tidak sama (yaitu keduanya atau tidak satu pun dari simpul harus cocok dalam ). Ini dapat dibuktikan dengan sangat sederhana melalui kontradiksi: misalkan satu simpul (wlog ) cocok dan yang lainnya tidak; maka karena ada keunggulan antara mereka, properti diberikan pada mengatakan bahwa $M$ $v_1$ $v_2$ $M$ $M$ $v_1$ $M$ , yang merupakan kontradiksi. $deg(v_1) > deg(v_2)$

$G$ $V \setminus \{x\}$ $3$ $V \setminus\{x\}$ $M$ $M$ $V_1$ $M$ $V_1$ $V_2$ $G$ $M$ $x$ $M$

$M$ $G$

Mikhail Rudoy
sumber

Ya, saya ingin menggunakan argumen yang pada dasarnya sama untuk membuktikan bahwa praktis setiap expander bipartit 3-reguler dapat dijadikan sampel-balik jika kita menghapus satu simpul dan menghubungkan 3 tetangganya dengan simpul lain yang cukup jauh.

domotorp