Элементы теории графов

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

Граф – совокупность вершин и ребер – универсальное средство наглядного представления достаточно разнообразных задач (рис. 4.1а).

Рис. 4.1

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

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

Каждую вершину сети нумеруют порядковым номером. Начальную (“1”) вершину называют “ источником ”, конечную – “стоком ” в описании движения потоков.

Дугу (рис. 4.2) обозначают двойной индексацией 1–2; 3–4 и т.д. В общем случае дугу обозначают “ i – j ”, где i – номер вершины, из которой исходит дуга; j – номер вершины, в которую входит дуга. Каждая дуга имеет свою характеристику: t_ij – продолжительность движения по дуге i – j; c_ij – стоимость перемещения; d_ij – пропускная способность дуги и т.д.

Рис. 4.2

Зная топологию сети и ее параметры можно решать самые разнообразные часто встречающиеся задачи оптимизации.