Дискретная математика & математическая логика
..pdf2.9. ДОПОЛНИТЕЛЬНЫЕ ВИДЫ ФАКТОРИАЛОВ
Двойной факториал числа n обозначается n!! и определяется как произведение всех чисел одинаковой с ним четности до n включительно. По определению полагают 0!! = 1.
Примориал – число n обозначается n# и определяется как произведение простых чисел, не превышающих n: 2·3·5·7·11 = 2310.
Первые 15 примориалов: 2, 6, 30, 210, 2310, 30030, 510510.
Суперфакториал числа n определяется как произведение факториалов всех целых чисел от 1 до n включительно.
Субфакториал (!n) определяется как количество беспорядков порядка n, т.е. перестановок n-элементного множества без неподвижных точек.
71
3.ТЕОРИЯ ГРАФОВ
3.1.ТРАНСВЕРСАЛЬ И ТЕОРЕМА О СВАДЬБАХ. ТРАНСВЕРСАЛЬНОЕ ПОКРЫТИЕ
Рассмотрим двудольный граф Гд(E, V), где E, V – доли. Еj – множество множеств соответствующих смежных E вершин доли [5].
Трансверсалью (или системой различных представителей, или трансверсальным покрытием) называется подмножество T V, состоящее из элементов V – по одному из каждого множества Еj
(рис. 3.1).
Рис. 3.1. Двудольный граф с трансверсалями
72
Матрица смежности этого двудольного графа имеет вид
|
v1 |
v2 |
|
v3 |
v4 |
v5 |
|
e1 |
1 |
|
|
|
|
1 |
1 |
e2 |
1 |
|
|
|
|
|
|
e3 |
|
1 |
|
1 |
|
1 |
|
e4 |
|
1 |
|
|
|
1 |
|
Для Гд(E,V)E = {e1, e2, e3, e4}, V = {v1, v2, v3, v4, v5}.
Множество множеств смежных долей E вершин доли V:
Еj = {{v1, v4, v5}, {v1}, {v2, v3, v4}, {v2, v4}}.
Легко определить четыре трансверсали:
T1 = {v1, v2, v3, v4}, T2 = {v1, v2, v3, v5},
T3 = {v1, v3, v4, v5}, T4 = {v1, v2, v4, v5}.
Получим трансверсальные покрытия путём определения декартова произведения всех подмножеств Еj и выделения из полученных четвёрок четырёхэлементных множеств:
Еj = {{v1, v4, v5}, {v1}, {v2, v3, v4}, {v2, v4}}.
Будем указывать только номера v:
1, 1, 2, 2 |
1, 1, 2, 4 |
1, 1, 3, 2 |
1, 1, 3, 4 |
1, 1, 4, 2 |
1, 1, 4, 4 |
|
|
|
|
|
|
4, 1, 2, 2 |
4, 1, 2, 4 |
4, 1, 3, 2 |
4, 1, 3, 4 |
4, 1, 4, 2 |
4, 1, 4, 4 |
|
|
|
|
|
|
5, 1, 2, 2 |
5, 1, 2, 4 |
5, 1, 3, 2 |
5, 1, 3, 4 |
5, 1, 4, 2 |
5, 1, 4, 4 |
|
|
|
|
|
|
Переходя к соответствующим множествам, получим четыре указанные выше трансверсали.
73
Теорема о свадьбах (или теорема Холла)
Теорема Холла (или теорема о свадьбах), названная в честь английского математика Филипа Холла, гласит, что если в двудольном графе любые k элементов одной из долей связаны по крайней мере с k элементами другой, то граф разбивается на пары, т.е. каждый юноша может жениться на знакомой девушке. Действительно, как можно жениться на незнакомой?!
Возьмём
Еj = {{v1, v4, v5}, {v1}, {v2, v3, v4}, {v2, v4}}.
Е1 = {v1, v4, v5}, т.е. е1 связана с тремя v;
Е1 Е2 = {v1, v4, v5}, т.е. е1, е2 связаны с тремя v;
Е1 Е2 Е3 = {v1, v2, v3, v4, v5}, т.е. е1, е2, е3 связаны с пятью v;
Е1 Е2 Е3 Е4 = {v1, v2, v3, v4, v5}, т.е. е1, е2, е3, е4 связаны с пя-
тью v и т.д. – всего 15 возможных объединений (булеан от 4 элементов без пустого множества), т.е.
k |
k |
E≥ |
k≤ ,1≤ k |
|
E |
|
. |
|
|
||||||
|
i=1 |
i |
|
|
|
|
|
|
|
|
|
|
|
|
Всего 2 E − 1 вариант.
Приведем ещё один пример – рис. 3.2:
Рис. 3.2. Некоторый двудольный граф
74
В графе на рис. 3.2
{{v1, v2}, {v1, v3}, {v2, v3}, {v1, v2, v3}, {v1, v3, v4, v5}}
нет трансверсали.
Здесь объединение четырёх множеств содержит только три элемента:
Е1 Е2 Е3 Е4 = {v1, v2, v3}.
Рассмотрим матрицу плоскости Фано – как матрицу смежности двудольного графа, где строки – первая доля, а столбцы – вторая:
1 |
1 |
|
0 |
1 |
0 |
0 |
0 |
1 |
0 |
|
1 |
0 |
0 |
0 |
1 |
0 |
1 |
|
0 |
0 |
0 |
1 |
1 |
|
|||||||
|
|
|
|
|
|
|
|
1 |
0 |
|
0 |
0 |
1 |
1 |
0 |
0 |
0 |
|
0 |
1 |
1 |
0 |
1 |
0 |
0 |
|
1 |
1 |
0 |
1 |
0 |
|
|||||||
0 |
1 |
|
1 |
0 |
1 |
0 |
0 |
Тогда Еj = {{1, 2, 4}, {1, 3, 7}, {2, 6, 7}, {1, 5, 6}, {4, 5, 7}, {3, 4, 6},
{2, 3, 5}}.
Получим трансверсаль T = {1, 3, 6, 5, 7, 4, 2}.
Влатинских квадратах трансверсаль одна: Т = {1, 2, 3}:
Влатинских прямоугольниках много трансверсалей {1, 2, 3}, {1, 3, 4}, {1, 3, 5}, …:
75
3.2. МНОЖЕСТВА ВНУТРЕННЕЙ И ВНЕШНЕЙ УСТОЙЧИВОСТИ ОРГРАФА
Множества внутренней устойчивости орграфа
В орграфе – ориентированном графе G = <V, Г>, где V – множество вершин, Г – множество дуг, подмножество S V называется внутренне устойчивым, если S∩ Г (S) = 0, т.е. никакие две вершины из S не смежны.
Пусть задан некоторый орграф [7] – рис. 3.3:
Рис. 3.3. Некоторый орграф
Матрица смежности этого графа имеет вид
|
1 |
2 |
3 |
4 |
5 |
1 |
|
1 |
|
|
|
2 |
|
|
1 |
1 |
|
3 |
|
|
|
|
|
4 |
|
|
|
|
|
5 |
|
|
1 |
|
|
Метод Магу нахождения максимального внутренне устойчивого множества предполагает получение по матрице смежности КНФ, описывающей условия существования такого множества, по каждой вершине, смежной другим вершинам.
Например, для заданного графа: если вершина 1 смежна вершине 2, то это условие звучит так:
Если 1, то не 2: (1 → не 2). Это эквивалентно (не 1 или не 2).
76
Если 2, то не 3 и если 2, то не 4: (2 → |
не 3) (2 → не 4). Это эк- |
|||||||||||||||
вивалентно (не 2 или не 3) (не 2 или не 4) |
|
|
|
|||||||||||||
Вершине 3 |
смежных нет – |
пропускаем её. |
||||||||||||||
Вершине 4 |
смежных нет – |
пропускаем её. |
||||||||||||||
Если 5, то не 3: (5 → не 3). Это эквивалентно (не 5 или не 3). |
||||||||||||||||
Запишем формулу |
|
|
|
|
|
|
|
|
|
|
|
|||||
|
(1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2)(2 |
3)(2 4)(5 |
3). |
Получим ДНФ, используя распределительный закон:
(2 134)(5 3)= (25 23 1345 134).
По закону поглощения получаем
(25 23 134).
Эта запись означает, что получены следующие множества:
– 1- я конъюнкция – |
не 2 |
и не 5 – |
значит, множество {1, 3, 4}, |
– 2- я конъюнкция – |
не 2 |
и не 3 – |
множество {1, 4, 5}, |
– 3- я конъюнкция – |
не 1 |
и не 3 и не 4 – множество {2, 5}. |
Множества внешней устойчивости орграфа
В ориентированном графе G = <V, Г>, где V – множество вершин, Г – множество дуг, подмножество Т V называется внешне устойчивым, если для любой вершины vi из Т T ∩ Г(vi) ≠ 0, т.е. из любой вершины, не принадлежащей Т, исходит по крайней мере одна дуга в Т.
Метод Магу нахождения минимального внешне устойчивого множества предполагает получение КНФ, описывающей условия существования такого множества, по каждой вершине, смежной другим вершинам [7].
Например, для заданного графа: вершина 1 смежна вершине 2, это условие звучит так: 1 или 2.
Вершина 2 смежна 3 и 4: (2 или 3 или 4).
77
Вершине 3 смежных нет – записываем 3. Вершине 4 смежных нет – записываем 4. Вершина 5 смежна 3: (5 или 3).
Запишем формулу
(1 2)(2 3 4) 3 4(5 3).
Упрощаем:
(1 2) 3 4= 134 234.
Таким образом, получаем два минимальных внешне устойчи-
вых множества {1, 3, 4}, {2, 3, 4}.
Задача о видеонаблюдении (К. Берж)
У Бержа вообще-то речь идёт о тюремных казематах, но нам больше нравится банковская тематика.
Имеется граф банковского хранилища с сейфами 1, 2, …, 9, соединённых коридорами – рис. 3.4 [7]. Каково минимальное количество видеокамер, которые надо установить так, чтобы они могли наблюдать за всеми сейфами?
Рис. 3.4. Задача о видеонаблюдении
78
|
|
Матрица «наблюдений» – |
матрица смежности: |
|
|
|
|
|
|
|
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
2 |
|
|
3 |
|
|
4 |
|
|
|
5 |
|
|
6 |
|
|
|
7 |
|
|
8 |
|
|
|
9 |
|
1 |
|
1 |
|
1 |
|
|
|
|
1 |
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
1 |
|
||||||
2 |
|
1 |
|
1 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
||||
3 |
|
|
|
|
1 |
|
|
1 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
4 |
|
1 |
|
|
|
|
1 |
|
1 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|||||||
5 |
|
|
|
|
|
|
|
|
|
|
1 |
|
|
1 |
|
1 |
|
|
1 |
|
1 |
|
|
|
|
|
|||||
6 |
|
1 |
|
|
|
|
|
|
|
|
|
|
1 |
|
1 |
|
1 |
|
|
|
|
|
|
|
|
||||||
7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
1 |
|
|
1 |
|
1 |
|
|
|
|
|
|||||
8 |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
1 |
|
1 |
|
1 |
|
|||||||
9 |
|
1 |
|
1 |
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
1 |
|
Задача сводится к нахождению минимального внешне устойчивого множества графа {2, 5}, что легко определяется по матрице с учётом того, что камера «видит» свой сейф.
3.3. ТРАНСПОРТНАЯ СЕТЬ И ЗАДАЧА НАХОЖДЕНИЯ МАКСИМАЛЬНОГО ПОТОКА
Пусть задана транспортная сеть: х0 – вход сети (исток), z – выход сети(сток), х1, х2, х3, х4 – промежуточныевершины– рис. 3.5 [8].
Рис. 3.5. Транспортная сеть
Цифры означают пропускную способность дуг – в числителе, поток в знаменателе. Стрелки – направление потока. Поток, входящий в вершину, равен сумме исходящих потоков. При изменении направления промежуточных дуг поток может изменяться.
79
Разрез сети – линия, разрывающая все пути от истока к стоку
(рис. 3.6).
Рис. 3.6. Разрезы транспортной сети
Очевидно, что невозможно пропустить через сеть поток, больший потока минимального разреза – рис. 3.7.
Рис. 3.7. Минимальный разрез транспортной сети
Ясно, что максимум, что можно «выжать» из сети, равно 6 единицам.
Задача о наибольшем потоке
Эта задача формулируется следующим образом: при заданной конфигурации сети и известной пропускной способности дуг необходимо найти наибольший поток и распределение его по дугам сети.
Дуга называется насыщенной, если поток в ней равен пропускной способности. Поток называется полным, если каждый путь от истока к стоку содержит по крайней мере одну насыщенную дугу.
80