Методичка (дискретка)

5.Функція від трьох змінних набуває значень 1 на наборах № 1, 2, 4, 7. Побудувати ДДНФ і ДКНФ. З’ясувати, чи буде ця функція самодвоїстою.

6.З’ясувати, чи будуть повними системи функцій:

9. Функція f приймає значення 1 на наборах: 010, 011, 100, 101 та 111.

За допомогою методу Петрика знайти тупикові ДНФ та вибрати серед них мінімальні форми.

B6

b)f (x, y, z) ((x y) (x z) (x y z) y .

3.Нехай задана функція f (x, y) (x | y) (x y) x .

a)Який порядковий номер цієї функції?

b)Застосовуючи тотожні перетворення, спростити формулу, яка задає f (x, y) .

e) Побудувати f * (x, y) . Чи буде функція f (x, y) самодвоїстою?

41

таблицею істинності побудувати ДДНФ і ДКНФ. З’ясувати, чи буде ця функція самодвоїстою.

шляхом тотожних перетворень та за допомогою таблиць істинності. 7. З’ясувати, чи будуть повними системи функцій:

простими?

10.За допомогою карт Карно мінімізувати булеві функції:

12.За допомогою методу Петрика знайти тупикові ДНФ та вибрати серед них мінімальні форми для булевої функції, яка задана вектором

C6

42

таблицею істинності побудувати ДДНФ і ДКНФ. З’ясувати, чи буде ця функція самодвоїстою.

тотожних перетворень до ДДНФ та ДКНФ.

7.Знайти всі самодвоїсті функції від двох змінних.

8.Перевірити рівності:

7. Графи

b) граф G є незв’язним і має рівно дві компоненти зв’язності, якщо ребро e не входить у жодний цикл графа G .

Розв’язання.

a) Нехай дві довільні вершини v і w є зв’язаними у графі G . Покажемо,

зв’язним.

b) Нехай ребро e (u1, u2 ) не належить жодному циклу графа G . Тоді у графі G вершини u1 та u2 будуть незв’язаними і будуть належати двом різним компонентам зв’язності G1 та G2 графа G . Крім того, у графі G

43

Задача 2. Якщо у простому графі G тільки дві вершини v та w мають непарні степені, то вони зв’язані. Довести.

наслідком з леми про рукостискання кожен простий граф має парну кількість вершин непарної степені. Тому і вершина w повинна належати цій же компоненті, оскільки за умовою інших вершин непарної степені не існує. Отже, вершини v та w зв’язані.

При побудові відображення враховуємо степінь вершин графів: в графі G1

графі G1 , то їх образи h(u) та h(v) є суміжними у графі G2 . Отже, графи G1 та G2 ізоморфні.

44

перевірити, що це відображення також зберігає суміжність вершин.

Розв’язання. Дерево – це зв’язний ациклічний граф. Отже, потрібно довести, що T – це зв’язний граф. Доведення проведемо від супротивного. Нехай T – незв’язний граф, який має k компонент зв’язності: T1, T2 , , Tk ,

тобто є зв’язним. Це і означає, що граф Е є деревом.

A7

45

Чи буде послідовність вершин 1 2 1 5 2 4 маршрутом? Побудувати:

a)маршрут, який з’єднує вершини 1 та 4 і не є ланцюгом;

b)ланцюг, який з’єднує вершини 1 та 4 і не є простим ланцюгом;

c)прості ланцюги, які з’єднують вершини 1 та 4 і мають найбільшу та найменшу довжини;

d)циклічний маршрут, який містить вершину 1 та не є циклом;

e)цикл, який містить вершину 1 та не є простим циклом;

f)прості цикли, які містять вершину 1 та мають найбільшу та найменшу довжини.

46

Знайти всі ланцюги, які з’єднують вершини 1 та 9. Скільки серед них буде простих?

15.Граф, ізоморфний своєму доповненню, називається самодоповнювальним графом. Довести, що існує тільки один самодоповнювальний граф із чотирма вершинами. Побудувати його.

18.Побудувати всі дерева з п’ятьма вершинами (з точністю до ізоморфізму).

19.Незв’язний граф, кожна компонента зв’язності якого є дерево, називається лісом. Скільки ребер містить такий граф з n вершинами і k компонентами зв’язності?

21.Для графів G1 та G2 побудувати відповідні їм остовні дерева:

a)вилучаючи ребро з кожного циклу;

b)пошуком в ширину;

c)пошуком в глибину.

47

Знайти напівстепені входу і виходу кожної вершини. Зясувати, чи має цей граф джерело та стік.

24. Побудувати орієнтований граф з сімома вершинами, який має 2 недосяжні і 3 тупикові вершини.

B7

48

5. Чи існує граф із шістьма вершинами, степені яких дорівнюють: a) 1, 2, 3, 3, 4, 4; b) 2, 3, 3, 4, 4, 4; c) 2, 2, 2, 4, 5, 5.

Відповідь обґрунтувати.

6.Побудувати граф із п’ятьма вершинами, у якому тільки дві вершини мають однакові степені. Чи можуть ці вершини мати степінь 0 або степінь

4?

7.Побудувати об’єднання, перетин, різницю та доповнення графів:

49

a)Вказати степінь кожної вершини.

b)Перевірити лему про рукостискання та її наслідок.

c)Не будуючи доповнення G , вказати, скільки ребер буде мати

11.Кубічний граф – це граф, степінь кожної вершини якого дорівнює 3. Побудувати кубічний граф, що має:

a) 4 вершини; b) 6 вершин; c) 8 вершин. Чи існує кубічний граф з n вершинами, якщо:

такому графі?

13.Довести, що доповнення кубічного графа не є кубічним графом.

15.Чи існує самодоповнювальний граф, у якого кількість ребер

16.Побудувати всі самодоповнювальні графи із п’ятьма вершинами.

Які з наведених нижче послідовностей вершин є маршрутом: a) abcabcd ; b) d f bac f ; c) bcd f ca ; d) d f c ab ?

Вказати ланцюги, прості ланцюги та довжину кожного маршруту. 18.Чи має граф

50