Алгоритм Флойда (поиск всех кратчайших путей в графе)

Алгоритм Флойда является одним из методов поиска кратчайших путей в графе. В отличии от алгоритма Дейкстры, который позволяет при доведении до конца построить ориентированное дерево кратчайших путей от некоторой вершины, метод Флойда позволяет найти длины всех кратчайших путей в графе.…

Главный центр

Главный центр — это произвольная вершина х с минимальным среди всех вершин значением МВД(х) -максимальное расстояние вершина-дуга, т. е. главным центром является такая вершина х, что расстояние от х до наиболее удаленной точки на дугах графа минимально. МВД(x)=min{МВД(i)} Для накождения…

Центр графа

Вспомним, что центром является любая вершина х с наименьшим значением МВВ(х) (макимальное расстояние вершина-вершина), т. е. центр — это любая вершина х, такая, что расстояние от нее до наиболее отдаленной вершины минимально. МВВ(х) =min{МВВ(i)} Центр отыскивается как один из элементов…

Пример применения алгоритма Дейкстры

Необходимо найти все кратчайшие пути от вершины №1 для графа, представленого на рисунке Составим матрицу длин кратчайших дуг для данного графа. ∞ 10 18 8 ∞ ∞ 10 ∞ 16 9 21 ∞ ∞ 16 ∞ ∞ 15 ∞ 7…

Абсолютная медиана графа

Абсолютная медиана — это такая точка на дуге графа, что сумма расстояний от нее до всех вершин графа минимальна. Теорема. В графе всегда существует вершина, являющаяся абсолютной медианой. Доказательство. Рассмотрим функцию, характеризующую расстояния точка — вершина d(f— (r, s), j)…

Алгоритм Данцига

Этот алгоритм  отличается от алгоритма Флойда последовательностью выполнения действий. Перенумеруем все вершины графа от 1 до n целыми числами и обозначим через di,jm длину пройденного пути из i в j где в качестве промежуточных использованы первые m вершин графа. Матрица…

Линейная корреляция. Нормальная корреляция

Корреляция Корреляционный момент и коэффициент корреляции Коррелированность и зависимость случайных величин Нормальный закон распределения на плоскости Линейная регрессия. Прямые линии среднеквадратической регрессии Линейная корреляция. Нормальная корреляция Коэффициент корреляции Пирсона Коэффициент корреляции Пирсона: пример решения задачи Коэффициент ранговой корреляции Спирмена Коэффициент…

Нормальный закон распределения на плоскости

Корреляция Корреляционный момент и коэффициент корреляции Коррелированность и зависимость случайных величин Нормальный закон распределения на плоскости Линейная регрессия. Прямые линии среднеквадратической регрессии Линейная корреляция. Нормальная корреляция Коэффициент корреляции Пирсона Коэффициент корреляции Пирсона: пример решения задачи Коэффициент ранговой корреляции Спирмена Коэффициент…

Задача коммивояжера

Коммивояжеру требуется посетить каждый город в пределах конкретной зоны обслуживания и возвратиться домой. Не приходится и говорить, что коммивояжеру хотелось бы выбрать такой порядок обхода клиентов, при котором его путь был возможно короче. Таким образом, коммивояжер сталкивается с задачей поиска…

Метод искусственного базиса (Симплекс метод) – Пример 2

Целевая функция: 2x1-x2+7x3+11x4+5x5→min Условия: 2x1+5x3+x4+8x5=12 -3x1+6x2+2x3-2x4≤5 Приведем систему ограничений к каноническому виду, для этого необходимо неравенства преобразовать в равенства, с добавлением дополнительных переменных. Если в преобразуемом неравенстве стоит знак “≥”, то при переходе к равенству знаки всех его коэффициентов и…