Латинский квадрат

Лати́нский квадра́т — таблица n × n, заполненная n различными символами таким образом, чтобы в каждой строке и в каждом столбце встречались все n символов (каждый по одному разу). Ниже приводятся два примера:

\begin{bmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \\ 3 & 1 & 2 \\ \end{bmatrix} \quad\quad \begin{bmatrix} a & b & d & c \\ b & c & a & d \\ c & d & b & a \\ d & a & c & b \end{bmatrix}

Латинские квадраты существуют для любого n. Любой латинский квадрат является таблицей умножения (таблицей Кэли) квазигруппы.

Содержание

Ортогональные латинские квадраты

Два латинских квадрата называются ортогональными, если различны все пары символов (a,b), где a — символ в некоторой клетке первого латинском квадрата, а b — символ в той же клетке второго латинского квадрата. Пример пары ортогональных латинских квадратов:

\begin{bmatrix} 2 & 3 & 1 \\ 1 & 2 & 3 \\ 3 & 1 & 2 \\ \end{bmatrix} \quad\quad \begin{bmatrix} 3 & 2 & 1 \\ 2 & 1 & 3 \\ 1 & 3 & 2 \\ \end{bmatrix}

Ортогональные латинские квадраты существуют для любого порядка n кроме 2 и 6. Для n являющихся степенью простого числа есть набор n-1 взаимно ортогональных латинских квадратов. Это следует из теоремы о том, что набор n-1 взаимно ортогональных латинских квадратов порядка n существует тогда и только тогда, когда существует конечная проективная плоскость порядка n.

Использование латинских квадратов для планирования экспериментов

Предположим, что нужно провести несколько экспериментов, зависящих от 3 параметров 1≤a,b,cn, так чтобы для каждой пары параметров были опробованы все n² вариантов. Тогда нужно взять любой латинский квадрат порядка n и провести n² экспериментов с параметрами a = номер строки, b = номер стоблца, c = значение в клетке латинского квадрата.

Задача о заполнении латинского квадрата

Пусть дана таблица n × n, в которой некоторые ячейки пусты, а в некоторых стоят числа от 1 до n. Задача о заполнении латинского квадрата формулируется так: существует ли способ вписать числа в пустые ячейки так, чтобы полученная таблица стала латинским квадратом.

Задача о заполнении латинского квадрата NP-полна.

См. также

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home