В.А. Носов - Комбинаторика и теория графов (1023552), страница 11

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 11)

Суммируем числаa 1i1 ,K , a ni n по всем n-перестановкам элементов 1, 2, … , m. Тогда получим с одной стороны число систем различных представителей для X1, … , Xn, а с другой - значение перманента матрицы А. ♦69Следствие. Система различных представителей для X1, … , Xn существует тогдаи только тогда, когда для соответствующей матрицы инциденция А выполнено:per A > 0(7)Поскольку в формуле (1) m(m - 1) … (m - n +1) членов, то вычисление перманента наоснове определения затруднительно. Приведем для этой цели общую формулу.2.

Ограничимся рассмотрением квадратных числовых матриц А = (aij), i, j = 1, n .∑Тогда per A =( i1 ,K,i n )a 1i 1 ⋅ a 2i2 ⋅L a ni nгде сумма распространяется по всем перестановкам i1, … , in элементов1, 2, … , n. Применим формулу включения-исключения для вычисления перманента матрицы А. Каждому набору i1, … , in поставим в соответствие вес, равный a 1i1 , K , a ni n .Значит перманент А - это сумма весов тех наборов, которые соответствуют перестановкам. Введем n свойств P1, … , Pn на множестве всех наборов i1, i2, … , in из 1, 2, … , n, гдесвойство Pi означает, что в наборе i1, … , in нет элемента i.

Таким образом, перманент А это сумма весов наборов i1, … , in, не обладающих ни одним из свойств P1, … , Pn. Осталось определить сумму весов W( Pi 1 , K , Pi k ) наборов, обладающих k свойствамиPi 1 ,K , Pi k . Имеем для суммы весов W(0) всех наборов i1, … , ik.W(0) =∑ a 1i1 , K , a ni n = (a 11 +L+a 1n )(a 21 +L+ a 2 n )L (a n1 +L+ a nn )(8)i1 ,K,i nW(N(Pi)) =^^∑ a 1i1 , K , a ni n = (a 11 +L+ a 1i +L+ a 1n )L (a n1 +L a ni +L+ a nn ) (9)i1 ,K,i n≠iгде знак ^ над элементом матрицы А означает, что этот элемент следует опустить.Аналогично для sij (i < j) имеем^^^^W(N(Pi, Pj)) = (a 11 +L+ a 1i +L+ a 1 j +L+ a 1n )L (a n1 +L a ni +L+ a nj +L+ a nn ) (10)Теперь, используя формулу включения-исключения, получаем формулу Райзера дляперманента А:n^per A = ∏in=1 (a i1 +L+ a in ) − ∑ ∏ nk =1 (a k1 +L+ a ki +L+ a kn ) +L +i =1+ ( −1) s^^n(aLaLa++++ki 1ki s +L+ a kn ) +L∑ ∏ k =1 k11≤i1 <L<is ≤ n(11)Вычисление перманента по формуле Райзера можно организовать так, что потребуется70(2n - 1)(n - 4) умножений и (2n - 2)(n + 1) сложений.

Хотя эта величина растет быстро сростом n, данная формула дает наиболее эффективный способ вычисления перманентов.3. Выясним теперь вопрос об условиях равенства нулю перманента(0, 1)-матрицы. Ограничимся случаем квадратной матрицы.Теорема 2. Пусть A = (aij), i, j = 1, n - (0, 1)-матрица порядка n. Тогдаper A= 0 в том и только в том случае, когда в А существует подматрица из нулей размераs × t, где s + t = n + 1.♦ Пусть такая нулевая подматрица в А существует.

Поскольку перманент неменяется от перестановок строк и столбцов, то можно считать, что эта подматрица расположена в левом нижнем углу, т.е. B CA=  O Dгде О - (s × t) - матрица из нулей, подматрица B имеет размер (n - s) × t. Любой член перманента А должен содержать по одному элементу из первых t столбцов. Поэтому, еслиискать положительный член перманента, то элементы этих столбцов должны принадлежать попарно различным строкам с номерами 1, 2, … , n - s.

Однако n - s = t - 1 < t и поэтому данное условие выполнить нельзя, т.е. per A = 0.Пусть теперь per A = 0. Доказательство теоремы проводим индукцией по n. Приn = 1 утверждение очевидно (А = (0)). Пусть оно справедливо для всех порядков, меньших n. Если А - нулевая матрица порядка n, то утверждение очевидно.

Если А - не нулевая матрица, то пусть aij = 1. Запишем разложение А по строке i:per A = ai1Ai1 + … + ainAinПоскольку per А = 0, то per Аij = 0. Но Аij имеет размер (n - 1) × (n - 1) и по предположению индукции для нее существует подматрица из нулей размераs1 × t1 , причем s1 + t1 = n - 1 + 1 = n. Переставим строки и столбцы так, чтобы эта нулеваяподматрица оказалась в нижнем левом углу: C EA → B=  O Dгде О - нулевая подматрица размера s1× t1, s1 + t1 = n, С - имеет размер (n - s1) × t1, D имеет размер s1 × (n - t) . Значит, матрицы С и D - квадратные и имеют порядок (t1 × t1) и(s1 × s1) соответственно.

Согласно определению перманента имеем per B = per A и ,per B = per C ⋅ per D и поэтому из per А = 0 следует, что либо per C = 0, либо per D = 0.Пусть per C = 0. По предположению индукции в С найдется нулевая подматрица размера71u × v, где u + v = t1 + 1. Пусть она расположена в строках с номерами i1, … , iu и столбцами с номерами j1, … , jv . Рассмотрим подматрицу B, состоящую из строкi1, … , iu, t1+ 1, … , n и столбцов j1, … , jv. Это нулевая подматрица размера (u + n - t1) × v,где u + n - t1 + v = n + +1. Итак, в матрице B указана нулевая подматрица размера s × t,где s + t = n + 1.

Так как матрицы А и B отличаются перестановкой строк и столбцов, тотеорема доказана. ♦Рассмотрим теперь важный частный случай матрицы А. Обозначим через А(k,n) - матрицу из элементов 0,1 размера n × n с k единицами к каждой строке и каждомстолбце (k > 0).Теорема 3. Для любой матрицы А(k, n) справедливо per А(k, n) > 0.♦ Допустим противное, что per А(k, n) = 0.

Тогда по теореме 2 существует нулевая подматрица размера s × t, где s + t = n + 1. Тогда, переставляя строки и столбцы матрицы А(k, n) получим матрицу B C O Dгде О - нулевая (s × t)-матрица.Подсчитаем число единиц в матрицах B и D. Поскольку A(k, n) имеет k единиц в каждойстроке и каждом столбце, то в каждом столбце B и каждой строке D имеется точно kединиц. Всего в А(k, n) имеется n⋅k единиц, поэтому nk ≥ tk + sk = (t + s)n. Таким образом, n ≥ t + s, что невозможно, т.к. s + t = n + 1 Из данного противоречия следует справедливость утверждения.

♦Аналогично доказываетсяТеорема 3а. Пусть А - (0,1)-матрица размера n×m (n≤m). Тогда perА = 0 в том итолько в том случае, когда содержит нулевую подматрицу размера s×t, где s+t=m+1.4. Рассмотрим теперь приложение рассматриваемых вопросов к построению латинских квадратов.

Латинским (n×m)-прямоугольником над множеством X={x1,…,xm}называется (n×m) -матрица из элементов X, в которой каждая строка есть n-перестановкаX, а каждый столбец есть m-перестановка множества X. При n=m латинский прямоугольник называется латинским квадратом.Ясно, что при n=1 число латинских 1×m прямоугольников равно m!. При n=2после того, как выбрана первая строка, в качестве второй можно взять любую перестановку, противоречащую выбранной. Число таких перестановок Dm, поэтому число 2×m латинских прямоугольников равно m! ⋅ Dm.72Возникает естественный вопрос в связи с индуктивным построением латинскихквадратов.

Пусть мы построили латинский (n×m)-прямоугольник (n<m). Можно ли егорасширить до ((n+1)×m) -прямоугольника добавлением (n+1)-й строки?СправедливаТеорема 4. Всякий латинский (n×m) -прямоугольник n<m можно расширить долатинского квадрата (n×n) добавлением m-n новых строк.♦Пусть X={x1,…,xm } и L- латинский (n×m)-прямоугольник с элементами из X.Рассмотрим набор множеств A1,… ,Am где Ai - элементы i -го столбца латинского прямоугольника L.

Пусть А - матрица инцидентности системы множеств A1,… ,Am. Она имеетразмер m×m , и каждая строка матрицы А содержит точно n единиц, поскольку Ai= n,i = 1, m . Каждый элемент xi ∈ X может появиться в столбцах L не более m раз, иначенашлась бы строка, в которой этот элемент встретится дважды.

Общее число элементовL равно m⋅n, поэтому каждый элемент xi ∈ X появляется в столбцах точно n раз. Отсюдаследует, что и каждый столбец матрицы А содержит точно n единиц. Рассмотрим теперьматрицу A , полученную заменой каждой единицы на нуль и каждого нуля на единицу.Матрица A есть матрица инциденций системы множеств X1, … , Xn , где Xi = X\Ai,i = 1, m . Она содержит по m - n единиц в каждой строке и в каждом столбце. По теореме3 per A > 0. Пусть ai1 … a mi m ≠ 0 .

Тогда имеем x i1 ∈ X1 ,K , x i m ∈ X m и все элементыx i1 , K , x i m попарно различны. Строка x i1 , K , x i m может быть взята в качестве (n + 1)-ойдля латинского (n × m)-прямоугольника L. Продолжая эту процедуру, получим латинский квадрат.

Характеристики

Список файлов книги