Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия, Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
Последний раз редактировалось Alex Krylov 17.03.2024, 07:20, всего редактировалось 1 раз.
Если обратиться к самому 1-му куску кода Matlab, то смысл там такой.
Пусть - матрица смежности нашего графа. Эта матрица симметрична и имеет нулевую диагональ. Т.е. в этой матрице уникальных элементов. Пусть это элементы нижне-треугольной части матрицы, т.е. . Эту нижнетреугольную матрицу можно векторизовать и ввести сквознную линейную нумерацию: . Тогда элементу матрицы смежности соответсвует уникальный элемент с линейным индексом :
q = max(i,j);
k = min(i,j);
ind = (q^2-3*q)/2+k+1;
Т.е. "x" - в вышеприведенном коде Matlab это (построчно) векторизованная нижнетреугольная часть матрицы смежности с дополнительным добавочным (46-м) элементом в конце. Этот добавочный 46-й элемент должен быть равен сумме предыдущих 45 элементов:
Далее в виде СЛАУ формализуется система линейных ограничений, приведенных в условии задачи. Последняя строка матрицы A (имеющая вид [-ones(1,45), 1]) и последний нулевой элемент вектора s используются для формализации вышеприведенного условия:
Spinv = S.'; fori=1:size(S,1)
Spinv(i,i)=1/Spinv(i,i); end
pinvA = V*Spinv*U.';% псевдообратная матрица Мура-Пенроуза
sol=pinvA*s;
sol(end) %Общее решение x неоднородной СЛАУ A*x=s имеет вид % x = pinvA*s + null(A)*c; % где null(A) - базис нуль-пространства матрицы A % c - вектор-столбец произвольных коэффициентов.
Замечаем, что у всех векторов, образующих базис нуль-пространства, последний элемент равен НУЛЮ! Т.е. вклад нуль-пространства в общее решение x(end) равен нулю. Т.е. сумма уникальных элементов матрицы смежности определяется только частным решением СЛАУ и не зависит от ядра A.
Alex Krylov
Re: Задача из теории графов
19.03.2024, 14:10
Можно кстати говоря эту задачу решать через исключение по Гауссу, т.е. через LU-разложение. Это фактически символьный метод.