Menghubungkan sel dengan permutasi baris dan kolom dalam kisi terbatas

Saya ingin tahu apakah masalah sederhana berikut telah dipelajari sebelumnya dan apakah ada solusi yang diketahui.

Biarkan G menjadi kisi terbatas (MxN), S himpunan bagian dari sel G ("remah"). Dua remah dikatakan terhubung (lokal) jika koordinatnya berbeda paling banyak satu (yaitu, jika digambarkan sebagai kotak, mereka berbagi setidaknya satu titik sudut).

Sekarang, orang dapat mencoba untuk menghubungkan remah-remah (set mereka secara keseluruhan) dengan permutasi garis dan kolom dari kisi. Dengan kata lain, tujuannya adalah untuk menghasilkan permutasi dari garis-garis dan permutasi kolom sehingga setiap dua remah dalam kisi yang dihasilkan dihubungkan oleh rantai remah-remah yang terhubung (secara lokal).

Pertanyaan: apakah selalu ada solusi?

Saya tidak tahu bagaimana cara menyerangnya. Karena kurangnya ide yang lebih baik, saya telah menulis sebuah program mentah yang mencari solusi dengan kekerasan (ini menghasilkan permutasi secara acak dan memeriksa apakah grid yang dihasilkan memiliki remah-remahnya terhubung). Program sejauh ini selalu menemukan solusi pada kisi-kisi bertubuh kecil (10x10 atau 7x14), dan kisi-kisi yang lebih besar jelas di luar jangkauan strategi simplistisnya (akan butuh waktu terlalu lama untuk menemukan solusi secara acak).

Berikut adalah contoh grid yang dipecahkan oleh program:

Kotak awal (remah dilambangkan dengan X's, sel kosong oleh titik-titik):

   0 1 2 3 4 5 6 7 8 9 
 0 X . X X . X . X X .
 1 X . . . . X . . . .
 2 . . X . . . . X . X
 3 . X . . X . X . . X
 4 . . . X . . . . . .
 5 X X . . . X X . X .
 6 . . . X . . . . X .
 7 X . X . . X . . . .
 8 X . . . X . . X X .

Larutan:

   6 1 4 7 8 2 9 3 5 0
 1 . . . . . . . . X X
 4 . . . . . . . X . .
 5 X X . . X . . . X X
 8 . . X X X . . . . X
 7 . . . . . X . . X X
 0 . . . X X X . X X X
 3 X X X . . . X . . .
 6 . . . . X . . X . .
 2 . . . X . X X . . .

Secara alami, masalahnya dapat dengan mudah digeneralisasikan ke dimensi apa pun d> 2. Saya kira generalisasi lain dapat dipertimbangkan.

Terima kasih sebelumnya,

Yann David

ds.algorithms graph-theory graph-algorithms Yann David
sumber

masalah yang menarik. apakah ada beberapa aplikasi?

Suresh Venkat

@ Tsuyoshi: Anda benar sosok yang saya posting memiliki solusi (yang Anda berikan). Saya menghapusnya.

Marzio De Biasi

Crosspost simultan tidak disarankan. math.stackexchange.com/questions/83231/…

Tsuyoshi Ito

Jawaban:

Mari kita coba argumen penghitungan serupa dengan yang ada di versi sebelumnya dari jawaban saya, lebih hati-hati.

Diberikan input 0-1 matriks dengan q nonzeros, tentukan "solusi" untuk menjadi permutasi dari baris, permutasi kolom, dan matriks 0-1 yang terhubung yang didapat sebagai output setelah melakukan permutasi. Pengamatan penting di sini adalah bahwa paling banyak matriks keluaran yang berbeda mungkin: sekali kita membuat salah satu dari pilihan untuk posisi salah satu nonzeros, kita dapat menyandikan sisa matriks keluaran dalam bit dengan melakukan preorder traversal dari spanning tree dari nonzeros dan merekam untuk setiap edge pada tree apakah itu pergi ke leaf, apakah itu edge terakhir dari induknya, dan apa arahnya. Jadi jumlah solusi paling banyak adalah . $n^2 2^{5q}$ $n^2$ $5q$ $n^2 2^{5q} (n!)^2$

Sekarang setiap solusi hanya berfungsi untuk satu input, karena kita dapat membalik permutasi untuk mendapatkan kembali input dari matriks output. Jumlah input yang memiliki tepat nonzeros per baris adalah , dan untuk konstanta ini dapat ditulis ulang . Tetapi untuk jumlah solusinya adalah . Untuk , input lebih banyak dari solusi, jadi ada input yang tidak dapat dipecahkan. $c$ $\binom{n}{c}^n$ $c$ $\exp(cn\log n-O(n))$ $q=cn$ $\exp(2n\log n+O(cn))$ $c>2$

David Eppstein
sumber

Pengaturan dan mengabaikan istilah, saya mengejar ketidaksetaraan Anda untuk menemukan titik "titik impas", mendapatkan . Nilai terakhir sangat dekat dengan 26608.

c = 3

$c=3$

o (n)

$o(n)$

n > 6 * 2^{15} / e^{2}

$n > 6*2^{15}/e^2$

hardmath

Itu kebetulan numerik yang aneh. Saya sudah menanyakannya di mathoverflow.net/questions/81368/…

David Eppstein

Itu memang bukti yang elegan dan meyakinkan. (Saya mengambil sedikit waktu saya untuk merinci perkiraan untuk keuntungan saya sendiri.) Masih harus dilihat apakah ada orang yang berhasil menghasilkan contoh-contoh nyata. Komentar @ hardmath di atas menunjukkan itu bisa sulit (CE akan menjadi binatang yang jelek); sekarang orang tidak perlu memiliki jumlah remah yang sama di semua baris CE.

Yann David