Partisi grafik kardinalitas minimum yang menghilangkan tepi tertentu

Question

Saya memiliki masalah komputasi yang ingin saya selesaikan. Saya tidak yakin apakah itu sudah dipelajari dalam literatur, atau jika demikian dengan nama apa. Saya akan menghargai petunjuk apa pun pada literatur atau saran untuk suatu algoritme.

Input: Grafik terhubung dan tidak berarah G = (V, E) di mana tepi tertentu diberi label "buruk".

Keluaran: Partisi kardinalitas minimum dari V sehingga 1) semua subgraf terinduksi dari partisi terhubung, dan 2) tidak ada subgraf terinduksi yang memiliki tepi buruk.

Terima kasih!

Answer 1

Cobalah untuk melihat apa yang terjadi ketika semua tepinya adalah sisi yang buruk .

Apa pertanyaannya jika saya bertanya:

Dapatkah Anda mempartisi grafik menjadi tiga partisi, misalnya merah, hijau, biru , sedemikian rupa sehingga untuk setiap tepi, "warna" dari titik-titik ujung setiap tepi adalah "berwarna".

(Mari kita juga membuat grafik menjadi grafik lengkap dengan menambahkan tepi yang "bagus" di antara setiap simpul yang tidak bersebelahan.)