Учебное пособие: Дискретная мат-ка_УП

166

2. 

Задан

граф

 G=(X,U), X={x1,x2,x3,x4,x5}, U={(x1,x4), 

(x1,x3), (x2,x1), (x2,x4), (x3,x4), (x3,x5),(x4,x4),(x4,x5)}. 

Постро

-

ить

его

графическое

представление

и

матрицы

инциденций

и

смежности

, 

все

простые

цепи

. 

3. 

Доказать

, 

что

полный

граф

имеет

 n

n–2

деревьев

. 

Вариант №18 
1. 

Задан

граф

 G=(X,U),  

X={1, 2, 3, 4, 5, 6, 7, 8, 9,10}, U={(2,4), (1,8), (2,7), (3,6), (5,3), 

(1,3), (2,5), (4,6), (3,4), (6,8), (5,6), (1,9), (9,3), (5,7), (7,1),  (3,7)}. 

Нарисуйте

его

,  

дайте

полную

характеристику

  (

связность

, 

циклы

, 

ориентированность

, 

матрица

расстояний

и

т

.

д

.), 

задайте

матрицей

смежности

. 

2. 

Задан

граф

 G=(X,U), X={x1,x2,x3,x4,x5,x6}, U={(x1,x2), 

(x2,x4), (x4,x6), (x1,x1), (x3,x6), (x3,x2), (x1,x5), (x3,x1), (x6,x5), 
(x6,x1), (x2,x5), (x5,x4)}.

Постройте

граф

. 

Найдите

раскраску

гра

-

фа

. 

Начиная

с

 1 

вершины

и

с

 5. 

3. 

Построить

сеть

Петри

для

решения

задачи

о

 5 

мудрецах

. 

(5 

мудрецов

. 

Могут

есть

или

думать

. 

Для

еды

им

даны

 5 

палочек

. 

Чтобы

поесть

, 

мудрецу

нужны

 2 

палочки

.) 

 
Вариант №19 
1. 

Задан

граф

 G=(X,U),  

X={1, 2, 3, 4, 5, 6, 7, 8, 9}, U={(2,4), (2,8), (2,7), (3,6), (2,3), 

(1,3), (2,5), (4,6),  (5,6), (4,8), (1,9), (9,3), (1,7), (7,4), (3,7)}. 

Нарисуйте

его

,  

дайте

полную

характеристику

, (

связность

, 

циклы

, 

ориентированность

, 

матрица

расстояний

и

т

.

д

.) 

задайте

матрицей

смежности

. 

2. 

Задан

граф

 G=(X,U), X={x1,x2,x3,x4,x5,

х

6}, U={(x1,x2), 

(x2,x4), (x4,x3), (x1,x1), (x3,x4), (x3,x2), (x1,x5), (x3,x1), (x5,x5), 
(x2,x1), (x3,x5), (x5,x4),(

х

1,

х

6), (

х

2,

х

6)}. 

Постройте

его

, 

найдите

все

простые

цепи

из

 3 

в

 6 

вершину

.  

3. 

Показать

, 

что

граф

, 

имеющий

мост

, 

не

является

эйлеро

-

вым

. 

 
Вариант №20 
1. 

Задан

граф

 G=(X,U),  

167

X={1, 2, 3, 4, 5, 6, 7}, U={(1,4), (2,7), (3,6), (2,3), (1,3), (2,5), 

(4,6), (3,4), (5,6),  (2,7),  (3,7),(6,7),(1,5)}. 

Нарисуйте

его

,   

двойственный

ему

граф

, 

плоский

и

планар

-

ный

, 

дайте

полную

характеристику

, 

задайте

матрицей

смежности

. 

2. 

Задан

граф

 G=(X,U), X={x1,x2,x3,x4,x6,x5}, U={(x1,x2), 

(x2,x3), (x4,x3), (x5,x1), (x3,x6), (x3,x2), (x1,x5), (x3,x1), (x6,x5), 
(x6,x1), (x3,x5), (x5,x4)}. 

Дайте

определения

: 

маршрута

, 

цепи

, 

цикла

, 

связности

. 

Постройте

на

заданном

графе

маршрут

, 

цепь

, 

цикл

, 

покрывающее

его

дерево

. 

3. 

Определить

число

неизоморфных

деревьев

двудольного

графа

К

2,3

. 

 
Вариант №21 
1. 

Задан

граф

 G=(X,U),  

X={1, 2, 3, 4, 5, 6, 7, 8, 9}, U={(1,4), (1,8), (2,7), (3,6), (2,3), 

(1,3), (2,5),  (6,8), (5,6),  (1,9), (9,3), (2,7), (7,7), (3,7)}. 

Нарисуйте

его

, 

Нарисуйте

двойствегнный

ему

граф

. 

Дайте

полную

характеристику

двойственного

графа

, 

задайте

матрицей

смежности

, 

постройте

плоский

и

планарный

графы

. 

2.

Дайте

определение

цикла

, 

маршрута

. 

Приведите

пример

, 

используя

граф

заданный

таблицей

: 

X1  X2 X3 X4 X5 

X1 

0  1 1 0 1 

X2 

1  0 1 0 0 

X3 

1  1 0 1 1 

X4 

0  0 1 0 1 

X5 

1  0 1 1 0 

Найдите

хроматическое

число

и

диаметр

заданного

графа

. 

3. 

Доказать

, 

что

удаление

одного

ребра

, 

которое

принадлежит

какому

-

то

циклу

связного

графа

, 

не

делает

этот

граф

несвязным

. 

Вариант №22 
1. 

Задан

граф

 G=(X,U),  

X={1, 2, 3, 4, 5, 6, 7, 8, 9}, U={(1,4), (1,8), (2,7), (3,6), (2,3), 

(1,3), (2,5),  (6,8), (5,6),  (1,9), (9,3), (2,7),  (7,7), (3,7)}. 

168

Нарисуйте

его

,  

найдите

подграф

, 

суграф

, 

дополненние

до

полного

графа

. 

2.

Задан

граф

 G=(X,U),|X|=6 (6 

вершин

) 

и

степень

каждой

вершины

ρ ≥ 3. 

Нарисовать

такой

граф

и

построить

все

его

про

-

стые

циклы

. 

3. 

Доказать

, 

что

эйлеров

граф

не

имеет

мостов

. 

 
Вариант №23 
1. 

Задан

граф

 G=(X,U),  

X={1, 2, 3, 4, 5, 6, 7}, U={(1,4), (2,7), (3,6), (2,3), (1,3), (2,5), 

(4,6), (3,4), (5,6),  (2,7),  (3,7),(6,7),(1,5)}. 

Нарисуйте

его

, 

задайте

матрицей

инциденций

, 

постройте

подграф

, 

суграф

, 

дополнение

до

полного

графа

. 

2. 

Дайте

определение

и

назначение

решетчатого

графа

. 

При

-

ведите

пример

основных

соотношений

. 

Найдите

расстояние

меж

-

ду

вершинами

 x5 

и

 x27 (

решетку

взять

из

лекций

). 

3. 

Постройте

примеры

графов

, 

для

которых

алгоритм

после

-

довательного

раскрашивания

строит

не

минимальную

раскраску

. 

169

КОНТРОЛЬНАЯ

РАБОТА

№

2 

Вариант №1 
1. 

Построить

таблицу

истинности

функции

, 

реализуемую

следующей

формулой

: 

(x

→y)⊕ ((y→z)~(¬z∨x)). 

Привести

к

виду

ДНФ

, 

используя

алгебраические

преобра

-

зования

. 

2. 

Задана

булева

функция

. 

Получить

СДНФ

, 

используя

раз

-

ложение

Шеннона

. 

Х

1

Х

2

∨

Х

1

Х

3

∨¬

Х

2

¬

Х

3

∨¬

Х

1

Х

2

Х

3

∨

Х

2

¬

Х

3. 

3. 

Задана

булева

функция

.  

F = X1¬X2X5

∨X1X2X4¬X5∨X1¬X2¬X3X5∨X2X3¬X4¬X5∨ 

X1X2¬X3X4¬X5. 

Построить

карту

Карно

. 

4. 

Минимизировать

, 

используя

метод

Квайна

и

метод

Пет

-

рика

. 

F = 

Х

1

Х

2

¬

Х

3

¬

Х

4 

∨ ¬

Х

2

¬

Х

3

¬

Х

4 

∨ 

Х

1

Х

2

Х

3 

∨ ¬

Х

2

Х

3

Х

4 

∨ 

Х

1

Х

3

¬

Х

4 

∨ 

Х

1

¬

Х

2

¬

Х

3

Х

4. 

5. 

Минимизировать

, 

используя

карты

Карно

. 

Задана

КНФ

булевой

функции

. 

F=(X1

∨X2∨¬X3)(X2∨X3∨X4)(X3∨¬X4)(¬X2∨¬X5). 

Вариант №2 
1. 

Построить

таблицу

истинности

функции

, 

реализуемую

следующей

формулой

: 

 ((x

∧y)∨z)⊕(z→x). 

Привести

к

виду

ДНФ

, 

используя

алгебраические

преобра

-

зования

. 

2. 

Задана

булева

функция

. 

Получить

СДНФ

, 

используя

раз

-

ложение

Шеннона

. 

Х

1

Х

2

Х

3

∨

Х

1

Х

3

∨¬

Х

2

¬

Х

3

∨¬

Х

1

Х

2

¬

Х

3

∨

Х

2

¬

Х

3. 

3. 

Задана

булева

функция

от

 5 

переменных

. 

Построить

карту

Карно

. 

F=¬X1¬X2X4

∨X1X2X4¬X5∨X1¬X2¬X4X5∨X2X3¬X4¬X5∨ 

X1¬X3X4¬X5. 

170

4. 

Минимизировать

, 

используя

метод

Квайна

и

метод

Пет

-

рика

. 

F = 

Х

1

Х

2

¬

Х

3

¬

Х

4 

∨ ¬

Х

2

¬

Х

3

∨

Х

1

Х

2

Х

3 

∨ ¬

Х

2

Х

3

Х

4 

∨ 

Х

1

Х

3

¬

Х

4 

∨ ¬

Х

2

¬

Х

3

Х

4

∨

Х

1

Х

2

¬

Х

3

Х

4. 

5. 

Минимизировать

, 

используя

карты

Карно

. 

¬X1X2¬X3¬X4¬X5  ∨ X1¬X2X3¬X4¬X5∨X1X4¬X5  ∨ 

¬X2¬X3X4X5  ∨ X1¬X2¬X3X4¬X5  ∨ X1X2¬X3¬X5  ∨ 
X1

¬X3X4X5  ∨ X1X2¬X4X5 ∨  X1¬X3¬X4X5. 

 
Вариант №3 
1. 

Построить

таблицу

функции

, 

реализуемую

следующей

формулой

: 

 (x

⊕¬y)∧(x∨z). 

Привести

к

виду

ДНФ

, 

используя

алгебраические

преобра

-

зования

. 

2. 

Получить

СДНФ

функции

 f=(x

∧y∧¬z∨¬x∧y∧z)Æ(x∨y). 

3. 

Используя

карты

Карно

, 

сравнить

две

функции

: 

F

1

 = 

Х

1

Х

2

¬

Х

3

¬

Х

4 

∨ ¬

Х

2

¬

Х

3

¬

Х

4 

∨ 

Х

1

Х

2

Х

3 

∨ ¬

Х

2

Х

3

Х

4 

∨ 

Х

1

Х

3

¬

Х

4 

∨ 

Х

1

¬

Х

2

¬

Х

3

Х

4. 

F

2

 = X1 

∨ ¬X1¬X2¬X3¬X4 ∨ ¬

Х

2

Х

3

Х

4. 

4. 

Минимизировать

, 

используя

метод

Квайна

и

метод

Пет

-

рика

. 

Х

1

Х

2

¬

Х

4 

∨ ¬

Х

2

¬

Х

3

¬

Х

4 

∨ 

Х

1

Х

2

Х

3X4 

∨ X1¬

Х

2X3 

∨ 

Х

1

Х

3

¬

Х

4 

∨ 

Х

1

¬

Х

2

¬

Х

3

Х

4

∨¬

Х

1

¬

Х

2

¬

Х

3

Х

4. 

5. 

Минимизировать

, 

используя

карты

Карно

. 

X1X2

¬X3X4 ∨ X1¬X2X3¬X5 ∨ X2X3X5 ∨ X2X3¬X5 ∨ 

X2

¬X3X5. 

 
Вариант №4 
1. 

Построить

таблицу

функции

, 

реализуемую

следующей

формулой

: 

¬((¬x

⊕y)∨(x~z)). 

Привести

к

виду

ДНФ

, 

используя

алгебраические

преобра

-

зования

. 

2. 

Минимизировать

, 

используя

метод

Квайна

и

метод

Пет

-

рика

.