нет. Учебное пособие в оронеж 2011 фгбоу впо Воронежский государственный технический университет

• Название: Учебное пособие в оронеж 2011 фгбоу впо Воронежский государственный технический университет
• Дата: 23.12.2020
• Размер: 0.65 Mb.
• Имя файла: Teoria_avtomatov.docx
• Тип: Учебное пособие; #163524
• страница: 8 из 17

1.7. Трансверсали и перманенты

1.7.1. Множества и мультимножества

Не существует формального определения множества; считается, что это понятие первичное и не определяется. Так, можно говорить, что множество есть объединение различных элементов, но при этом мы оставляем неопределяемыми понятия "объединение" и "элементы". Дадим следующее определение множеству: множество - это неупорядоченная совокупность различных объектов или структура данных, используемая для представления множества. Мультимножество есть объединение не обязательно различных элементов; его можно считать множеством, в котором каждому элементу поставлено в соответствие положительное целое число, называемое кратностью.

Конечное множество S будем записывать в следующем виде:

S = {s₁, s₂, …, s_n}

где s₁, s₂, …, s_n - элементы S, обязательно различные! Мощность множества S обозначается как |S|, для выписанного выше множества мощность записывается так |S| = n. Если S- конечное мультимножество, то будем записывать его в следующем виде:
S = {s₁, s₁, …, s_1, s₂, s₂, …, s₂,s₃…, s₃} = {m₁*s₁,m₂*s₂,m_n*s_n }

m₁ раз m₂ раз m₃ раз
Здесь все S_iразличны и m_i- кратность элемента s_i. В этом случае мощность S равна

|S| = ∑m_i (i = 1..n)

Наиболее общими операциями на множествах и мультимножествах являются операции объединения и пересечения. Для множеств эти операции будем обозначать и , а для мультимножеств и . Последовательное и связанное представление последовательностей можно использовать для множеств и мультимножеств очевидным способом. Индуцируя искусственный порядок элементов множества, или используя собственный порядок, если он существует, можно рассматривать множество как последовательность. Аналогично, как последовательность можно рассматривать и мультимножество, или, для того чтобы сэкономить место, его можно рассматривать как последовательность пар, каждая из которых состоит из элемента и его кратности.

Как и для последовательностей, наилучший метод представления множеств или мультимножеств существенно зависит от операций, которые выполняются над ними. Предположим, например, что имеем дело с непересекающимися подмножествами множества S = {s₁, s₂, …, s_n} и что над ними необходимо выполнить две следующие операции: объединение двух множеств и отыскание подмножества, содержащего данное s_i. Таким образом, в любой момент времени имеем разбиение S на непустые непересекающиеся подмножества. Рассмотрим эти операции в конце данной лекции.

С целью идентификации считаем, что каждое из непересекающихся подмножеств множества S имеет имя. Имя - это просто один из элементов подмножества, или, иначе, - представитель подмножества. Когда мы будем ссылаться на имя подмножества, то будем под этим подразумевать его представителя. Рассмотрим, например, множество разбитое на четыре непересекающихся подмножества {1, 6, [7], 8, 11}, {[3], 4, 5}, {[2]}, {9, [10]}.

В каждом из подмножеств, взятый в скобки элемент является его именем. Если нам нужно найти подмножество, в котором содержится восьмерка, искомым ответом будет 7, то есть имя подмножества, содержащего восьмерку. Если нужно взять объединение подмножеств с именами 2 и 10, получим разбиение множества S следующего вида:

{1, 6, [7], 8, 11}, {[3], 4, 5}, {[2]} {9, 10]}

Именем множества {[2]} {9, 10]} может быть или 2, или 10. Предполагаем, что вначале имеется разбиение множества S = {s₁, s₂, …, s_n} на nподмножеств, каждое из которых состоит из одного элемента

{[s₁], [s₂], …, [s_n]}

и имя каждого из них есть просто этот единственный элемент. Это разбиение преобразуется путем применения операций объединения вперемешку с операциями отыскания. Такая кажущаяся на первый взгляд надуманной задача чрезвычайно полезна в определенных комбинаторных алгоритмах; пример ее полезности виден в "жадном" алгоритме.

1.7.2. Трансверсали

Пусть дано множество мощности n и множество , элементы которого являются подмножествами множества S, т.е.. , . При этом допускается что при

Системой различных представителей (транверсалью) для совокупности множеств M(S) называется множество элементов мощности m из множества S и таких, что

1. 
   ,
   
2. 
   , при .
   

Критерием существования трансверсали для M(S) служит следующая теорема.

Теорема Холла. Совокупность множеств M(S) имеет трансверсаль тогда и только тогда, когда для любого k и любой k – выборки без повторений из множества индексов выполняется следующее неравенство

то есть число элементов объединения множеств не меньше k.

Если для некоторого подсемейства семейства M(S) имеет место равенство


то такое подсемейство называется критическим.

1.7.3. Пермамент матрицы

Рассматривается матрица A = (a_ij), , , .

Перманентом матрицы A называется число, определяемое следующим выражением

Где суммирование производится по всевозможным выборкам объема n из m различных элементов.
Рассмотрим примеры

1. 
   
   

2. 
   
   

3. 
   
   

Если m = n, то суммирование производится по всевозможным перестановкам элементов 1,2,…,n ; а пермамент матрицы А(perA)получается из определителя этой матрицы при условии, что все слагаемые соответствующей суммы берутся с положительными знаками.

Свойства перманентов.

1. 
   Если строка матрицы A состоит полностью из нулей, то perA=0.
   
2. 
   Перманент матрицы инвариантен относительно любой перестановки строк и столбцов.
   
3. 
   При умножении какой-либо строки (или столбца) на скаляр , перманент матрицы умножается на .
   
4. 
   Если A квадратная матрица, то per A^T = per A.
   
5. 
   Если A_ijполучена вычеркиванием из А i – строки и j–го столбца, - матрица, полученная из A заменой элемента a_ij на 0, тогда
   
6. 
   Разложение перманента по i – строке.
   

Многие свойства перманента подобны свойствам определителя для квадратных матриц, однако свойство

,

вообще говоря, не верно для перманентов. Перманент в отличие от определителя в общем случае не равен 0 при наличии строк (столбцов), линейно выражающихся через другие строки (столбцы).

1.7.4. Число трансверсалей

Важнейшее применение перманентов определяется следующей теоремой.

Теорема. Пусть A = (a_ij), i = 1,2,..,n, j = 1,2,..,m, , есть матрица инцидентности множеств , являющихся подмножествами множества .

То есть

Тогда для числа трансверсалей семейства имеет место равенство

Трансверсаль семейства существует тогда и только тогда, когда для соответствующей матрицы инцидентности выполняется условие.

Пример 1. (задача о встречах). Требуется определить число трансверсалей семейства , где X_i = X\{i} и x = {1,2,..,n}. Эта задача имеет и другие разнообразные формулировки, но обычно называется задачей о встречах. В данном случае матрицы инцидентности , где - символ Кронекера.

Обозначим h_n = per(1-δ_ij) и разлагая перманент по первой строке, получим

,

Где матрица получается из матрицы заменой элемента a₁₁ на 1.

Разлагая perA′_n-1 по элементу a_11, получим

то есть получим рекуррентное соотношение

с начальными условиями h₀=1 и h₁=0

Перепишем рекуррентное соотношение в виде

h_n-nh_n-1=-(h_n-1-(n-1)h_n-2)=…=(-1)^k(h_n-k-(n-k)h_n-k-1)=…=(-1)ⁿ

Полагая , получим

Отсюда следует что

Таким образом, окончательный ответ

Пример 2.

Требуется найти число трансверсалей семейства (X_i , 1≤i≤n), где

X₁={1,2}, X₂={1,2,3}, X₃={2,3,4},…, X_n-1={n-2, n-1, n}, X_n={n-1, n}, являющихся подмножествами множества X={1,2,…,n}.

Решение.

Число трансверсалей

Разлагая этот перманент сначала по первой строке, а затем получившийся перманент разлагаем по первому столбцу, получаем рекуррентное соотношение

C_n=C_n-1+C_n-2

с начальным условием C₁=1, C₂=2

Полученные числа C_n являются числами Фибоначчи.