Главная » Учебно-методические материалы » ВЫСШАЯ МАТЕМАТИКА, ТВ и МС, МАТ. МЕТОДЫ » Математические методы. Попова Н.В.

Тема 2.14. Методы решения сетевых задач
22.12.2011, 14:29

Нахождение минимального остова в графе

Алгоритм решения

  1. Упорядочить ребра графа по возростанию весов;
  2. Выбрать ребро с минимальным весом, не образующее цикл с ранее выбранными ребрами. Занести выбранное ребро в список ребер строящегося остова;
  3. Проверить, все ли вершины графа вошли в постоенный остов. Если нет, то выполнить пункт 2.

Продемонстрируем приведенный выше алгоритм на примере.

Пример 2.14.1

Нахождение кратчайшего пути в графе

Пусть дан граф, дугам которого приписаны веса. Задача о нахождении кратчайшего пути состоит в нахождении кратчайшего пути от заданной начальной вершины до заданной конечной вершины, при условии, что такой путь существует.

Можно дать много практических интерпретаций задачи о кратчайших путях. Например, вершины могут соответствовать городам и каждая дуга - некоторому пути, длина которого представлена весом дуги. Мы ищем кратчайшие пути между городами. Вес дуги может соответствовать стоимости (или времени) передачи информации между вершинами. В этом случае мы ищем самый дешевый (или самый скорый).

Данная задача может быть разбита на две:

  1. для начальной заданной вершины найти все кратчайшие пути от этой вершины к другим;
  2. найти кратчайшие пути между всеми парами вершин.

Рассмотрим алгоритм решения для задачи первого типа:

Необходимо найти путь от s - начальной вершины до t - конечной вершины. Каждой вершине присваиваем пометки I(Xi).

  1. I(s) = 0, I(Xi) равно бесконечности для всех Хi не равных s и считать эти пометки временными. Положить р = s.
  2. Для всех Хi, пренадлежащих Г(р) и пометки которых временны, изменить пометки по следующему правилу: 
    I(Xi) = min[I(Xi), I(p) + c(p, Xi)]
  3. среди всех вершин с временными пометками найти такую, для которой I(Xi*) = min[I(Xi)]
  4. считать пометку вешины Хi* постоянной и положить р = Хi*.
  5. если р = t, то I(р) является длинной кратчайшего пути, если нет, перейти к шагу 2.

Как только все пометки расставлены, кратчайшие пути получают, используя состношение I(Xi') + c(Xi',Xi) = I(Xi) (1). Поясним работу данного алгоритма на примере.

Пример 2.14.2

Для решения задачи второго типа можно применять данный алгоритм для каждой вершины.

http://matmetod-popova.narod.ru/




БАНКОВСКОЕ ДЕЛО
БУХГАЛТЕРСКИЙ УЧЕТ
БЮДЖЕТ И БЮДЖЕТНАЯ СИСТЕМА РФ
ВЫСШАЯ МАТЕМАТИКА, ТВ и МС, МАТ. МЕТОДЫ
ГУМАНИТАРНЫЕ НАУКИ
ДОКУМЕНТОВЕДЕНИЕ И ДЕЛОПРОИЗВОДСТВО
ДРУГИЕ ЭКОНОМИЧЕСКИЕ ДИСЦИПЛИНЫ
ЕСТЕСТВЕННЫЕ ДИСЦИПЛИНЫ
ИНВЕСТИЦИИ
ИССЛЕДОВАНИЕ СИСТЕМ УПРАВЛЕНИЯ
МАРКЕТИНГ
МЕНЕДЖМЕНТ
МЕТ. РЕКОМЕНДАЦИИ, ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ
МИРОВАЯ ЭКОНОМИКА И МЭО
НАЛОГИ И НАЛОГООБЛОЖЕНИЕ
ПЛАНИРОВАНИЕ И ПРОГНОЗИРОВАНИЕ
РАЗРАБОТКА УПРАВЛЕНЧЕСКИХ РЕШЕНИЙ
РЫНОК ЦЕННЫХ БУМАГ
СТАТИСТИКА
ТЕХНИЧЕСКИЕ ДИСЦИПЛИНЫ
УПРАВЛЕНИЕ ПЕРСОНАЛОМ
УЧЕБНИКИ, ЛЕКЦИИ, ШПАРГАЛКИ (СКАЧАТЬ)
ФИНАНСОВЫЙ МЕНЕДЖМЕНТ
ФИНАНСЫ, ДЕНЕЖНОЕ ОБРАЩЕНИЕ И КРЕДИТ
ЦЕНЫ И ЦЕНООБРАЗОВАНИЕ
ЭКОНОМИКА
ЭКОНОМИКА, ОРГ-ЦИЯ И УПР-НИЕ ПРЕДПРИЯТИЕМ
ЭКОНОМИКА И СОЦИОЛОГИЯ ТРУДА
ЭКОНОМИЧЕСКАЯ ТЕОРИЯ (МИКРО-, МАКРО)
ЭКОНОМИЧЕСКИЙ АНАЛИЗ
ЭКОНОМЕТРИКА
ЮРИСПРУДЕНЦИЯ