Файл: С. Д. Данилова С. С. Михайлова УланУдэ 2022дискретнаяматематика.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 04.12.2023
Просмотров: 286
Скачиваний: 10
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Тема 3.4. Двудольные графы
3.4.1. Основные определения
Определение 3.68. Граф ???? = (????, ????) называется двудольным, если существует такое разбиение множества его вершин на две части (доли) V
1
, V
2
, что концы каждого ребра при- надлежат разным частям.
Пример
Дан двудольный граф (рис. 3.27):
Имеются две доли вершин:
Матрица этого двудольного графа имеет вид:
.
Определение 3.69. Если в двудольном графе ???? = (????, ????)
:
Рисунок
3.27 –
Двудольный граф
v
1
v
2
v
4
v
5
v
3
119 любые две вершины, входящие в разные доли, являются смежными, то граф называется
полным двудольным графом и обозначается ????
????,????
Пример
Графы K
1,8
и K
3,3
, изображенные на рисунке 3.28, являютсяполными двудольными гра- фами.
Рисунок 3.28 – Полные двудольные графы
3.4.2. Паросочетания в графе
Определение 3.70. Произвольное подмножество ????′ ⊆ ???? попарно несмежных ребер графа ???? = (????, ????) называется паросочетанием (или независимым множеством ребер).
Определение 3.71. Паросочетание в графе ???? называется максимальным, если оно не содержится в паросочетании с большим числом ребер.
Определение 3.72. Паросочетание в графе ???? называется наибольшим, если число ребер в нем наибольшее среди всех паросочетаний графа????.
Определение 3.72. Число ребер в наибольшем паросочетании называется числом паро-
сочетания и обозначается ????(????).
Пример
Граф K
1,8
не имеет паросочетаний, так все ребра между собой смежны.
3.4.3. Реберное покрытие графа
Определение 3.73. Реберным покрытием графа ???? называется такое подмножество ре- бер ????′′ ⊆ ???? графа ????, которое покрывает все вершины графа, другими словами, каждая вер- шина графа G инцидентна, по крайней мере, одному ребру из множества ????′′.
Пример
K
,
3 3
K
1 8
,
e
1
e
2
e
3
e
4
e
5
e
6
e
7
e
8
e
9
120
Определение 3.75. Реберное покрытие графа ???? называется минимальным, если в нем не содержится покрытий с меньшим числом ребер.
Определение 3.76. Реберное покрытие графа ???? называется наименьшим, если число ребер в нем наименьшее среди всех покрытий.
Определение 3.77. Число ребер в наименьшем реберном покрытии графа ???? называется
числом реберного покрытия и обозначается ????(????).
Пример
Определение 3.78. Паросочетание называется совершенным, если оно одновременно является реберным покрытием.
Пример
Теорема Т.Галлаи
Для любого графа ???? = (????, ????)
,
|????| = ????, без изолированных вершин верно равенство:
????
(
????
)
+
????
(
????
)
= ????.
3.4.4. Поиск наибольшего паросочетания и задача о назначениях
Поиск наибольшего паросочетания в графе представляет собой классическую алго- ритмическую задачу. Рассмотрим ее решение для двудольных графов.
Шаг 0. По матрице ????(???? × ????) двудольного графа строится рабочая таблица тех же раз- меров:
– если m
ij
= 0, то в клетку с номером (????, ????) помещается символ “×” и клетка при этом называют недопустимой;
– если же m
ij
=1, то в клетку ничего не записывается и клетку называют допустимой.
121
Слева от рабочей таблицы для удобства располагаются номера ее строк, а сверху – номера ее столбцов.
Шаг 1. При просмотре каждой строки в первую допустимую клетку строки ставится символ “1”. Если в очередной строке найдена первая допустимая клетка, при этом в соот- ветствующем ей столбце уже есть символ “1”, то эта клетка игнорируется.
Фиксируем набор ребер в графе, соответствующих проставленным в таблице симво- лам “1”, который представляет собой максимальное паросочетание.
Если в результате всех действий этого шага в каждой строке рабочей таблицы ока- жется символ “1”, то ребра указанного паросочетания составляют наибольшее паросочета- ние, и действия окончены.
Если же остались строки без “1”, то они помечаются справа от таблицы символом “–“, и осуществляется переход к следующему шагу.
Шаг 2. Производится просмотр каждой помеченной строки: в строке отыскиваются допустимые клетки, и столбцы, в которых эти клетки расположены, помечаются снизу но- мером просматриваемой строки. При этом соблюдается принцип (℘): если пометка уже
стоит, то на ее место вторая не ставится.
Если в результате этого шага ни один из столбцов не будет помечен, то это означает, что паросочетание, полученное на Шаге 1, является наибольшим и все действия прекраща- ются.
Шаг 2. Производится просмотр каждого помеченного столбца: в столбце отыскива- ется символ “1”, и строка, в которой он расположен, помечается номером просматриваемого столбца справа от таблицы. Соблюдается принцип (℘).
Если в результате действий этого шага будут просмотрены все помеченные ранее столбцы и, тем самым, возникнет набор помеченных строк символом “–“ или номерами столбцов, то следует вернуться к Шагу 2 и повторить предусмотренные им действия.
Шаг 3. Рассматривается столбец, имеющий пометку и не содержащий символа “1”. В этот столбец ставится символ “1” в строку, номер которой равен пометке этого столбца.
Затем в этой строке ищется «старый» символ “1”, который перемещается по его столбцу в строку, номер которой равен пометке при этом столбце. И так далее. В конце концов оче- редной перемещаемый «старый» символ “1” окажется в строке, где больше символов «1» нет. Возникает новый набор символов “1”, в котором уже элементов на один больше, чем в исходном наборе символов “1”. По этому новому набору можно построить паросочетание так же, как это делалось в самом начале, и после этого повторить все сначала.
В конце концов возникнет одно из указанных выше условий прекращения действий по алгоритму, и наибольшее паросочетание будет найдено.
Пример
122
Рассмотрим задачу о назначении на узкие места, которая решается описанным выше алгоритмом. Вот ее постановка.
Имеется n рабочих мест p
1
,, p
n
на некотором конвейере и
n рабочих w
1
,,w
n
, кото- рых нужно на эти рабочие места расставить; известна производительность C
ij
рабочего w
i
на рабочем месте p
j
. Тот факт, что при некотором распределении на рабочие места рабочий
w
k
попадает на рабочее место p
i
k
можно описать следующей таблицей:
Имея способ s назначения на рабочие места, можно найти конкретную для этого спо- соба минимальную производительность C
ki
k
и заметить, что именно эта минимальная про- изводительность и определяет скорость и производительность конвейера. То рабочее место, на котором реализуется минимальная производительность, и называют узким местом в назначении.
Приведем алгоритм решения задачи о назначении на узкие места.
Шаг 0. Фиксируем матрицу производительностей C = (C
ij
) и любое назначение на ра- бочие места. Например, рабочий w
i
назначается на рабочее место p
i
, i = 1,, n. Пусть
s – минимальная производительность при этом назначении. Построим рабочую таблицу тех же размеров, что и матрица C; в клетку с номером (i, j)
в этой таблице проставим символ “×”, если C
ij
≤
s; в противном случае эту клетку оставим пустой.
Шаг 1. Рассматривая рабочую таблицу, построенную на предыдущем шаге, как рабо- чую таблицу в алгоритме для выбора наибольшего паросочетания в двудольном графе, найдем соответствующее наибольшее паросочетание. Если в нем окажется n ребер, то по ним восстанавливается новое назначение на рабочие места и с новой, более высокой, мини- мальной производительностью. Обозначим ее снова через s и вернемся к шагу 0. Если же число ребер окажется меньше n, то имеющееся назначение на рабочие места уже опти- мально.
Контрольные вопросы
1. Какой граф называется двудольным, что такое полный двудольный граф?
2. Какое машинное представление имеет двудольный граф?
3. Что такое полный двудольный граф, и как он обозначается?
4. Что называется паросочетанием в графе?
5. Чем отличается максимальное паросочетание от наибольшего паросочетания?
6. Что характеризует число паросочетания?
7. Что называется реберным покрытием графа?
123 8. Чем отличается минимальное покрытие от наименьшего покрытия?
9. Что характеризует число реберного покрытия?
10. Что такое совершенное паросочетание?
11. Как используется алгоритм поиска наибольшего паросочетания в задаче о назна- чениях?
124
ПРАКТИКУМ
1. Множества, отношения, функции
1.1. Доказательство теоретико-множественных соотношений
Методические указания к выполнению задания
Задание. Доказать теоретико-множественные соотношения.
При выполнении задания необходимо пользоваться следующим рекомендациями:
1. При доказательстве включения
???? ???? использовать следующую схему доказатель- ства:
«Пусть ???? ∈ ????, тогда ..., значит ???? ∈ ????. Следовательно, ???? ????.»
либо использовать элементарные соотношения типа:
(1)
???? ∩ ???? ????, ???? ∩ ???? ????
(2)
???? ???? ∪ ????, ???? ???? ∪ ????
(3)
???? \ ????
(4)
???? ???? и ???? ???? ???? ???? и т.д.
2. При доказательстве равенства двух множеств нужно проверять два включения по определению равенства множеств.
3. Правильно пользоваться отрицанием условий:
????
∪ ???? и ???? ????
????
∩ ???? или ???? ????
????
\ ???? ???? или ???? ∈ ????
Примеры выполнения задания:
Пример 1. Доказать равенство множеств: ???? ∪ ???? = ???? ∪ (????\????).
Решение.
Докажем, что ???? ∪ ???? ???? ∪ (????\????).
Пусть ???? ∈ ???? ∪ ????, тогда ???? ∈ ???? или ???? ∈ ????.
Если ???? ∈ ????, то по формуле (2) ???? ∈ ∪ (????\????).
Если ???? ???? и ???? ∈ ????, то по определению разности множеств ???? ∈ ????\????. По формуле (2)
???? ∈ ∪ (????\????).
Докажем, что ???? ∪ (????\????) ???? ∪ ????.
Пусть ???? ∈ ???? ∪ (????\????), тогда ???? ∈ ???? или ???? ∈ ????\????.
Если ???? ∈ ????, то по формуле (2) ???? ∈ ???? ∪ ????.
125
Если ???? ∈ ????\????, то по определению разности множеств ???? ∈ ???? и ???? ????. Так как ???? ∈ ???? , то по формуле (2) ???? ∈ ???? ∪ ????.
Пример 2. Доказать: ???? ???? ∩ ???? ???? ???? и ???? ????.
Решение.
Докажем, что ???? ???? ∩ ???? ???? ???? и ???? ????.
Способ 1.
Чтобы доказать, что ???? ???? и ???? ????, возьмем ???? ∈ ????. Так как ???? ???? ∩ ????, то из ???? ∈ ????сле- дует, что???? ∈ ???? и???? ∈ ????. Значит, одновременно выполняются (???? ∈ ????и???? ∈ ????)и (???? ∈ ???? и???? ∈
????). Поэтому ???? ???? и ???? ????.
Способ 2.
Учитывая соотношение (1) имеем ???? ???? ∩ ???? ???? и ???? ???? ∩ ???? C. Отсюда по транзи- тивности получаем ???? ???? и ???? ????.
Докажем, что ???? ???? и ???? ???? ???? ???? ∩ ????.
Чтобы доказать, что ???? ???? ∩ ????, возьмем ???? ∈ ????. Так как???? ????и???? ????, то из ???? ∈ ????сле- дует, что???? ∈ ???? и???? ∈ ????. По определению пересечения множеств получаем, что???? ∈ ???? ∩ ????.
Варианты индивидуальных заданий:
№
Соотношение
№
Соотношение
1
????−̇???? = ???? = ????
16
????\???? = ????−̇(???? ∩ ????)
2
???? ∩ ???? ???? ???? ???? ∪ ????
17
???? ∪ ???? = (????−̇????) ∪ (???? ∩ ????)
3
???? ∩ ???? = ???? ∪ ???? = ????−̇????
18
????−̇(????−̇????) = ????
4
???? ∪ ???? = ????−̇????−̇(???? ∩ ????)
19
(????−̇????)−̇???? = ????−̇(????−̇????)
5
???? ∪ ???? = ???? ∩ ???? ???? = ????
20
???? = ???? ???? ∩ ???? = и ???? ∪ ???? = ????
6
????\(???? ∩ ????) = (????\????) ∪ (????\????)
21
????\(???? ∪ ????) = (????\????) ∩ (????\????)
7
(???? ∪ ????) ∩ (???? ∪ ????) = ????
22
???? ∪ ???? = ???? ∪ (????\????)
8
(???? ∩ ????) ∪ (???? ∩ ????) = ????
23
(????\????)\???? = (????\????)\(????\????)
9
???? ∩ (????\????) = (???? ∩ ????)\????
24
(???? ∩ ????)\(???? ∩ ????) = (???? ∩ ????)\????
10
???? ∩ (????\????) = (???? ∩ ????)\(???? ∩ ????)
25
????\(????\????) = (???? ∩ ????)
11
(???? ∪ ????) ∩ ???? = ???? ∩ ????
26
????\???? = ????\(???? ∩ ????)
12
???? ???? ???? ????
27
???? ???? ∩ ???? ???? ???? и ???? ????
13
???? ∪ ???? ???? ???? ???? и ???? ????
28
????\(???? ∪ ????) = (????\????)\????
14
???? ???? ∪ ???? ???? ∩ ???? ????
29
????\(????\????) = (????\????) ∪ (???? ∩ ????)
15
???? ???? ????\???? ????\????
30
(???? ∪ ????)\???? = (????\????) ∪ (????\????)
126
1.2.
Нахождение областей определения, значений,
обратного отношения, композиции отношений
Методические указания к выполнению задания
Задание. Для бинарного отношения P на множестве действительных чисел????найти
1 1
1
,
,
,
,
,
P
P
P
P
P P P
P P
−
−
−
При выполнении задания необходимо пользоваться следующими определениями:
1. Областью определения
????
????
бинарного отношения
???? называется множество значе- ний ????, таких, что пара (????, ????) ∈ ????:
(
)
, такое, что
,
R
x
y
x y
R
=
2. Областью значений
????
????
бинарного отношения
???? называется множество значений ????, таких, что пара (????, ????) ∈ ????:
(
)
, такое, что
,
R
y
x
x y
R
=
3. Обратным отношением
????
−1
для отношения
???? называется множество:
(
) (
)
1
,
,
R
x y
y x
R
−
=
4. Композицией бинарных отношений
????
1
и
????
2
называется отношение:
(
)
( )
(
)
1 2
1 2
,
, такое, что
,
и ,
R
R
x y
z
x z
R
z y
R
=
Пример выполнения задания:
Дано отношение ???? = {(????, ????)|3???????? < 17, ????, ???? ∈ ????}.
Найти ????
????
,
????
????
,
????
−1
,
????
−1
°????, ????°????
−1
,
????°????.
Решение
По определению область определения бинарного отношения – это множество таких
????, для которых (????, ????) ∈ ???? хотя бы для одного ????. В данном примере для ∀???? мы найдем ???? так, чтобы выполнялось отношение 3???????? < 17 на множестве????. Поэтому:
????
????
= ????.
По определению область значений – это множество таких ????, для которых (????, ????) ∈ ???? хотя бы для одного ????. В данном примере для ∀???? мы найдем ???? так, чтобы выполнялось от- ношение 3???????? < 17 на множестве ????. Поэтому:
????
????
= ????.
По определению обратного отношения ????
−1
= ????, так как при перестановке перемен- ных ???? и ???? в соотношении 3???????? < 17 суть отношения не меняется. Из этого также следует, что:
????
−1
°???? = ????°????
−1
= ????°????.
127
Найдем композицию отношений ????°????. По определению композиции существует ????, такое что (????, ????) ∈ ???? и (????, ????) ∈ ????. Получаем систему неравенств:
{
3???????? < 17 3???????? < 17
Решение этой системы дает нам следующее неравенство:
????
????
< 1.
Таким образом: ????
−1
°???? = ????°????
−1
= ????°???? = {(????, ????)|
????
????
< 1, ????, ???? ∈ ????}.
Варианты индивидуальных заданий:
№
Отношение
№
Отношение
1
???? = {(????, ????)|???? + ???? ≤ 0, ????, ???? ∈ ????}
16
???? = {(????, ????)|????
2
> ????
2
, ????, ???? ∈ ????}
2
???? = {(????, ????)|???? + ???? > 0, ????, ???? ∈ ????}
17
???? = {(????, ????)|????
2
+ ???? > 0, ????, ???? ∈ ????}
3
???? = {(????, ????)|3???? − 5???? < 0, ????, ???? ∈ ????}
18
???? = {(????, ????)|???????? > −5, ????, ???? ∈ ????}
4
???? = {(????, ????)|???????? > 15, ????, ???? ∈ ????}
19
???? = {(????, ????)|????
2
− ???? > 0, ????, ???? ∈ ????}
5
???? = {(????, ????)|2???? − 3???? > 0, ????, ???? ∈ ????}
20
???? = {(????, ????)|7???? − 4???? ≥ 0, ????, ???? ∈ ????}
6
???? = {(????, ????)|???????? < 20, ????, ???? ∈ ????}
21
???? = {(????, ????)|???? + ???? ≥ 2, ????, ???? ∈ ????}
7
???? = {(????, ????)|???? − ???? > 3, ????, ???? ∈ ????}
22
???? = {(????, ????)|????
2
+ ????
2
< 0, ????, ???? ∈ ????}
8
???? = {(????, ????)|????
2
− ???? < 0, ????, ???? ∈ ????}
23
???? = {(????, ????)|????
2
+ ???? < 0, ????, ???? ∈ ????}
9
???? = {(????, ????)|2???? + 5???? ≥ 0, ????, ???? ∈ ????}
24
???? = {(????, ????)|7???? + 3???? < 2, ????, ???? ∈ ????}
10
???? = {(????, ????)|???? − ???? < 0, ????, ???? ∈ ????}
25
???? = {(????, ????)|3???? + 8???? ≥ 2, ????, ???? ∈ ????}
11
???? = {(????, ????)|9???? − 5???? ≤ 2, ????, ???? ∈ ????}
26
???? = {(????, ????)|6???? − 7???? ≥ 0, ????, ???? ∈ ????}
12
???? = {(????, ????)|???? + ???? < 7, ????, ???? ∈ ????}
27
???? = {(????, ????)|????
2
> ???? + 2, ????, ???? ∈ ????}
13
???? = {(????, ????)|???? − ???? ≤ 9, ????, ???? ∈ ????}
28
???? = {(????, ????)||????| < ????, ????, ???? ∈ ????}
14
???? = {(????, ????)|???? − ???? ≥ 0, ????, ???? ∈ ????}
29
???? = {(????, ????)||????| > ????, ????, ???? ∈ ????}
15
???? = {(????, ????)|5???? − ???? > 7, ????, ???? ∈ ????}
30
???? = {(????, ????)|???? + 2???? < −6, ????, ???? ∈ ????}
1.3. Исследование бинарного отношения на свойства
Методические указания к выполнению задания
Задание. Исследовать бинарное отношение ???? ????
2
на свойства рефлексивности, ан- тирефлексивности, симметричности, антисимметричности, транзитивности. Выяснить, яв- ляется ли оно отношением строгого порядка, нестрогого порядка, эквивалентности.
При выполнении задания необходимо пользоваться следующим понятиями:
1. Бинарное отношение
???? на множестве ???? называется:
1) рефлексивным, если для
∀???? ∈ ???? (????, ????) ∈ ????;
2) антирефлексивным, если: для
∀???? ∈ ???? (????, ????)????;
3.4.1. Основные определения
Определение 3.68. Граф ???? = (????, ????) называется двудольным, если существует такое разбиение множества его вершин на две части (доли) V
1
, V
2
, что концы каждого ребра при- надлежат разным частям.
Пример
Дан двудольный граф (рис. 3.27):
Имеются две доли вершин:
Матрица этого двудольного графа имеет вид:
.
Определение 3.69. Если в двудольном графе ???? = (????, ????)
:
Рисунок
3.27 –
Двудольный граф
v
1
v
2
v
4
v
5
v
3
119 любые две вершины, входящие в разные доли, являются смежными, то граф называется
полным двудольным графом и обозначается ????
????,????
Пример
Графы K
1,8
и K
3,3
, изображенные на рисунке 3.28, являютсяполными двудольными гра- фами.
Рисунок 3.28 – Полные двудольные графы
3.4.2. Паросочетания в графе
Определение 3.70. Произвольное подмножество ????′ ⊆ ???? попарно несмежных ребер графа ???? = (????, ????) называется паросочетанием (или независимым множеством ребер).
Определение 3.71. Паросочетание в графе ???? называется максимальным, если оно не содержится в паросочетании с большим числом ребер.
Определение 3.72. Паросочетание в графе ???? называется наибольшим, если число ребер в нем наибольшее среди всех паросочетаний графа????.
Определение 3.72. Число ребер в наибольшем паросочетании называется числом паро-
сочетания и обозначается ????(????).
Пример
Граф K
1,8
не имеет паросочетаний, так все ребра между собой смежны.
3.4.3. Реберное покрытие графа
Определение 3.73. Реберным покрытием графа ???? называется такое подмножество ре- бер ????′′ ⊆ ???? графа ????, которое покрывает все вершины графа, другими словами, каждая вер- шина графа G инцидентна, по крайней мере, одному ребру из множества ????′′.
Пример
K
,
3 3
K
1 8
,
e
1
e
2
e
3
e
4
e
5
e
6
e
7
e
8
e
9
120
Определение 3.75. Реберное покрытие графа ???? называется минимальным, если в нем не содержится покрытий с меньшим числом ребер.
Определение 3.76. Реберное покрытие графа ???? называется наименьшим, если число ребер в нем наименьшее среди всех покрытий.
Определение 3.77. Число ребер в наименьшем реберном покрытии графа ???? называется
числом реберного покрытия и обозначается ????(????).
Пример
Определение 3.78. Паросочетание называется совершенным, если оно одновременно является реберным покрытием.
Пример
Теорема Т.Галлаи
Для любого графа ???? = (????, ????)
,
|????| = ????, без изолированных вершин верно равенство:
????
(
????
)
+
????
(
????
)
= ????.
3.4.4. Поиск наибольшего паросочетания и задача о назначениях
Поиск наибольшего паросочетания в графе представляет собой классическую алго- ритмическую задачу. Рассмотрим ее решение для двудольных графов.
Шаг 0. По матрице ????(???? × ????) двудольного графа строится рабочая таблица тех же раз- меров:
– если m
ij
= 0, то в клетку с номером (????, ????) помещается символ “×” и клетка при этом называют недопустимой;
– если же m
ij
=1, то в клетку ничего не записывается и клетку называют допустимой.
121
Слева от рабочей таблицы для удобства располагаются номера ее строк, а сверху – номера ее столбцов.
Шаг 1. При просмотре каждой строки в первую допустимую клетку строки ставится символ “1”. Если в очередной строке найдена первая допустимая клетка, при этом в соот- ветствующем ей столбце уже есть символ “1”, то эта клетка игнорируется.
Фиксируем набор ребер в графе, соответствующих проставленным в таблице симво- лам “1”, который представляет собой максимальное паросочетание.
Если в результате всех действий этого шага в каждой строке рабочей таблицы ока- жется символ “1”, то ребра указанного паросочетания составляют наибольшее паросочета- ние, и действия окончены.
Если же остались строки без “1”, то они помечаются справа от таблицы символом “–“, и осуществляется переход к следующему шагу.
Шаг 2. Производится просмотр каждой помеченной строки: в строке отыскиваются допустимые клетки, и столбцы, в которых эти клетки расположены, помечаются снизу но- мером просматриваемой строки. При этом соблюдается принцип (℘): если пометка уже
стоит, то на ее место вторая не ставится.
Если в результате этого шага ни один из столбцов не будет помечен, то это означает, что паросочетание, полученное на Шаге 1, является наибольшим и все действия прекраща- ются.
Шаг 2. Производится просмотр каждого помеченного столбца: в столбце отыскива- ется символ “1”, и строка, в которой он расположен, помечается номером просматриваемого столбца справа от таблицы. Соблюдается принцип (℘).
Если в результате действий этого шага будут просмотрены все помеченные ранее столбцы и, тем самым, возникнет набор помеченных строк символом “–“ или номерами столбцов, то следует вернуться к Шагу 2 и повторить предусмотренные им действия.
Шаг 3. Рассматривается столбец, имеющий пометку и не содержащий символа “1”. В этот столбец ставится символ “1” в строку, номер которой равен пометке этого столбца.
Затем в этой строке ищется «старый» символ “1”, который перемещается по его столбцу в строку, номер которой равен пометке при этом столбце. И так далее. В конце концов оче- редной перемещаемый «старый» символ “1” окажется в строке, где больше символов «1» нет. Возникает новый набор символов “1”, в котором уже элементов на один больше, чем в исходном наборе символов “1”. По этому новому набору можно построить паросочетание так же, как это делалось в самом начале, и после этого повторить все сначала.
В конце концов возникнет одно из указанных выше условий прекращения действий по алгоритму, и наибольшее паросочетание будет найдено.
Пример
122
Рассмотрим задачу о назначении на узкие места, которая решается описанным выше алгоритмом. Вот ее постановка.
Имеется n рабочих мест p
1
,, p
n
на некотором конвейере и
n рабочих w
1
,,w
n
, кото- рых нужно на эти рабочие места расставить; известна производительность C
ij
рабочего w
i
на рабочем месте p
j
. Тот факт, что при некотором распределении на рабочие места рабочий
w
k
попадает на рабочее место p
i
k
можно описать следующей таблицей:
Имея способ s назначения на рабочие места, можно найти конкретную для этого спо- соба минимальную производительность C
ki
k
и заметить, что именно эта минимальная про- изводительность и определяет скорость и производительность конвейера. То рабочее место, на котором реализуется минимальная производительность, и называют узким местом в назначении.
Приведем алгоритм решения задачи о назначении на узкие места.
Шаг 0. Фиксируем матрицу производительностей C = (C
ij
) и любое назначение на ра- бочие места. Например, рабочий w
i
назначается на рабочее место p
i
, i = 1,, n. Пусть
s – минимальная производительность при этом назначении. Построим рабочую таблицу тех же размеров, что и матрица C; в клетку с номером (i, j)
в этой таблице проставим символ “×”, если C
ij
≤
s; в противном случае эту клетку оставим пустой.
Шаг 1. Рассматривая рабочую таблицу, построенную на предыдущем шаге, как рабо- чую таблицу в алгоритме для выбора наибольшего паросочетания в двудольном графе, найдем соответствующее наибольшее паросочетание. Если в нем окажется n ребер, то по ним восстанавливается новое назначение на рабочие места и с новой, более высокой, мини- мальной производительностью. Обозначим ее снова через s и вернемся к шагу 0. Если же число ребер окажется меньше n, то имеющееся назначение на рабочие места уже опти- мально.
Контрольные вопросы
1. Какой граф называется двудольным, что такое полный двудольный граф?
2. Какое машинное представление имеет двудольный граф?
3. Что такое полный двудольный граф, и как он обозначается?
4. Что называется паросочетанием в графе?
5. Чем отличается максимальное паросочетание от наибольшего паросочетания?
6. Что характеризует число паросочетания?
7. Что называется реберным покрытием графа?
123 8. Чем отличается минимальное покрытие от наименьшего покрытия?
9. Что характеризует число реберного покрытия?
10. Что такое совершенное паросочетание?
11. Как используется алгоритм поиска наибольшего паросочетания в задаче о назна- чениях?
124
ПРАКТИКУМ
1. Множества, отношения, функции
1.1. Доказательство теоретико-множественных соотношений
Методические указания к выполнению задания
Задание. Доказать теоретико-множественные соотношения.
При выполнении задания необходимо пользоваться следующим рекомендациями:
1. При доказательстве включения
???? ???? использовать следующую схему доказатель- ства:
«Пусть ???? ∈ ????, тогда ..., значит ???? ∈ ????. Следовательно, ???? ????.»
либо использовать элементарные соотношения типа:
(1)
???? ∩ ???? ????, ???? ∩ ???? ????
(2)
???? ???? ∪ ????, ???? ???? ∪ ????
(3)
???? \ ????
(4)
???? ???? и ???? ???? ???? ???? и т.д.
2. При доказательстве равенства двух множеств нужно проверять два включения по определению равенства множеств.
3. Правильно пользоваться отрицанием условий:
????
∪ ???? и ???? ????
????
∩ ???? или ???? ????
????
\ ???? ???? или ???? ∈ ????
Примеры выполнения задания:
Пример 1. Доказать равенство множеств: ???? ∪ ???? = ???? ∪ (????\????).
Решение.
Докажем, что ???? ∪ ???? ???? ∪ (????\????).
Пусть ???? ∈ ???? ∪ ????, тогда ???? ∈ ???? или ???? ∈ ????.
Если ???? ∈ ????, то по формуле (2) ???? ∈ ∪ (????\????).
Если ???? ???? и ???? ∈ ????, то по определению разности множеств ???? ∈ ????\????. По формуле (2)
???? ∈ ∪ (????\????).
Докажем, что ???? ∪ (????\????) ???? ∪ ????.
Пусть ???? ∈ ???? ∪ (????\????), тогда ???? ∈ ???? или ???? ∈ ????\????.
Если ???? ∈ ????, то по формуле (2) ???? ∈ ???? ∪ ????.
125
Если ???? ∈ ????\????, то по определению разности множеств ???? ∈ ???? и ???? ????. Так как ???? ∈ ???? , то по формуле (2) ???? ∈ ???? ∪ ????.
Пример 2. Доказать: ???? ???? ∩ ???? ???? ???? и ???? ????.
Решение.
Докажем, что ???? ???? ∩ ???? ???? ???? и ???? ????.
Способ 1.
Чтобы доказать, что ???? ???? и ???? ????, возьмем ???? ∈ ????. Так как ???? ???? ∩ ????, то из ???? ∈ ????сле- дует, что???? ∈ ???? и???? ∈ ????. Значит, одновременно выполняются (???? ∈ ????и???? ∈ ????)и (???? ∈ ???? и???? ∈
????). Поэтому ???? ???? и ???? ????.
Способ 2.
Учитывая соотношение (1) имеем ???? ???? ∩ ???? ???? и ???? ???? ∩ ???? C. Отсюда по транзи- тивности получаем ???? ???? и ???? ????.
Докажем, что ???? ???? и ???? ???? ???? ???? ∩ ????.
Чтобы доказать, что ???? ???? ∩ ????, возьмем ???? ∈ ????. Так как???? ????и???? ????, то из ???? ∈ ????сле- дует, что???? ∈ ???? и???? ∈ ????. По определению пересечения множеств получаем, что???? ∈ ???? ∩ ????.
Варианты индивидуальных заданий:
№
Соотношение
№
Соотношение
1
????−̇???? = ???? = ????
16
????\???? = ????−̇(???? ∩ ????)
2
???? ∩ ???? ???? ???? ???? ∪ ????
17
???? ∪ ???? = (????−̇????) ∪ (???? ∩ ????)
3
???? ∩ ???? = ???? ∪ ???? = ????−̇????
18
????−̇(????−̇????) = ????
4
???? ∪ ???? = ????−̇????−̇(???? ∩ ????)
19
(????−̇????)−̇???? = ????−̇(????−̇????)
5
???? ∪ ???? = ???? ∩ ???? ???? = ????
20
???? = ???? ???? ∩ ???? = и ???? ∪ ???? = ????
6
????\(???? ∩ ????) = (????\????) ∪ (????\????)
21
????\(???? ∪ ????) = (????\????) ∩ (????\????)
7
(???? ∪ ????) ∩ (???? ∪ ????) = ????
22
???? ∪ ???? = ???? ∪ (????\????)
8
(???? ∩ ????) ∪ (???? ∩ ????) = ????
23
(????\????)\???? = (????\????)\(????\????)
9
???? ∩ (????\????) = (???? ∩ ????)\????
24
(???? ∩ ????)\(???? ∩ ????) = (???? ∩ ????)\????
10
???? ∩ (????\????) = (???? ∩ ????)\(???? ∩ ????)
25
????\(????\????) = (???? ∩ ????)
11
(???? ∪ ????) ∩ ???? = ???? ∩ ????
26
????\???? = ????\(???? ∩ ????)
12
???? ???? ???? ????
27
???? ???? ∩ ???? ???? ???? и ???? ????
13
???? ∪ ???? ???? ???? ???? и ???? ????
28
????\(???? ∪ ????) = (????\????)\????
14
???? ???? ∪ ???? ???? ∩ ???? ????
29
????\(????\????) = (????\????) ∪ (???? ∩ ????)
15
???? ???? ????\???? ????\????
30
(???? ∪ ????)\???? = (????\????) ∪ (????\????)
126
1.2.
Нахождение областей определения, значений,
обратного отношения, композиции отношений
Методические указания к выполнению задания
Задание. Для бинарного отношения P на множестве действительных чисел????найти
1 1
1
,
,
,
,
,
P
P
P
P
P P P
P P
−
−
−
При выполнении задания необходимо пользоваться следующими определениями:
1. Областью определения
????
????
бинарного отношения
???? называется множество значе- ний ????, таких, что пара (????, ????) ∈ ????:
(
)
, такое, что
,
R
x
y
x y
R
=
2. Областью значений
????
????
бинарного отношения
???? называется множество значений ????, таких, что пара (????, ????) ∈ ????:
(
)
, такое, что
,
R
y
x
x y
R
=
3. Обратным отношением
????
−1
для отношения
???? называется множество:
(
) (
)
1
,
,
R
x y
y x
R
−
=
4. Композицией бинарных отношений
????
1
и
????
2
называется отношение:
(
)
( )
(
)
1 2
1 2
,
, такое, что
,
и ,
R
R
x y
z
x z
R
z y
R
=
Пример выполнения задания:
Дано отношение ???? = {(????, ????)|3???????? < 17, ????, ???? ∈ ????}.
Найти ????
????
,
????
????
,
????
−1
,
????
−1
°????, ????°????
−1
,
????°????.
Решение
По определению область определения бинарного отношения – это множество таких
????, для которых (????, ????) ∈ ???? хотя бы для одного ????. В данном примере для ∀???? мы найдем ???? так, чтобы выполнялось отношение 3???????? < 17 на множестве????. Поэтому:
????
????
= ????.
По определению область значений – это множество таких ????, для которых (????, ????) ∈ ???? хотя бы для одного ????. В данном примере для ∀???? мы найдем ???? так, чтобы выполнялось от- ношение 3???????? < 17 на множестве ????. Поэтому:
????
????
= ????.
По определению обратного отношения ????
−1
= ????, так как при перестановке перемен- ных ???? и ???? в соотношении 3???????? < 17 суть отношения не меняется. Из этого также следует, что:
????
−1
°???? = ????°????
−1
= ????°????.
127
Найдем композицию отношений ????°????. По определению композиции существует ????, такое что (????, ????) ∈ ???? и (????, ????) ∈ ????. Получаем систему неравенств:
{
3???????? < 17 3???????? < 17
Решение этой системы дает нам следующее неравенство:
????
????
< 1.
Таким образом: ????
−1
°???? = ????°????
−1
= ????°???? = {(????, ????)|
????
????
< 1, ????, ???? ∈ ????}.
Варианты индивидуальных заданий:
№
Отношение
№
Отношение
1
???? = {(????, ????)|???? + ???? ≤ 0, ????, ???? ∈ ????}
16
???? = {(????, ????)|????
2
> ????
2
, ????, ???? ∈ ????}
2
???? = {(????, ????)|???? + ???? > 0, ????, ???? ∈ ????}
17
???? = {(????, ????)|????
2
+ ???? > 0, ????, ???? ∈ ????}
3
???? = {(????, ????)|3???? − 5???? < 0, ????, ???? ∈ ????}
18
???? = {(????, ????)|???????? > −5, ????, ???? ∈ ????}
4
???? = {(????, ????)|???????? > 15, ????, ???? ∈ ????}
19
???? = {(????, ????)|????
2
− ???? > 0, ????, ???? ∈ ????}
5
???? = {(????, ????)|2???? − 3???? > 0, ????, ???? ∈ ????}
20
???? = {(????, ????)|7???? − 4???? ≥ 0, ????, ???? ∈ ????}
6
???? = {(????, ????)|???????? < 20, ????, ???? ∈ ????}
21
???? = {(????, ????)|???? + ???? ≥ 2, ????, ???? ∈ ????}
7
???? = {(????, ????)|???? − ???? > 3, ????, ???? ∈ ????}
22
???? = {(????, ????)|????
2
+ ????
2
< 0, ????, ???? ∈ ????}
8
???? = {(????, ????)|????
2
− ???? < 0, ????, ???? ∈ ????}
23
???? = {(????, ????)|????
2
+ ???? < 0, ????, ???? ∈ ????}
9
???? = {(????, ????)|2???? + 5???? ≥ 0, ????, ???? ∈ ????}
24
???? = {(????, ????)|7???? + 3???? < 2, ????, ???? ∈ ????}
10
???? = {(????, ????)|???? − ???? < 0, ????, ???? ∈ ????}
25
???? = {(????, ????)|3???? + 8???? ≥ 2, ????, ???? ∈ ????}
11
???? = {(????, ????)|9???? − 5???? ≤ 2, ????, ???? ∈ ????}
26
???? = {(????, ????)|6???? − 7???? ≥ 0, ????, ???? ∈ ????}
12
???? = {(????, ????)|???? + ???? < 7, ????, ???? ∈ ????}
27
???? = {(????, ????)|????
2
> ???? + 2, ????, ???? ∈ ????}
13
???? = {(????, ????)|???? − ???? ≤ 9, ????, ???? ∈ ????}
28
???? = {(????, ????)||????| < ????, ????, ???? ∈ ????}
14
???? = {(????, ????)|???? − ???? ≥ 0, ????, ???? ∈ ????}
29
???? = {(????, ????)||????| > ????, ????, ???? ∈ ????}
15
???? = {(????, ????)|5???? − ???? > 7, ????, ???? ∈ ????}
30
???? = {(????, ????)|???? + 2???? < −6, ????, ???? ∈ ????}
1.3. Исследование бинарного отношения на свойства
Методические указания к выполнению задания
Задание. Исследовать бинарное отношение ???? ????
2
на свойства рефлексивности, ан- тирефлексивности, симметричности, антисимметричности, транзитивности. Выяснить, яв- ляется ли оно отношением строгого порядка, нестрогого порядка, эквивалентности.
При выполнении задания необходимо пользоваться следующим понятиями:
1. Бинарное отношение
???? на множестве ???? называется:
1) рефлексивным, если для
∀???? ∈ ???? (????, ????) ∈ ????;
2) антирефлексивным, если: для
∀???? ∈ ???? (????, ????)????;