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

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

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

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

Условие

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

Нужно полное решение этой работы?

Решение

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

Определим веса ребер заданного графа.
Ребро 0-1 0-2 0-3 0-4 0-5 1-6 2-6 3-6 3-10
Вес 4 7 12 15 18 16 11 6 20
Ребро 4-11 4-12 5-12 6-7 6-8 6-9 7-10 8-10 9-10 11-12
Вес 4 13 8 15 9 19 10 5 14 17
Формируем очередь из ребер графа в порядке возрастания их весов:
Q=(0-1,4-11,8-10,3-6,0-2,5-12,6-8,7-10,2-6,0-3,4-12,9-10,0-4,1-6,11-12,0-5,6-9,3-10),
Выбираем первое ребро и помещаем его в множество T={0-1} - это ребра строящегося остова. Строим первый букет из вершин выбранных ребер: B1={0,1}. Имеем очередь
Q=(4-11,8-10,3-6,0-2,5-12,6-8,7-10,2-6,0-3,4-12,9-10,0-4,1-6,11-12,0-5,6-9,3-10),
Выбираем ребро 4-11, помещаем в множество T={0-1,4-11}, формируем букет B2={4,11}. Итак, имеем букеты B1={),1}, B2={4,11}. Остаток очереди
Q=(8-10,3-6,0-2,5-12,6-8,7-10,2-6,0-3,4-12,9-10,0-4,1-6,11-12,0-5,6-9,3-10),
Выбираем ребро 8-10, получаем T={0-1,4-11,8-10}, B3={8,10}. Имеем букеты B1={0,1}, B2={4,11}, B3={8,10}. Очередь
Q=(3-6,0-2,5-12,6-8,7-10,2-6,0-3,4-12,9-10,0-4,1-6,11-12,0-5,6-9,3-10),
Выбираем ребро 3-6, получаем T={0-1,4-11,8-10,3-6}. Новый букет B4={3,6}. Множество букетов B1={0,1}, B2={4,11}, B3={8,10}, B4={3,6} . Новая очередь
Q=(0-2,5-12,6-8,7-10,2-6,0-3,4-12,9-10,0-4,1-6,11-12,0-5,6-9,3-10),
Выбираем ребро 0-2. Одна концевая вершина этого ребра входит в букет B1. Помещаем это ребро в множество T={0-1,4-11,8-10,3-6,0-2}, а вершину 2 включаем в букет B1. Тогда имеем букеты B1={0,1,2}, B2={4,11}, B3={8,10}, B4={3,6} и новую очередь
Q=(5-12,6-8,7-10,2-6,0-3,4-12,9-10,0-4,1-6,11-12,0-5,6-9,3-10).
Выбираем ребро 5-12. Формируем T={0-1,4-11,8-10,3-6,0-2,5-12} и новый букет B5={5,12}. Тогда имеем букеты B1={0,1,2}, B2={4,11}, B3={8,10}, B4={3,6}, B5={5,12} и новую очередь
Q=(6-8,7-10,2-6,0-3,4-12,9-10,0-4,1-6,11-12,0-5,6-9,3-10).
Выбираем ребро 6-8. Концевые вершины ребра входят в два разных букета B3={8,10}, B4={3,6}. Объединяем эти букеты в букет B3={3,6,8,10} ребро 6-8 присоединяем к множеству T={0-1,4-11,8-10,3-6,0-2,5-12,6-8} и тогда имеем букеты B1={0,1,2}, B2={4,11}, B3={3,6,8,10}, B5={5,12} и имеем очередь
Q=(7-10,2-6,0-3,4-12,9-10,0-4,1-6,11-12,0-5,6-9,3-10).
Выбираем ребро 7-10. Оно имеет одну общую вершину 10 с букетом B3. Поэтому включаем вершину 7 в букет B3={3,6,7,8,10} и ребро 7-10 присоединяем к множеству T={0-1,4-11,8-10,3-6,0-2,5-12,6-8,7-10}

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

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

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

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

Условие

Нужно полное решение этой работы?

Решение

Найти общее решение дифференциального уравнения первого порядка

Решить систему линейных уравнений (СЛУ) по методу Крамера

Фабрика изготовляет два вида красок