Тема 7. Розрізи графів
Перерізом (розрізом) s графа G називається певна підмножина дуг, видалення якої збільшує кількість компонент зв’язності.
Підмножини вершин, що не перетинаються, утворюють розбиття множини усіх вершин графа G. Для перерізу довільно вводиться орієнтація – напрямок від одного боку перерізу до іншого.
Матриця S, рядки якої утворюють максимальний лінійно-незалежний набір вектор-перерізів, називається матрицею перерізів графа G. Стовпчики матриць перерізів i циклів нумеруються однаково – дугами графа, а кількість їх рядків у загальному випадку різна.
Навчитися знаходити розрізи графів, ранг розрізів та будувати базис розрізів [1, c. 286-292; 2, c. 286-292].
Тема 8. Комбінаторика
Розбиттям
числа
називається його подання у вигляді
(5.1), коли порядок додатків
не враховується.
де
(5.1)
Підрахунок
кількості розбиттів еквівалентний
завданню про кількість розподілу
однакових предметів за однаковими
непорожніми комірками. Додатки
у розбиттях називаються частинами;
кількість входжень кожної частини до
суми (5.1) називається її
кратністю. Розбиття
числа
на
додатків
можна розглядати як
-сполучення
(з повтореннями) цих чисел, що задовольнить
умові (5.1). Інколи для пошуку композицій
числа
(або обчислення їхньої кількості) зручно
вирішити цю саму задачу для його
розбиттів, а після цього перейти до
композицій.
Нехай дана деяка послідовність чисел а0, а1, а2, …, аn, .... Якщо степеневий ряд (а0 + а1х + а2х2 + ... + аnхn + ...) збігається при деяких х до функції f(x), то f(x) називається продуктивною функцією для послідовності а0, а1, а2, …, аn, ... . Операціям над продуктивними функціями відповідають певні операції над відповідними послідовностями.
Розглянути додаткові розділи комбінаторики та навчитися використовувати їх на практиці [1, с. 438-453; 2, c. 437-453; 10, c. 90-121, с. 192-296, с. 212-216; 12, c. 28-30].
6 Індивідуальні контрольні завдання
Завдання 1. Задана універсальна множина U та чотири її підмножини A, B, C, D.
U = {1, 2, 3, ... , 60};
A = {a U ¦ a=p*i};
B = {b U ¦ b=q*i};
C = {c U ¦ c=r*i};
D = {d U ¦ d=s*i};
i=1,2,3,...n .
Значення p, q, r, s за варіантами наведені у табл. 6.1.
Вказати за допомогою кругів Ейлера відношення між множинами U, A, B, C, D.
Таблиця 6.1
Параметр |
Варіанти |
|||||||||
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
p |
2 |
3 |
1 |
4 |
2 |
4 |
3 |
2 |
5 |
4 |
q |
3 |
6 |
2 |
2 |
4 |
8 |
2 |
3 |
3 |
6 |
r |
5 |
4 |
3 |
6 |
3 |
5 |
6 |
7 |
5 |
2 |
s |
6 |
9 |
4 |
3 |
6 |
3 |
6 |
8 |
9 |
3 |
Знайти потужність множин F1, , F10.
;
;
;
;
;
;
;
;
;
.
Завдання 2. У табл. 6.2 задані значення 10 булевих функцій f(x,y,z).
Таблиця 6.2
Параметр |
Варіант |
|||||||||||
x |
y |
z |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
Для кожного варіанта за таблицею значень булевої функції записати її ДДНФ та ДКНФ. Спростити отримані ДДНФ і ДКНФ, використовуючи тотожності булевої алгебри.
Завдання 3. У табл. 6.3 наведені значення 10 булевих функцій. Функцію Вашого варіанта та функцію для наступного варіанта вважати набором булевих функцій. Визначити, чи є такий набір функцій функціонально-повним.
Таблиця 6.3
Параметр |
Варіант |
|||||||||||
x |
y |
z |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
Завдання 4. У табл. 6.4 наведені ДДНФ булевих функцій номерами конституент одиниці, що закодовані десятковими еквівалентами. Мінімізувати ДДНФ, що відповідає варіанту, за допомогою метода Квайна – Мак-Класки
Таблиця 6.4
Варіант |
|||||||||
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
1 |
0 |
0 |
1 |
1 |
2 |
0 |
1 |
0 |
1 |
2 |
1 |
2 |
3 |
2 |
3 |
3 |
3 |
1 |
5 |
5 |
2 |
4 |
4 |
4 |
5 |
4 |
4 |
2 |
6 |
6 |
3 |
5 |
6 |
5 |
6 |
8 |
6 |
4 |
7 |
7 |
8 |
7 |
7 |
9 |
8 |
9 |
7 |
6 |
8 |
11 |
9 |
9 |
9 |
10 |
11 |
12 |
9 |
8 |
11 |
12 |
10 |
11 |
11 |
11 |
12 |
13 |
10 |
9 |
13 |
14 |
11 |
12 |
13 |
13 |
13 |
14 |
11 |
11 |
14 |
15 |
12 |
14 |
14 |
15 |
15 |
15 |
13 |
14 |
15 |
Завдання 5. Спростити за допомогою карт Карно.
;
;
;
;
;
;
;
;
;
.
Завдання 6 За мінімальною ДНФ завдання 5 побудувати перемикальний ланцюг у базисі ТА-НІ (И-НЕ).
Завдання 7. Визначити за допомогою таблиць істинності, яких висловлювань (Істинне, Хибне, ні те, ні інше) стосуються формули, наведені у табл. 6.5 за Вашими варіантами.
Таблиця 6.5
Варіант |
Формула |
1 |
|
2 |
|
3 |
|
4 |
|
5 |
|
6 |
|
7 |
|
8 |
|
9 |
|
10 |
|
)
Завдання 8. Неорієнтований мультиграф з 9 вершинами заданий матрицею сумiжностi. Деякі елементи цієї матриці r[j,k], позначені координатами j та k, наведені в табл. 6.6. Невказанi елементи матриці дорівнюють нулю. Треба:
а) побудувати повну матрицю сумiжностi, діаграму графа та матрицю iнцiденцiї;
б) знайти у графі ейлерів та гамiльтонiв цикли або ланцюги, якщо вони є;
в) визначити хроматичне число та реберне хроматичне число графа;
г) знайти цикломатичне число графа.
д) побудувати деяке остовне дерево графа;
е) побудувати базис розрiзiв графа, базис циклів графа.
Таблиця 6.6
Параметр |
Варiант |
||||||||||
j |
k |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
1 |
2 |
1 |
0 |
2 |
1 |
2 |
0 |
0 |
2 |
1 |
1 |
1 |
3 |
1 |
2 |
0 |
1 |
2 |
2 |
2 |
1 |
3 |
1 |
2 |
4 |
1 |
2 |
1 |
1 |
0 |
3 |
2 |
1 |
1 |
2 |
2 |
5 |
1 |
1 |
1 |
3 |
1 |
2 |
1 |
1 |
2 |
1 |
2 |
7 |
1 |
1 |
1 |
2 |
1 |
0 |
1 |
1 |
0 |
1 |
3 |
7 |
1 |
1 |
1 |
0 |
1 |
3 |
2 |
0 |
1 |
1 |
3 |
8 |
1 |
2 |
2 |
1 |
2 |
0 |
0 |
1 |
3 |
1 |
3 |
9 |
2 |
3 |
2 |
0 |
1 |
4 |
2 |
2 |
1 |
3 |
4 |
6 |
1 |
0 |
0 |
2 |
2 |
3 |
1 |
1 |
1 |
1 |
5 |
6 |
1 |
1 |
1 |
2 |
1 |
3 |
2 |
0 |
1 |
1 |
6 |
8 |
1 |
2 |
1 |
1 |
1 |
0 |
2 |
3 |
2 |
1 |
7 |
8 |
1 |
1 |
0 |
1 |
0 |
2 |
0 |
1 |
1 |
1 |
8 |
2 |
0 |
0 |
1 |
1 |
0 |
2 |
3 |
1 |
1 |
1 |
8 |
9 |
1 |
1 |
2 |
2 |
1 |
2 |
1 |
3 |
1 |
1 |
Завдання 9. У табл. 6.7 ребрам (Vj, Vk) неорієнтованого графа, що задані номерами вершин j та k, вiдповiдає числова характеристика (довжина, вартість).
Таблиця 6.7
Параметр |
Варiант |
||||||||||
j |
k |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
1 |
2 |
15 |
12 |
5 |
10 |
17 |
2 |
15 |
3 |
3 |
9 |
1 |
4 |
2 |
5 |
3 |
3 |
5 |
2 |
4 |
2 |
10 |
2 |
1 |
5 |
16 |
7 |
9 |
7 |
7 |
5 |
2 |
15 |
5 |
9 |
2 |
3 |
1 |
15 |
10 |
2 |
16 |
9 |
14 |
14 |
7 |
7 |
2 |
4 |
1 |
14 |
7 |
20 |
15 |
12 |
17 |
12 |
10 |
8 |
2 |
7 |
13 |
11 |
3 |
8 |
15 |
2 |
11 |
2 |
1 |
7 |
3 |
4 |
3 |
6 |
3 |
10 |
1 |
2 |
10 |
11 |
2 |
2 |
3 |
5 |
2 |
2 |
12 |
9 |
8 |
3 |
8 |
10 |
4 |
9 |
4 |
5 |
10 |
4 |
6 |
5 |
3 |
9 |
2 |
6 |
10 |
8 |
4 |
6 |
15 |
7 |
4 |
11 |
2 |
15 |
14 |
4 |
3 |
7 |
5 |
6 |
5 |
2 |
11 |
14 |
14 |
9 |
7 |
2 |
3 |
3 |
5 |
7 |
3 |
11 |
1 |
3 |
11 |
8 |
3 |
5 |
2 |
2 |
6 |
7 |
3 |
3 |
14 |
12 |
2 |
2 |
9 |
3 |
4 |
2 |
Довжини ребер, не вказані у таблиці, вважаються рівними нескiнченностi. Необхідно:
а) визначити відстань від вершини V1 до решти вершин;
б) побудувати на вершинах графа дерево мiнiмальної вартості.
Завдання 10. Транспортна мережа складається з дуг, що йдуть вiд вершини Vj до вершини Vk. Пропускнi спроможностi дуг, задані номерами j та k, вказані у табл. 6.7. V1 – вхід мережі, V7 – вихід. Знайти найбiльший потiк та найменший розрiз мережi.