Латинский квадрат
Материал из Википедии — свободной энциклопедии
Лати́нский квадра́т — таблица n × n, заполненная n различными символами таким образом, чтобы в каждой строке и в каждом столбце встречались все n символов (каждый по одному разу). Ниже приводятся два примера:
Латинские квадраты существуют для любого n. Любой латинский квадрат является таблицей умножения (таблицей Кэли) квазигруппы.
Содержание |
[править] Ортогональные латинские квадраты
Два латинских квадрата называются ортогональными, если различны все пары символов (a,b), где a — символ в некоторой клетке первого латинском квадрата, а b — символ в той же клетке второго латинского квадрата. Пример пары ортогональных латинских квадратов:
Ортогональные латинские квадраты существуют для любого порядка n кроме 2 и 6. Для n являющихся степенью простого числа есть набор n-1 взаимно ортогональных латинских квадратов. Это следует из теоремы о том, что набор n-1 взаимно ортогональных латинских квадратов порядка n существует тогда и только тогда, когда существует конечная проективная плоскость порядка n.
[править] Использование латинских квадратов для планирования экспериментов
Предположим, что нужно провести несколько экспериментов, зависящих от 3 параметров 1≤a,b,c≤n, так чтобы для каждой пары параметров были опробованы все n² вариантов. Тогда нужно взять любой латинский квадрат порядка n и провести n² экспериментов с параметрами a = номер строки, b = номер стоблца, c = значение в клетке латинского квадрата.
[править] Задача о заполнении латинского квадрата
Пусть дана таблица n × n, в которой некоторые ячейки пусты, а в некоторых стоят числа от 1 до n. Задача о заполнении латинского квадрата формулируется так: существует ли способ вписать числа в пустые ячейки так, чтобы полученная таблица стала латинским квадратом.
Задача о заполнении латинского квадрата NP-полна.
[править] См. также
 |
Это незавершённая статья по математике. Вы можете помочь проекту, исправив и дополнив её. |
