А.И. Орлов       
Основы теории принятия решениий       
Учебное пособие. Москва, 2002.

9.Теория графов и оптимизация
    

Один из разделов дискретной математики, часто используемый при принятии решений - теория графов (см., например, учебное пособие [8]). Граф - это совокупность точек, называемых вершинами графа, некоторые из которых соединены дугами. Примеры графов приведены на рис.5.

Рис.5. Примеры графов.

На только что введенное понятие графа "навешиваются" новые свойства. Исходному объекту приписывают новые качества. Например, вводится и используется понятие ориентированного графа. В таком графе дуги имеют стрелки, направленные от одной вершины к другой. Примеры ориентированных графов даны на рис.6.

Рис.6. Примеры ориентированных графов.

Ориентированный граф был бы полезен, например, для иллюстрации организации перевозок в транспортной задаче. В экономике дугам ориентированного или обычного графа часто приписывают числа, например, стоимость проезда или перевозки груза из пункта А (начальная вершина дуги) в пункт Б (конечная вершина дуги).

Рассмотрим несколько типичных задач принятия решений, связанных с оптимизацией на графах.

Предыдущая страница | Оглавление | Следующая страница