Прикладная математика - контрольная работа

50

Контрольная работа

15 вариант

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

Рис. 15.1

граф G1UG2

граф G1∩G2

граф G1(G2)

граф G2(G1)

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

Рис. 15.2

Построим матрицу смежности А(G₁G₂)

Построим матрицу смежности А(G₁G₂)

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

1 6 8

2 3 5 7

4 9 Рис. 15.3

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

v₂ 3 v₉

1 4 5

5 2 5 v₁₀ 1 v₈

v₁ 4 v₃ 3 v₁₂ 1 1 v₁₁ 4 2

3 v₅ 2 4 v₇

1 2 1 2 3

v₄ 5 v₆

Рис. 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, по алгоритму Форда-Фалкерсона.

d

4,2

Рис. 15.6

,3),,3),,4),ε = 3

,2),,2),,2), ε = 2

,1),,3),,1),,1), ε = 1

,1),,2)

x = {s,a,b,c,d,e}, x⃐={t}

(x,x⃐) = {(d,t),(e,t)}

f=11

c =11

Задача № 7. Доказать справедливость тождества для произвольных множеств А, B и C:

= ()⋃C

= ⋃C)⋂⋃C) = ()⋃C

Задача № 8. Доказать, что множества Х и Y равномощны, построив взаимно-однозначное соответствие между ними.

Х=(–2,+), Y=R.

Задача № 9. Даны три вещественных функции:

, g(x)= –13arctg(7x)–20, h(x)= –5ln(x²+1).

1) Найти заданные композиции функций: fgh, hgf, ggf.

2) Являются ли f, g, h инъекциями, сюръекциями, биекциями на R?

3) Найти обратные функции к f, g, h. Если функции со своими областями определения обратных не имеют, то найти обратные функции к их сужениям.

Задача № 10. Является ли транзитивным бинарное отношение R₁R₂, если отношения R₁ и R₂ транзитивны? В случае отрицательного ответа необходимо привести конкретный пример.