Jumlah simpul hadir dalam semua pencocokan maksimum

Diberikan grafik , kita perlu menemukan kardinalitas set simpul terbesar sehingga masing-masing hadir dalam setiap pencocokan maksimum yang dimungkinkan. $G$

Apakah ada solusi selain menghapus setiap simpul yang jelas dan menemukan pencocokan maksimum untuk melihatnya berkurang?

graph-theory graph-algorithms Hououin Kyouma
sumber

Saya tidak melihat bagaimana apa yang Anda sarankan bahkan merupakan solusi.

$\:$ (Pertimbangkan segitiga.)

$\hspace{1.4 in}$

@ RickyDemer pertama-tama kita menemukan pencocokan maksimum di seluruh grafik. Kemudian, kami menghapus titik dan menemukan pencocokan maksimum lagi. Jika perbedaannya adalah 1 maka kita dapat mengatakan bahwa titik ini hadir dalam semua pencocokan maksimum.

evil999man

Haruskah "menemukan pencocokan maksimum" diganti dengan "menemukan pencocokan maksimum" atau "menemukan semua pencocokan maksimum"?

$\;$

Saya pikir itu harus diganti dengan ukuran pencocokan maksimum.

evil999man

@Awesome benar. Saya akan mengedit pertanyaan saya.

Hououin Kyouma

Jawaban:

$O(n^3)$

Thomas Kalinowski
sumber

Saya hanya perlu ukuran, bukan simpul itu sendiri. Bisakah ini dilakukan dalam O (n ^ 2)? Dan terima kasih untuk makalahnya

Hououin Kyouma

$v$

Dengan melakukan dua pencarian pertama-pertama atau kedalaman-pertama, satu untuk menemukan bagian-bagian grafik yang dapat dicapai dari simpul yang tidak cocok dan satu untuk menemukan bagian yang dapat mencapai simpul yang tidak cocok, Anda dapat menemukan simpul-simpul penting dalam waktu linier begitu Anda sudah ada yang cocok.

Mungkin sesuatu seperti ini juga akan berfungsi untuk kasus non-bipartit, menggunakan pencarian jalur bolak-kontrak, tetapi detailnya akan lebih rumit.

David Eppstein
sumber

Saya ingin tahu bagaimana Anda melakukannya dalam grafik umum. Bisakah Anda menjelaskannya?

evil999man

Jika saya sudah menyelesaikannya secara terperinci, saya akan memasukkannya dalam jawaban saya. Tetapi pada dasarnya Anda hanya ingin menemukan simpul yang dapat dicapai dengan jalur bolak-balik dari simpul yang belum terjangkau, karena simpul itulah yang mungkin bisa dibiarkan tidak tertandingi. Pencarian jalur bergantian harus hampir sama dengan yang Anda gunakan untuk menemukan yang cocok di tempat pertama.

David Eppstein

Maaf atas komentar yang terlambat. Grafik saya bersifat umum. Saya akan mencoba memikirkan metode

Hououin Kyouma