Verbinden von Zellen durch Linien- und Spaltenpermutationen in einem endlichen Gitter

Ich würde gerne wissen, ob das folgende einfache Problem bereits untersucht wurde und ob eine Lösung bekannt ist.

Sei G ein endliches (MxN) Gitter, S eine Teilmenge von Gs Zellen (die "Krümel"). Zwei Krümel sollen (lokal) verbunden sein, wenn sich ihre Koordinaten um höchstens eins unterscheiden (dh wenn sie als Quadrate gezeichnet sind, teilen sie sich mindestens einen Eckpunkt).

Jetzt kann man versuchen, die Krümel (ihre Gesamtmenge) zu verbinden, indem man die Linien und Spalten des Gitters permutiert. Mit anderen Worten, das Ziel besteht darin, eine Permutation der Linien und eine Permutation der Spalten zu erstellen, so dass zwei beliebige Krümel im resultierenden Gitter durch eine Kette von (lokal) verbundenen Krümeln verbunden sind.

Frage: Gibt es immer eine Lösung?

Ich weiß nicht genau, wie ich es angreifen soll. Aus Mangel an einer besseren Idee habe ich ein Rohprogramm geschrieben, das mit roher Gewalt nach Lösungen sucht (es generiert die Permutationen zufällig und prüft, ob die Krümel des resultierenden Gitters verbunden sind). Das Programm hat bisher immer Lösungen für kleinere (10x10 oder 7x14) Gitter gefunden, und größere Gitter sind eindeutig außerhalb der Reichweite seiner simplen Strategie (es würde zu lange dauern, um zufällig über eine Lösung zu stolpern).

Hier ist ein Beispiel für ein vom Programm gelöstes Raster:

Anfangsraster (Krümel werden mit X bezeichnet, leere Zellen mit Punkten):

   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 .

Lösung:

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

Natürlich kann das Problem leicht auf jede Dimension d> 2 verallgemeinert werden. Ich nehme an, andere Verallgemeinerungen könnten in Betracht gezogen werden.

Danke im Voraus,

Yann David

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

interessantes Problem. Gibt es eine Anwendung?

Suresh Venkat

@ Tsuyoshi: Sie haben Recht, die Figur, die ich gepostet habe, hat eine Lösung (die, die Sie bereitgestellt haben). Ich habe es gelöscht.

Marzio De Biasi

Von einem gleichzeitigen Crosspost wird abgeraten. math.stackexchange.com/questions/83231/…

Tsuyoshi Ito

Versuchen wir es mit einem ähnlichen Zählargument wie in der früheren Version meiner Antwort.

$n^2 2^{5q}$ $n^2$ $5q$ $n^2 2^{5q} (n!)^2$

$c$ $\binom{n}{c}^n$ $c$ $\exp(cn\log n-O(n))$ $q=cn$ $\exp(2n\log n+O(cn))$ $c>2$

David Eppstein
quelle

Wenn ich setze und Terme vernachlässige, ich Ihre Ungleichung durch, um den "Breakeven" -Punkt zu finden, und erhalte . Der letztere Wert liegt bemerkenswert nahe bei 26608.

c = 3

$c=3$

o (n)

$o(n)$

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

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

Hardmath

Das ist ein merkwürdiger numerischer Zufall. Ich habe danach unter mathoverflow.net/questions/81368/… gefragt

David Eppstein

Das ist in der Tat ein eleganter und überzeugender Beweis. (Ich habe eine Weile gebraucht, um die Annäherungen zu meinem eigenen Vorteil detailliert darzulegen.) Es bleibt abzuwarten, ob es jemandem gelingt, ein konkretes Gegenbeispiel zu finden. @ hardmaths Kommentar oben legt nahe, dass es schwierig sein könnte (das CE wäre ein hässliches Tier); Jetzt muss man nicht mehr alle Krümel in allen Reihen eines CE haben.

Yann David

Verbinden von Zellen durch Linien- und Spaltenpermutationen in einem endlichen Gitter

Antworten: