Здравствуйте, Посетитель - 395932!
a) Алгоритм Краскала
Вначале текущее множество рёбер устанавливается пустым. Затем, пока это возможно, проводится следующая операция: из всех рёбер, добавление которых к уже имеющемуся множеству не вызовет появление в нём цикла, выбирается ребро минимального веса и добавляется к уже имеющемуся множеству. Когда таких рёбер больше нет, алгоритм завершён. Подграф данного графа, содержащий все его вершины и найденное множество рёбер, является его остовным деревом минимального веса.
В графе имеется 2 ребра весом 1 и 2 ребра весом 2. Добавляем их, при этом в подграфе нет циклов. Из двух ребер веса 3 ребро между 1 и 5 не вызывает появления цикла. Добавим его. Добавление любого другого ребра вызывает появления цикла. Алгоритм завершен.
Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.
Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.
Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u, назовем соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.
3
Коэффициент при a - x в степени 2, y^2 в степени 2, z в степени 2, следовательно, он равен 6!/(2!)^3=90
Учитывая коэффициенты при y и z, 90*4
2*5
2=36000
b задан неправильно, степерь при y должна быть четной
c - y^2 в степени 3, z в степени 2, следовательно, он равен
Учитывая коэффициенты при y и z, 15*4
2*5
4=150000