Дан граф G=(V E). Постройте список смежности для данного оргафа
.pdf
Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥
Дан граф G=(V, E):
1. Постройте список смежности для данного оргафа;
2. Определите центр Графа
3. Определите число деревьев в глубинном остовном лесу (перебор вершин производить строго в лексикографическом порядке)
4. Определите число поперечных и число прямых дуг в глубинном остовном лесу (перебор вершин производить строго в лексикографическом порядке)
5. Какова высота дерева, построенного обходом в ширину, начиная с вершины e (перебор вершин производить строго в лексикографическом порядке).
6. Определите, чему будет равно значение P[3] в алгоритме Дейкстры, если источником является вершина e (узел а – 1-ый в нумерации узлов, … узел e – 5-ый)
7. Определите, чему будет равна 1-ая строка массива A (кратчайших расстояний) в алгоритме Флойда после k=3
8. Чему равна стоимость остовного дерева минимальной стоимости для данного графа (граф рассматривать как неориентированный)
9. Сколько сильно связных компонент в графе?
10. Какая вершина будет добавлена во множество U четвертой по счету в алгоритме Прима при построении остовного дерева минимальной стоимости (перебор вершин производить строго в лексикографическом порядке) (граф рассматривать как неориентированный)
11. Какая дуга будет добавлена в в остовное дерево минимальной стоимости третьей по счету в алгоритме Крускала (перебор вершин производить строго в лексикографическом порядке) (граф рассматривать как неориентированный)
12. Определив обратные дуги в глубинном остовном лесу, постройте граф G2 на основе исходного Графа, удалив найденные обратные дуги. Для графа G2 вычислите матрицу транзитивного замыкания.
13. Рассмотрим граф G2 в качестве сети N2, задав источник и сток изобразите сеть N2(G2, c), где в качестве пропускных способностей дуг положите значение веса соответствующей дуги графа G2.
14. Для сети N2 определите её максимальный поток и найдите все минимальные разрезы.
15. Определите хроматическое число орграфа
Нужно полное решение этой работы?
Решение
1. a: b, c, d;
b: c, d;
c: e;
d: c;
e: a, d;
2. E(a)=2;E(b)=3; E(c)=3; E(d)=4; E(e)=2 – эксцентриситеты вершин;
{a;e} – центр графа
3. Всего два дерева в глубинном остовном лесу
4. Поперечных рёбер нет; прямых рёбер нет
5. Высота равна 3;
6. e-a-b-d-c – минимальный путь
P[3]=4
7. a b c d e
a - 2 10 7 ∞
b ∞ - 6 2 ∞
c ∞ ∞ - ∞ 5
d ∞ ∞ 1 - ∞
e 3 ∞ ∞ 12 -
Составим матрицу D0 – матрица расстояний рёбер и матрицу S0.
k=0
D0 a b c d e
S0 a b c d e
a - 2 10 7 ∞
a - 2 3 4 5
b ∞ - 6 2 ∞
b 1 - 3 4 5
c ∞ ∞ - ∞ 5
c 1 2 - 4 5
d ∞ ∞ 1 - ∞
d 1 2 3 - 5
e 3 ∞ ∞ 12 -
e 1 2 3 4 -
k=1. Выделяем строку и столбец с номером k в предыдущих матрицах. Выделим красным те элементы матрицы Dk-1 и Sk-1, где dij>dki+djk. В матрице Dk заменяем красные элементы на dki+djk, в Sk на k
. Повторяем аналогичные действия для k+1 до k=n – число вершин.
D1 a b c d e
S1 a b c d e
a - 2 10 7 ∞
a - 2 3 4 5
b ∞ - 6 2 ∞
b 1 - 3 4 5
c ∞ ∞ - ∞ 5
c 1 2 - 4 5
d ∞ ∞ 1 - ∞
d 1 2 3 - 5
e 3 5 13 10 -
e 1 1 1 1 -
k=2
D2 a b c d e
S2 a b c d e
a - 2 8 4 ∞
a - 2 2 2 5
b ∞ - 6 2 ∞
b 1 - 3 4 5
c ∞ ∞ - ∞ 5
c 1 2 - 4 5
d ∞ ∞ 1 - ∞
d 1 2 3 - 5
e 3 5 11 7 -
e 1 1 2 2 -
k=3
D3 a b c d e
S3 a b c d e
a - 2 8 4 13
a - 2 2 2 3
b ∞ - 6 2 11
b 1 - 3 4 3
c ∞ ∞ - ∞ 5
c 1 2 - 4 3
d ∞ ∞ 1 - 6
d 1 2 3 - 5
e 3 5 11 7 -
e 1 1 2 2 -
В первой строке будут 2;8;4;13
8. Используем жадный алгоритм для построения остовного дерева минимальной стоимости, убирая поочерёдно рёбра с наибольшим весом;
Минимальная стоимость остова равна 8;
9
Задать вопрос
на новый заказ в Автор24.
