Основы дискретной математики - тест 11

Упражнение 1:

---

Номер 1

 Построить для заданного нагруженного неориентированного  графа G=(V,E) минимальный остов.
V= {1,2,3,4,5,6,7,8, 9 }, 
E={(1,2;15), (1,3; 2), (1,4; 8), (1,7; 9), (2,3; 4), (2,5; 9), (2,9; 8), (3,4; 6), (6,3; 5), (6,5; 7), (6,4; 3), (6,8; 16), (4,7; 10), (4,8; 8), (7,8; 7), (8,9; 15)}
(здесь  каждая скобка (u,v; D) задает ребро (u,v) из E и его "вес"  c(u,v)=D ).
Каков вес этого остова?

Ответ:

---

Номер 2

 Построить для заданного нагруженного неориентированного  графа G=(V,E) минимальный остов.
V= {a, b, c, d, e, f, g, h }, 
E= {(a,b; 10), (a,c; 14),(a,f; 13), (a,g; 17), (h,a; 19) ,(b, d; 10), (b,f; 20), (b,g; 10), (c, d; 15), ( c,g; 13), (d, e; 5), (d,f; 13), (e,f; 12), (h, g; 21) }
(здесь  каждая скобка (u,v; D) задает ребро (u,v) из E и его "вес"  c(u,v)=D ).
Каков вес этого остова?

Ответ:

---

Номер 3

 Построить для заданного нагруженного неориентированного  графа G=(V,E) минимальный остов.
V= {a, b, c, d, e, f, g, h, k },
E= {(a,b; 10), (a,c; 9),(a,f; 20), (a,k; 7), (b, d; 17), (b,f; 27), (b,g; 10), (c, d; 17), ( c,g; 3), (c, h; 9), (d, e; 5), (d,f; 20), (h,g; 10), (h,k; 12) }.
(здесь  каждая скобка (u,v; D) задает ребро (u,v) из E и его "вес"  c(u,v)=D ).
Каков вес этого остова?

Ответ:

---

Упражнение 2:

---

Номер 1

 Пусть задан неориентированный нагруженный граф G:
V= {a, b, c, d, e, f, g, h }, 
E= {(a,b; 5), (a, h; 7), (b, c; 4), (b, f; 3), (c, d; 6), (c,f; 7), (d, e; 10), (e, f; 9), ( b,g; 15), (g, h; 10) }
(здесь  каждая скобка (u,v; D) задает ребро (u,v) из E и его "вес"  c(u,v)=D ).
Какие из следующих трех ребер не могут попасть ни в какой минимальный остов?
I)   (b, g)   II)  (c, f)    III)  (d, l)

Ответ:

---

Номер 2

 Пусть задан неориентированный нагруженный граф G:
V= {a, b, c, d, e, f, g, h, k }, 
E= {(a, b; 9), (a, c; 6), (b, c; 10), (b, d; 5), (b, e; 4), (d, e; 6), (d, f; 4), (e, f; 25),(f, g; 20), (g, h; 8), (g, k; 10), (h, k; 7) }
(здесь  каждая скобка (u,v; D) задает ребро (u,v) из E и его "вес"  c(u,v)=D ).
Какие из следующих трех ребер не могут попасть ни в какой минимальный остов?
I)   (b, c)   II)  (f, g)    III)  (g, k)

Ответ:

---

Номер 3

 Пусть задан неориентированный нагруженный граф G:
V= {a, b, c, d, e, f, g, h, k }, 
E= {(a, b; 10), (a, c; 7), (b, f; 21), (b, d; 9), (c, d; 8), (f, e; 7), (f, g; 8), (e, k; 12), (e, h; 10), (g, h; 8) }
(здесь  каждая скобка (u,v; D) задает ребро (u,v) из E и его "вес"  c(u,v)=D ).
Какие из следующих трех ребер не могут попасть ни в какой минимальный остов?
I)   (a, b)   II)  (e, h)    III)  (b, f)

Ответ:

---

Упражнение 3:

---

Номер 1

 Пусть неориентированный граф G=(V,E) задан с помощью списков смежности:

La: c, d, b           Lb: a, f, g             Lc: a, d, e
Ld: a, c, e           Le: c, d                Lf: b
Lg: b, i, h           Lh: g, i                Li: g, h

Постройте, начиная с вершины a, обход этого графа в глубину, в котором соседи каждой вершины рассматриваются в порядке, определенном ее списком смежности. Какая из следующих нумераций вершин ему соответствует?

Ответ:

---

Номер 2

 Пусть неориентированный граф G=(V,E) задан с помощью списков смежности:

La: b, c, d, g           Lb: a, f, d             Lc: a, d, e
Ld: a, b, c, e           Le: c, d, f             Lf: b, e
Lg: a, i, h              Lh: g, i                Li: g, h
Постройте, начиная с вершины a,  обход этого графа в глубину, в котором соседи каждой вершины рассматриваются в порядке, определенном ее списком смежности. Какая из следующих нумераций вершин ему соответствует?

Ответ:

---

Номер 3

 Пусть неориентированный граф G=(V,E) задан с помощью списков смежности:

La: d, c, b           Lb: a                   Lc: i, h
Ld: a, e, f           Le: d, g, f             Lf: d, e, g
Lg: e, f              Lh: c, i                Li: c, h
Постройте, начиная с вершины a, обход этого графа в глубину, в котором соседи каждой вершины рассматриваются в порядке, определенном ее списком смежности. Какая из следующих нумераций вершин ему соответствует?

Ответ:

---

Упражнение 4:

---

Номер 1

 Пусть задан неориентированный граф G=(V,E):
V= {a, b, c, d, e, f, g, h , i}, E = {(a, b), (a, c), (b, d), (b, c), (d, e), (d, f), (f, g), (f, h), (f,i) }.
Используя вариант поиска в глубину с подсчетом функции ВЕРХ, определите все мосты этого графа и укажите их число.

Ответ:

---

Номер 2

 Пусть задан неориентированный граф G=(V,E):
V= {a, b, c, d, e, f, g, h , i}, E = {(a, b), (a, c), (b, d), (b, c), (b, e), (f, e), (f, g), (d, h), (f, i), (h, a) }.
Используя вариант поиска в глубину с подсчетом функции ВЕРХ, определите все мосты этого графа и укажите их число.

Ответ:

---

Номер 3

 Пусть задан неориентированный граф G=(V,E):
V= {a, b, c, d, e, f, g, h , i}, E = {(a, b), (a, c), (b, d), (b, c), (b, f), (d, e), (f, e), (a, g), (g, i), (h, g), (i, h) }.
Используя вариант поиска в глубину с подсчетом функции ВЕРХ, определите все мосты этого графа и укажите их число.

Ответ:

---

Упражнение 5:

---

Номер 1

 Пусть задан ориентированный нагруженный граф G:
V= {a, b, c, d, e, f, g, h }, 
E= {(a,b; 21), (a, c; 5), (a, d; 4), (a, e; 16), (a, f; 13), (a, g; 10), (b, e; 10), (b, f; 8), ( b,g; 5), (b, h; 2), (c, e; 10), (c,f; 7), (d, b; 10), (d, g; 5), (d, h; 21), (g,b; 10), (g, h; 10) }
(здесь  каждая скобка (u,v; D) задает ребро (u,v) из E и его "вес"  c(u,v)=D ).
Используя алгоритм Дейкстры, определите дерево кратчайших путей из вершины a в остальные вершины графа. Каков суммарный вес всех ребер этого дерева?

Ответ:

---

Номер 2

 Пусть задан ориентированный нагруженный граф G:
V= {a, b, c, d, e, f, g, h }, 
E= { (a, c; 24), (a, d; 8), (a, e; 12), (a, f; 2), (a, g; 15), (b, c; 5), ( b,g; 15), (c, h; 5), (d, b; 10), (d, e; 3), (d, g; 10), (d, h; 21), (e, g; 2), (f, d; 5), (f, b; 17) }
(здесь  каждая скобка (u,v; D) задает ребро (u,v) из E и его "вес"  c(u,v)=D ).
Используя алгоритм Дейкстры, определите дерево кратчайших путей из вершины a в остальные вершины графа. Каков суммарный вес всех ребер этого дерева?

Ответ:

---

Номер 3

 Пусть задан ориентированный нагруженный граф G:
V= {a, b, c, d, e, f, g, h }, 
E= { (a, b; 5), (a, c; 32), (a, d; 2), (a, e; 32), (a, f; 12), (a, g; 15), (b, f; 6), (b, e; 20), ( b, h; 4), (c, h; 5), (d, g; 8), (d, h; 21), (g, c; 10), (g; e; 12), (f, d; 5), (f, b; 17) }
(здесь  каждая скобка (u,v; D) задает ребро (u,v) из E и его "вес"  c(u,v)=D ).
Используя алгоритм Дейкстры, определите дерево кратчайших путей из вершины a в остальные вершины графа. Каков суммарный вес всех ребер этого дерева?

Ответ:

---

Упражнение 6:

---

Номер 1

Какие из следующих утверждений о работе алгоритма Дейкстры верны?
А) Значения D[w] текущего расстояния от исходной вершины до вершины w, добавляемой на каждом этапе к множеству отмеченных вершин S, не убывают.
Б) В дереве кратчайших путей, построенном алгоритмом Дейкстры, длины ребер на каждой ветви не убывают.
В) На каждом этапе алгоритма Дейкстры кратчайший путь из исходной вершины в любую вершину множества S проходит только через вершины множества S.

Ответ:

---

Номер 2

Какие из следующих утверждений о работе алгоритма Дейкстры на графе с n вершинами верны?
А) Значения D[w] текущего расстояния от исходной вершины до вершины w, добавляемой на каждом этапе к множеству отмеченных вершин S, не возрастают.
Б) Число этапов (итераций основного цикла) не превосходит (n - 1).
В) На каждом этапе алгоритма Дейкстры кратчайший путь из исходной вершины в любую вершину множества S не длиннее кратчайшего пути из исходной вершины в любую вершину множества (V \ S).

Ответ:

---

Номер 3

Какие из следующих утверждений о работе алгоритма Дейкстры верны?
А) Если в графе нет циклов отрицательной длины, то алгоритм Дейкстры работает верно.
Б) На каждом этапе алгоритма Дейкстры кратчайший путь из исходной вершины в любую вершину множества S не короче кратчайшего пути из исходной вершины в любую вершину множества (V \ S).
В) Если длины всех ребер в графе попарно различны, то дерево кратчайших путей из заданной вершины единственно.

Ответ:

---