Conectando células por permutações de linha e coluna em uma grade finita

Gostaria de saber se o seguinte problema simples foi estudado antes e se alguma solução é conhecida.

Seja G uma grade finita (MxN), S um subconjunto das células de G (as "migalhas"). Diz-se que duas migalhas estão conectadas (localmente) se suas coordenadas diferirem em no máximo uma (isto é, se desenhadas como quadrados, elas compartilham pelo menos um ponto de canto).

Agora, pode-se tentar conectar as migalhas (seu conjunto como um todo) permutando as linhas e as colunas da grade. Em outras palavras, o objetivo é criar uma permutação das linhas e uma permutação das colunas para que quaisquer duas migalhas na grade resultante sejam conectadas por uma cadeia de migalhas conectadas (localmente).

Pergunta: sempre existe uma solução?

Não sei bem como atacá-lo. Por falta de uma idéia melhor, escrevi um programa bruto que procura soluções por força bruta (gera as permutações aleatoriamente e verifica se a grade resultante tem suas migalhas conectadas). Até o momento, o programa sempre encontrou soluções em grades pequenas (10x10 ou 7x14), e as grades maiores estão claramente fora do alcance de sua estratégia simplista (levaria muito tempo para encontrar aleatoriamente uma solução).

Aqui está um exemplo de uma grade resolvida pelo programa:

Grade inicial (migalhas são indicadas por X's, células vazias por pontos):

   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 .

Solução:

   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 . . .

Naturalmente, o problema pode ser facilmente generalizado para qualquer dimensão d> 2. Suponho que outras generalizações possam ser consideradas.

Desde já, obrigado,

Yann David

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

problema interessante. existe alguma aplicação?

Suresh Venkat

@ Tsuyoshi: você está certo, a figura que publiquei tem uma solução (a que você forneceu). Eu deletei.

Marzio De Biasi

O cruzamento simultâneo é desencorajado. math.stackexchange.com/questions/83231/...

Tsuyoshi Ito

Respostas:

Vamos tentar um argumento de contagem semelhante ao da versão anterior da minha resposta, com mais cuidado.

Dada uma matriz de entrada 0-1 com q nonzeros, defina uma "solução" para ser uma permutação das linhas, uma permutação das colunas e a matriz 0-1 conectada que obtém como saída após executar as permutações. A observação importante aqui é que existem no máximo matrizes de saída diferentes possíveis: uma vez que fazemos uma das escolhas para a posição de um dos não-zeros, podemos codificar o restante da matriz de saída em bits , fazendo uma travessia de pré-ordem de uma árvore de abrangência dos nonzeros e registrando para cada borda da árvore se ela vai para uma folha, se é a última borda de seu pai e qual é sua direção. Portanto, o número de soluções é no total no máximo . $n^2 2^{5q}$ $n^2$ $5q$ $n^2 2^{5q} (n!)^2$

Agora, cada solução funciona apenas para uma única entrada, porque podemos reverter as permutações para recuperar a entrada da matriz de saída. O número de entradas que possuem exatamente nonzeros por linha é e, para constante, isso pode ser reescrito . Mas para o número de soluções é . Para , as entradas superam as soluções, portanto há uma entrada insolúvel. $c$ $\binom{n}{c}^n$ $c$ $\exp(cn\log n-O(n))$ $q=cn$ $\exp(2n\log n+O(cn))$ $c>2$

David Eppstein
fonte

Definindo e negligenciando os termos, procurei sua desigualdade para encontrar o ponto de equilíbrio, obtendo . Este último valor é notavelmente perto 26608.

c = 3

$c=3$

o (n)

$o(n)$

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

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

hardmath

Essa é uma curiosa coincidência numérica. Eu perguntei sobre isso em mathoverflow.net/questions/81368/…

David Eppstein

Essa é realmente uma prova elegante e convincente. (Demorei um pouco para detalhar as aproximações para meu próprio benefício.) Resta saber se alguém conseguirá apresentar um contra-exemplo concreto. O comentário de @ hardmath acima sugere que poderia ser difícil (o CE seria um animal feio); agora não é necessário ter o mesmo número de migalhas em todas as linhas de um CE.

Yann David