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

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

Типовые задачи теории графов и их приложения:

- задача о кратчайшей цепи: замена оборудования; составление расписания движения транспортных средств; размещение пунктов скорой помощи; размещение ретрансляционных и телефонных станций;

- задача о максимальном потоке: анализ пропускной способности коммуникационной сети; организация движения в динамической сети; оптимальное назначение интенсивностей выполнения работ; синтез двухполюсной сети с заданной структурной надежностью; задача о распределении работ;

- задача об упаковках и покрытиях: оптимизация структуры ПЗУ; размещение диспетчерских пунктов городской транспортной сети;

- раскраска в графах: распределение памяти в ЭВМ; проектирование сетей теле- и радиовещания;

- связность графов и сетей: проектирование кратчайшей коммуникационной сети; синтез структурно-надежной сети циркуляционной связи; анализ надежности стохастических сетей связи;

- изоморфизм графов и сетей: структурный синтез линейных избирательных цепей; автоматизация контроля при проектировании БИС;

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

- автоморфизм графов: конструктивное перечисление структурных изомеров для производных органических соединений; синтез тестов цифровых устройств.

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

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

Сетью Т называют пару объектов (G, c), где G=(V, E) - произвольный ориентированный граф (или неориентированный граф), а c - функция, которая каждой дуге (u,v) ставит в соответствие неотрицательное вещественное число c(u,v), называемое пропускной способностью этой дуги (вес дуги).

Источником называют некоторую вершину сети, из которой достижимы все остальные вершины. В более широкой трактовке источником называют вершину сети, которая является начальной для некоторой задачи, например, начальной вершиной при поиске кратчайшего пути или при поиске максимального потока. Стоком называют некоторую вершину, которая достижима из всех остальных вершин. В более широкой трактовке стоком называют вершину, которая является конечной для некоторой задачи, например, конечной вершиной при поиске кратчайшего пути или при поиске максимального потока. Потоком из s в t (где s - источник, t - сток, s не равно t) в сети S называют произвольную функцию f: E→R, для которой выполняются условия: 0 f(u,v) c(u,v) для каждой дуги (u,v) из E и Div(v)=0 для каждой вершины v из V\{s,t}. Величину Div(s) для потока f называют величиной потока f.

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

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