Теория графов: основные понятия

покрывающем дереве в графе;
задача о минимальном пути в графе;
задача нахождения максимального потока в сети .

между двумя соседними населенными пунктами (млн. рублей) равна значению весовой функции для каждого ребра. Разработаем такой проект, чтобы общая стоимость его реализации была минимальной, при этом из любого населенного пункта по построенной транспортной сети можно попасть в любой другой населенный пункт рассматриваемого района.

Excel

Таблица с исходными данными в режиме формул

Диалоговое окно мастера
Поиска решения

транспортной сети рассматриваемого района будет заключаться в построении автодорог между населенными пунктами 1 и 2, 2 и 3, 3 и 4, 3 и 6, 5 и 6, 5 и 7

в минимальное покрывающее дерево входят ребра (1, 2), (2, 3), (3, 4), (3, 6), (5, 6), (5, 7)

виде графа. Протяженность каждой дороги представлена весовыми коэффициентами. Определить кратчайший путь между точками А и D.

Весовая матрица смежности

Требуется определить такую последовательность вершин, по которым должна перемещаться единица груза, отправленная из вершины А, при которой стоимость транспортных расходов будет минимальна и груз попадет в вершину D. Так как транспортные расходы при перемещении груза из одной вершины в другую равны расстоянию между вершинами, то последовательность вершин, при которой транспортные расходы будут минимальными, определяет наикратчайший путь из вершины А в вершину D.

Транспортная матрица

Здесь X – означает запрет перевозки в данном направлении.