Masalah Konektivitas Balik Minimum

Saya merumuskan masalah berikut hari ini saat bermain dengan GPS saya. Ini dia :

Misalkan menjadi grafik berarah sehingga jika e = ( u , v ) ∈ E maka ( v , u ) ∉ E , yaitu, G adalah orientasi dari grafik tak berarah yang mendasarinya. Pertimbangkan operasi berikut:$G(V,E)$$e=(u,v) \in E$$(v,u) \notin E$$G$

• : Ganti tepi ( u , v ) dengan tepi ( v , u $Flip(u,v)$$(u,v)$$(v,u)$
• : Membuat tepi ( u , v ) tidak diarahkan$undirect(u,v)$$(u,v)$

Mari menjadi dua simpul khusus. Pertimbangkan masalah pengoptimalan berikut:$s,t \in V$

• Min-Flip st-konektivitas: Diberikan dan dua simpul s , t menemukan jumlah minimum tepi yang perlu dibalik untuk membuat jalur diarahkan dari s ke t .$G$$s,t$$s$$t$
• Min-Flip kuat-konektivitas: Diberikan menemukan jumlah minimum tepi yang perlu dibalik untuk membuat G sangat terhubung. Jika tidak memungkinkan untuk membuat G sangat terhubung dengan membalik tepi maka keluaran NO.$G$$G$$G$
• Min-undirect strong-konektivitas: Diberikan menemukan jumlah tepi minimum yang perlu diarahkan untuk membuat G terhubung kuat.$G$$G$

Perhatikan bahwa Anda tidak diizinkan menambahkan tepian "baru". Anda hanya memodifikasi tepi yang ada menggunakan operasi di atas. Apakah masalah ini diketahui dalam literatur. Jika demikian, apa hasil yang diketahui?

Ringkasan: Masalah dapat diselesaikan dalam waktu polinomial dengan menemukan orientasi biaya minimum yang terhubung kuat.

Lebih detail: Teorema Robbins memberi tahu bahwa tepi grafik yang tidak diarahkan dapat diorientasikan sehingga grafik yang diarahkan sangat terhubung jika dan hanya jika grafik yang tidak diarahkan itu terhubung dengan 2-edge. Ada beberapa ekstensi, dan salah satunya mengatakan menggunakan algoritma aliran submodular waktu polinomial, kita dapat memecahkan masalah berikut dalam waktu polinomial: Diberikan grafik tidak terarah dengan biaya tepi (untuk kedua arah), temukan orientasi biaya minimum yang membuat grafik sangat terhubung. Misalnya, lihat koran Frank . Algoritma yang lebih baru disediakan oleh Iwata dan Kobayashi .

Hasil ini harus bermanfaat untuk menyelesaikan masalah yang diajukan. Masalah pertama dapat diselesaikan dengan metode yang diusulkan Tomek . Jadi kita akan berkonsentrasi pada masalah lain.

Untuk masalah kedua, kami menggunakan konstruksi yang sama dari grafik edge-weighted seperti Tomek, dan menemukan orientasi biaya minimum yang sangat terhubung dalam waktu polinomial.

Untuk masalah ketiga, untuk memungkinkan kedua arah untuk setiap sisi, kami menduplikasi setiap sisi, dan kemudian menerapkan konstruksi yang sama dan algoritma yang sama. Ini adalah pengurangan yang valid karena menggunakan arah yang sama untuk duplikasi tepi tidak mempengaruhi keterhubungan yang kuat.

$G'=(V,E')$$E'=\{(u,v,0)|(u,v) \in E\} \cup \{(v,u,1)|(u,v)\in E \}$$G$$s$$t$

$k$$k=0$$s$$t$$k$

Dalam buku terbaru saya, Connections in Combinatorial Optimization (Oxford University Press, 2011) tema sentralnya adalah masalah orientasi grafik, termasuk variasi yang dibahas di atas. Diketahui bahwa grafik 2k-edge-connected memiliki orientasi terhubung k-edge (ini adalah teorema Nash-Williams). Jika grafik tidak terhubung dengan 2k-edge, orang mungkin tertarik untuk memutuskan apakah subset F dari edge yang baik (dalam arti bahwa F memiliki orientasi sehingga grafik campuran yang dihasilkan terhubung dengan k-edge). Dalam buku ini saya menjelaskan bagaimana masalah ini dapat diselesaikan dalam waktu polinomial. Tapi saya tidak tahu bagaimana menemukan set kardinalitas minimum yang baik.

Andras Frank

Basis Konektivitas St-Flip Min: menghitung semua simpul yang dapat dijangkau dari s (T). jika t ada di T stop. Induktif: pertimbangkan semua simpul tidak dalam T yang berbatasan dengan T dengan satu flip dan sebut U ini. Hitung simpul yang dapat dicapai dari U panggil ini V. Jika t adalah V berhenti, jika tidak tambahkan V ke T dan lanjutkan.

Min-Flip konektivitas kuat Anda harus berarti tidak langsung karena Anda akan memiliki masalah dengan: A -> B