Задание 9.
Выяснить наличие или отсутствие моста в графе, используя «хордовый» алгоритм.
Каркас – суграф, являющийся деревом (связным ациклическим графом).
Мост – ребро, при удалении которого число компонентов связности увеличивается
-
Возьмем каркас, состоящий из следующих рёбер:
{Х1,X2,X3,X4,X5,X6,X7,X8, X9,X10,X11,X12,X13,X14,X15} .
-
Рёбра, не вошедшие в каркас, являются хордами.
-
Перебираем все хорды и смотрим, образуют ли они цикл с рёбрами каркаса.
T(X16) = {X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16}.
T(X17) = {X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X17}.
T(X18) = {X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X18}.
T(X19) = {X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X19}.
T(X20) = {X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X20}.
-
Если перебрав все хорды, мы видим, что какие-либо хорды не вошли ни в один цикл, то они являются мостом.
-
Т.к. у нас все хорды, входят в какой либо цикл, то делаем вывод: МОСТОВ НЕТ.
Ответ: мостов нет.
Задание 12.
Привести пример реальной системы для задания 4.
Алгоритм Краскала, можно рассмотреть на примере работы крупного магазина. Из многочисленных фирм, директор выбрал всего 16 с которыми хотел бы сотрудничать и считает, что их продукт производства будет пользоваться спросом. Все 16 фирм надо объехать за один день. Безусловно, директор хочет выполнить работу с меньшими затратами.
Так как у нас в задании взвешенный граф, зная путь с АЗС с самыми низкими ценами, магазин получит выгоду в связи с наименьшими затратами на доставку товара с фирм.
А также этот метод можно рассмотреть на примере туриста, который с меньшими затратами хочет осмотреть достопримечательности.
Задание 14.
Найти диаметр, радиус и центры графа, заданного списком рёбер:
|
1 |
1 |
2 |
2 |
3 |
4 |
4 |
4 |
5 |
6 |
6 |
7 |
|
2 |
4 |
3 |
7 |
4 |
5 |
6 |
7 |
6 |
7 |
8 |
8 |
Постановка:
Диаметром d(G) связного графа, называется максимальное возможное расстояние между любыми двумя его вершинами.
Центром графа G называется такая вершина v, что максимальное расстояние между v и любой другой вершиной является наименьшим из всех возможных. Это расстояние называется Радиусом графа.
Центр
– вершина, где 
достигает минимума.
Решение.
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
|
1 |
|
1 |
2 |
1 |
2 |
2 |
2 |
3 |
3 |
|
2 |
1 |
|
1 |
2 |
3 |
2 |
1 |
2 |
3 |
|
3 |
2 |
1 |
|
1 |
2 |
2 |
2 |
3 |
3 |
|
4 |
1 |
2 |
1 |
|
1 |
1 |
1 |
2 |
2 |
|
5 |
2 |
3 |
2 |
1 |
|
1 |
2 |
2 |
3 |
|
6 |
2 |
2 |
2 |
1 |
1 |
|
1 |
1 |
2 |
|
7 |
2 |
1 |
2 |
1 |
2 |
1 |
|
1 |
2 |
|
8 |
3 |
2 |
3 |
2 |
2 |
1 |
1 |
|
3 |
r₀(G)=
min r(c) =2
δ(G)= max r(c) =3
С1 =
4 ; C2
= 6 ; C3
= 7
Ответ: радиус равен 2, диаметр равен 3, центры графа равны 4, 6, 7.