Рассмотрите граф, вершины которого - абоненты 1-9, связанные линиями связи; веса на ребрах - оценка потери конфиденциальной информации при ее передаче по этой линии связи. Матричная модель графа: Найдите минимальное остовное дерево графа. Дайте

1. Выбираем ребра {1;2}, {3;5}, {8,9}, так как они имеют минимальный вес 3. При этом не возникает ни одного цикла. Далее выбираем ребра {2;5}, {4,7} с весом 4. Остаются несоединенной вершина 6. Выбираем ребро {3,6} с весом 5, чтобы присоединить вершину 6. Далее выбирая ребра {6;8} и {1;4} с весом 5 мы находим минимальное остовное дерево, так как количество выбранных вершин (1, 2, 3, 4, 5, 6, 7, 8, 9) = 9 соответствует количеству вершин графа. Минимальное остовное дерево графа: {1;2}, {3;5}, {8,9}, {2;5}, {4,7}, {3,6}, {6;8}, {1;4}. 2. При таком соединении абонентов линиями связи оценка ...