Diberikan grafik campuran dengan tepi dan busur , cari kecocokan dalam yang meminimalkan jumlah busur dalam , di mana diperoleh dari dengan mengontrak simpul yang cocok dan menghapus busur paralel.
Apakah (versi keputusan) masalah ini NP-complete? Apakah sudah dipelajari dalam literatur?
cc.complexity-theory
reference-request
graph-theory
Marcus Ritt
sumber
sumber
Jawaban:
Saya tidak tahu apakah maksud Anda adalah untuk memungkinkan tepi yang tidak diarahkan pada E dan busur di A menjadi paralel atau tidak, tetapi pada akhirnya tidak masalah. Dalam jawaban ini, kami berasumsi bahwa Anda tidak mengizinkan tepi dan busur paralel.
Pertimbangkan kasus khusus di mana untuk setiap busur di A , A juga berisi busur di arah yang berlawanan. Dalam hal ini, kita dapat mengabaikan orientasi busur dan menganggapnya tidak terarah. Kami menyebutnya tepi di E tepi hitam dan tepi di A merah tepi .
Jelas bahwa kita hanya perlu mempertimbangkan kecocokan maksimal pada tepi hitam untuk meminimalkan jumlah tepi merah setelah kontraksi. Juga jelas bahwa setiap pencocokan M maksimum di tepi hitam terdiri dari n tepi yang menghubungkan ke untuk i = 1, ..., n . Identifikasikan M yang cocok ini dengan penugasan kebenaran . Sangat mudah untuk memverifikasi bahwa setelah berkontraksi M dan menghilangkan tepi paralel, grafik memiliki tepat tepi merah, di mana kvi li∈{xi,x¯i} {l1,…,ln} 4(n2)−k adalah jumlah klausa yang puas dengan penugasan kebenaran ini. Oleh karena itu, meminimalkan jumlah tepi merah setelah mengontrak pencocokan di tepi hitam sama dengan memaksimalkan jumlah klausa yang puas.
sumber