Задача № 1. Для графов G1 и G2 (рис. 15.1) построить графы G1G2, G1G2, G1(G2), G2(G1), матрицы смежности вершин А(G1), А(G2) и матрицы инцидентности В(G1), В(G2), введя предварительно нумерацию дуг. По матрицам смежности вершин исходных графов построить матрицы смежности вершин А(G1G2), А(G1G2), А(G1(G2)), А(G2(G1)). Будут ли изоморфны графы G1(G2) и G2(G1)?

Рис. 15.1

граф G1UG2

граф G1∩G2

граф G1(G2)

граф G2(G1)

Задача № 2. При условии, что петля считается двойным ребром, для графов G1 и G2 (рис. 15.2) построить матрицы смежности вершин А(G1) и А(G2), введя предварительно нумерацию рёбер, построить матрицы инцидентности В(G1) и В(G2). По матрицам смежности вершин исходных графов построить матрицы смежности вершин А(G1G2) и А(G1G2).

Рис. 15.2

Построим матрицу смежности А(G1G2)

Построим матрицу смежности А(G1G2)

Задача № 3. Построить код (G) по дереву G (рис. 15.3) и восстановить G.
1 6 8

2 3 5 7
4 9 Рис. 15.3

Задача № 4. По алгоритму Краскала построить для нагруженного графа G, изображенного на рис. 15.4, минимальный каркас G1 с указанием последовательности выбора рёбер ei. Определить вес построенного каркаса (G1).

v2 3 v9
1 4 5
5 2 5 v10 1 v8
v1 4 v3 3 v12 1 1 v11 4 2
3 v5 2 4 v7
1 2 1 2 3
v4 5 v6

Рис. 15.4
M(G1) = 1+1+1+1+1+1+2+2+2+3+3 = 18
Задача № 5. В графе G, изображённом на рис. 15.5, найти все минимальные внешне устойчивые множества вершин, наименьшие доминирующие множества и число внешней устойчивости (G).

Рис. 15.5

Задача № 6. Построить максимальный поток и разрез с минимальной пропускной способностью в транспортной сети, приведённой на рис. 15.6, по алгоритму Форда-Фалкерсона.

Рис. 15.6

(S^+,3), (c^+,3), (c^+,4),ε = 3
(S^+,2), (b^+,2), (d^+,2), ε = 2
(S^+,1), (a^+,3), (b^+,1), (e^+,1), ε = 1
(d^-,1), (a^-,2)
x = {s,a,b,c,d,e}, x⃐={t}
(x,x⃐) = {(d,t),(e,t)}
f=11
c =11
Задача № 7. Доказать справедливость тождества для произвольных множеств А, B и C:

( (A⋂C ̅)⋃(B⋂C ̅)) ̅ = (A ̅⋂B ̅)⋃C
((A⋂C ̅)) ̅⋂((B⋂C ̅)) ̅ = (A ̅⋃C)⋂(B ̅⋃C) = (A ̅⋂B ̅)⋃C

Задача № 8. Доказать, что множества Х и Y равномощны, построив взаимно-однозначное соответствие между ними.
Х=(–2,+), Y=R.
Задача № 9. Даны три вещественных функции:
, g(x)= –13arctg(7x)–20, h(x)= –5ln(x2+1).
1) Найти заданные композиции функций: fgh, hgf, ggf.
2) Являются ли f, g, h инъекциями, сюръекциями, биекциями на R?
3) Найти обратные функции к f, g, h. Если функции со своими областями определения обратных не имеют, то найти обратные функции к их сужениям.
Задача № 10. Является ли транзитивным бинарное отношение R1R2, если отношения R1 и R2 транзитивны? В случае отрицательного ответа необходимо привести конкретный пример.