Для графа представленного на рис 20 задайте весовую функцию ребер и постройте остовное дерево минимального веса. Бесплатный доступ к контрольной работе

Реферат.Справочник
Контрольные работы по высшей математике
Для графа представленного на рис 20 задайте весовую функцию ребер и постройте остовное дерево минимального веса

Для графа представленного на рис 20 задайте весовую функцию ребер и постройте остовное дерево минимального веса .pdf

Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥

Условие

Для графа, представленного на рис. 20, задайте весовую функцию ребер и постройте остовное дерево минимального веса, полагая, что ребра имеют различные положительные целые веса. Минимальный вес ребра равен 8. Рис. 20. Связный неориентированный граф. .

Решение

Потяни, чтобы посмотреть

Зададим весовую функцию ребер, минимальный вес ребра равен 3, полагая, что ребра имеют различные положительные целые веса.
Вводим в дерево ребро минимального веса (v0,v1)=3
Выбираем ребро минимального веса смежное с вершинами (v0,v1) : (v1,v6)=4
Выбираем ребро минимального веса смежное с вершинами (v0,v1, v6) это (v6,v7)=5
Выбираем ребро минимального веса смежное с вершинами (v0,v1, v6,v7) это (v7,v10)=6
Выбираем ребро минимального веса смежное с вершинами (v0,v1, v6,v7,v10) это (v10,v3)=7
Выбираем ребро минимального веса смежное с вершинами (v0,v1, v6,v7,v10,v3) это (v10,v9)=8
Выбираем ребро минимального веса смежное с вершинами (v0,v1, v6,v7,v10,v3,v9) это (v10,v8)=9
Выбираем ребро минимального веса смежное с вершинами (v0,v1, v6,v7,v10,v3,v9,v8,) это (v2,v6)=13
Выбираем ребро минимального веса смежное с вершинами
(v0,v1, v6,v7,v10,v3,v9,v8,v3,v2) это (v0,v4)=15
Выбираем ребро минимального веса смежное с вершинами
(v0,v1, v6,v7,v10,v3,v9,v8,v3,v2,v4) это (v11,v4)=16
Выбираем ребро минимального веса смежное с вершинами
(v0,v1, v6,v7,v10,v3,v9,v8,v3,v2,v4, v11) это (v11,v12)=17
Выбираем ребро минимального веса смежное с вершинами
(v0,v1, v6,v7,v10,v3,v9,v8,v3,v2,v4, v11,v12) это (v12,v5)=18
Все вершины вошли в дерево, оно построено.
Остовное дерево минимального веса 18+17+16+15+13+9+8+7+6+5+4+3=121 построено

50% задачи недоступно для прочтения

Переходи в Кампус, регистрируйся и получай полное решение

Получить задачу