Вопрос 10. Для графа g найти диаметр графа, радиус графа, центр графа, эйлеров обход, гамильтонов путь и цикл. [л.3, стр. 29, №6.2 (14)].

Диаметр графа G равен d(G)=max d(v_i,v_j)=3. Найдем радиус графа: r(v₁)=3, r(v₂)=3, r(v₃)=3, r(v₄)=3, r(v₅)=3, r(v₆)=3, r(v₇)=3. Радиус графа G равен r(G)=3. В графе G все вершины являются центром графа. Так как три вершины имеют нечетные степени, следовательно в графе G эйлерова обхода нет. Найдем хотя бы один гамильтонов цикл: v₅-v₂-v₃-v₇-v₆-v₄-v₁-v₅.

Вопрос 11. Булева алгебра. [л.3, стр. 35, №7.4 (14)].

Найти минимальные ДНФ и КНФ булевой функции f(x, y, z, t)=1 на наборах {0, 1, 2, 3, 8, 10, 11}.

Построим таблицу истинности данной функции:

	x	y	z	t	f
0	0	0	0	0	1
1	0	0	0	1	1
2	0	0	1	0	1
3	0	0	1	1	1
4	0	1	0	0	0
5	0	1	0	1	0
6	0	1	1	0	0
7	0	1	1	1	0
8	1	0	0	0	1
9	1	0	0	1	0
10	1	0	1	0	1
11	1	0	1	1	1
12	1	1	0	0	0
13	1	1	0	1	0
14	1	1	1	0	0
15	1	1	1	1	0

Используем карты Карно для нахождения минимальных форм.

zt\xy	00	01	10	11
00	1	0	1	1
01	1	0	0	0
10	1	0	0	0
11	1	0	1	0

S₃

S₁ S₂

S₁=¬(xy)¬zt + ¬(xy) z¬t + ¬(xy)zt + ¬(xyzt) = ¬(xy);

S₂=x¬y¬(zt) + x¬y zt = x¬y;

S₃= x¬y¬(zt) + xy¬(zt) = x¬(zt).

Составляем минимальную ДНФ: ¬(xy) ˅ x¬y ˅ x¬(zt).

zt\xy	00	01	10	11
00	1	0	1	1
01	1	0	0	0
10	1	0	0	0
11	1	0	1	0

S₃

S₁ S₂

S₁=x¬yzt + x¬y z¬t + x¬y¬zt + x¬y¬(zt) = x¬y;

S₂=¬(xy z)t + ¬(xy zt) =¬ (xyz);

S₃= ¬xyz¬t +¬(xy)z¬t = ¬ xz¬t.

Составляем минимальную КНФ: x¬y ˄ ¬ (xyz) ˄ ¬ xz¬t.