Оптимизационные задачи на графах

Расширения модели

Модель графа при описании конкретных объектов, процессов или явлений может быть расширена. Для этого используют следующие способы: следующим образом.

· ВВзвешивание дуг (ребер). Каждому ребру (дуге) графа приписывается число - – вес дуги (ребра). Вес может обозначатьопределять, например, расстояние между городами, если вершинам приписаны имена городов, а ребрам -– дороги между ними. Для описания взвешенного графа используется матрица смежности, в ячейках которой в ячейках записаны веса. Если особо не оговорено, то под взвешенным графом будем понимать такой граф.

· Взвешивание вершин. Аналогично дугам веса приписываются вершинам. Например, вершинам вершинами составлены представлены магазины и склады, тогда а веса вес вершины могут обозначать, например,определяет количество некоторого товара на складе или в магазине.

· Взвешивание дуг и/или вершин векторами. Взвешивание производится не числом, а набором чисел. Например, для дороги могут быть указаны расстояние, стоимость проезда, время в пути и т.д.

· В графе допускается между двумя вершинами несколько «параллельных» дуг (или рёбер). В этом случае говорят о кратных дугах (рёбрах), а такие графы называют мультиграфами. Для описания мультиграфов используются такие же таблицы, как и для простых графов, но в клетках записаны не 0 и 1, а кратность дуги.

· В графе используется не бинарное, а r-арное отношение, где r > 2. Такие графы называются гиперграфами. Для представления этих графов на плоскости вершины, которые относятся к одному ребру, объединяются замкнутыми линиями, как на рис. 3.3. Здесь граф имеет три ребра: (1, 2, 3), (1, 2, 4), (4, 5, 6). К таким графам приходят при описании логических сетей, когда элементы находятся в отношении, если они имеют полюса, связанные общей цепью.

Рис. 3.3.

Большое количество практических задач формулируются как задачи поиска фрагментов графа или каких-то его характеристик, причем существует множество вариантов решения. Каждое решение оценивается числом, и среди множества решений нужно найти такое, для которого оценка имеет экстремальное значение - минимальное или максимальное. Чаще всего в качестве оценок используется сумма весов дуг или ребер, входящих в решение, - тогда оценка называется аддитивной, или произведение весов - тогда говорят о мультипликативной оценке. Наиболее часто ограничиваются случаем, когда веса дуг являются неотрицательными целыми числами.