Euler-Parkerova metoda

Euler-Parkerova metoda je metoda pro konstrukci ortogonálního čtverce pro daný latinský čtverec řádu . Navrhl Parker v roce 1959 [1] .

Metoda

Metoda vyhledávání se skládá ze tří kroků:

  1. Konstrukce množiny transverzál daného latinského čtverce.
  2. Výběr z nich podmnožin neprotínajících se transverzál.
  3. Tvorba ortogonálních latinských čtverců z nalezených podmnožin.

Konstrukci transverzál a volbu jejich neprotínajících se podmnožin lze realizovat metodou brute-force , efektivnější praktickou realizací je však polynomiální redukce těchto problémů na problém přesného pokrytí , For na jehož řešení je efektivní použít algoritmus tanečního spojení ( DLX).

Při hledání ortogonálních diagonálních latinských čtverců se místo obecných transverzál používají diagonální transverzály, které obsahují po jednom prvku z hlavní a vedlejší úhlopříčky čtverce.

Vytvoření ortogonálního čtverce z nalezené podmnožiny neprotínajících se transverzálů se provádí vyplněním každého --tého transverzálu hodnotou ve vytvořeném ortogonálním čtverci.

Historické pozadí

Leonhard Euler v průběhu řešení problému 36 důstojníků vyslovil hypotézu, že dvojice ortogonálních latinských čtverců neexistují pro všechny dimenze . Správnost dohadu o rozměru potvrdil Thomas Clausen v roce 1842. Hledání protipříkladu k Eulerově domněnce bylo provedeno v roce 1957 Page a Tompkinsem pomocí metody hrubé síly na počítači SWAC , ale nebylo úspěšné kvůli potřebě obrovských výpočetních nákladů. V roce 1959 navrhl Parker [1] konstrukci ortogonálního čtverce pomocí transversals a počítače UNIVAC a našel protipříklad k Eulerově domněnce pro objednávku . Podobný výsledek vyvracející Eulerovu domněnku publikovali ve stejném roce Bose a Shrinkhand [2] . V roce 1992 Brown [3] popsal diagonální latinský čtverec řádu 10, který má současně 4 ortogonální diagonální latinské čtverce, z nichž 3 jsou uvedeny v článku, a 4. našel O. Zaikin pomocí přístupu založeného na SAT . V současnosti jsou známy diagonální latinské čtverce řádu 10, které mají 1, 2, 3, 4, 5, 6, 7, 8 a 10 normalizovaných ortogonálních diagonálních latinských čtverců (sekvence A287695 v OEIS ). Tvoří 42 kombinatorických struktur (graf diagonálních latinských čtverců na množině vztahu binární ortogonality) [4] . Většina z nich byla od roku 2017 nalezena v dobrovolném distribuovaném výpočetním projektu Gerasim@Home . Otázky týkající se existence diagonálních latinských čtverců řádu 10 s velkým počtem normalizovaných ortogonálních latinských čtverců a existence kliky mohutnosti více než dvou párové ortogonální latinské čtverce řádu 10 jsou aktuálně otevřené.

Viz také

Poznámky

  1. ↑ 1 2 3 Parker E. T. Ortogonální latinské čtverce // Proc. Natl. Akad. sci. USA. sv. 45(6). 1959.pp. 859–862.
  2. ↑ Bose RC, Shrikhande SS O nepravdivosti Eulerovy domněnky o neexistenci dvou ortogonálních latinských čtverců řádu 4t + 2 // Proč Natl Acad Sci USA A. 1959 květen; 45(5): 734–737.
  3. ↑ Brown JW, Cherry F., Most L., Most M., Parker ET, Wallis WD Dokončení spektra ortogonálních diagonálních latinských čtverců // Poznámky k přednáškám v čisté a aplikované matematice. 1992 sv. 139.pp. 43–49.
  4. ↑ Seznam kombinatorických struktur z DLC řádu 10 na sadě vztahů ortogonality . Staženo 5. června 2020. Archivováno z originálu dne 21. května 2020.

Literatura