Графы и орграфы

Уиспользуются:рыночных отношений двудольные графы, представляющие собой различные промышленные предприятия и рынки, на

которые поступают их товары; игры – вершина различные стадии игры, а дуги – возможные ходы; электрические цепи; химические соединения; головоломки; изучение и построение печатных схем; задачи теории расписания (последовательность работы станков); математические потоки в транспортных сетях.

Задача о соединении городов

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

Граф, вершины которого соответствует городам, а ребра – соединяющие их, железные дороги, должен быть деревом.

Задача о соединении

Следовательно,городовнужно найти алгоритм, определяющий из возможных nn-2, соединяющих эти города, требуется наименьшее количество рельсов, и известны расстояния между каждой парой городов.