Понятие о графе. Способы задания, достижимость и обратная достижимость вершин графа. Разбиение графа на подграфы. Решение задачи о максимальном потоке в графе на основе линейного программирования. Кратчайший остов графа. Задача о наименьшем покрытии.
Аннотация к работе
Граф геометрически представляет собой множество точек, соединенных линиями. Множество точек или вершин х1,х2,…xn графа G обозначим через Х, а множество линий d1,d2,…dm, соединяющих между собой эти вершины - символом А. Если соединяющиеся линии из множества А ориентированы, что обычно показывается стрелкой, то они называются дугами и граф с такими линиями называется ориентированным графом. Дуга такого графа задается упорядоченной парой, состоящей из начальной и конечной вершин, ее направление предполагается заданным от первой вершины ко второй. Граф G можно считать заданным, если даны множество его вершин Х и способ отображения Г множества Х в Х, т.е.При исследовании и оптимизации дискретных систем на графовых моделях часто возникает вопрос, существует ли путь от вершины xi к вершине xj. Если такой путь существует, то говорят, что вершина xj достижима из вершины xi. В ряде случаев необходимо определить достижимость за конечное число шагов вершины xj из вершины xi, т.е. достижимость только на таких путях, длины которых не превосходят заданной величины. Обозначим через QM(xi) множество таких вершин графа, что из любой вершины этого множества можно достигнуть вершины xi. Поскольку из соотношений dij ? 0, djk ? 0 следует существование путей длиной 2 из вершины xi к вершине xk, проходящих через вершину xj, то d(2)ik равно числу путей, идущих из xi в xk.В данной главе рассматриваются графовые модели [4,5] для оптимизации транспортных сетей и потоков, решения задач календарного планирования, задач о назначениях и других задач дискретной оптимизации. Те вершины, для которых D(i) > 0, называются источниками, вершины, для которых D(i) <0 - стоками, остальные - нейтральными. В отношении любой вершины j поступаем аналогично: если ее пометка вида (i , ej), то заменяем dij на (djt et), если ее пометка вида (j-, ej), то заменяем dji на (dji - et) и переходим к вершине i. 3.3) с одним истоком (вершина 1) и одним стоком (вершина 4), на которой заданы пропускные способности дуг c1=11, с2=7, с3=5, с4=8. В конечном многомерном графе каждой дуге поставлено в соответствие число Сі1,i2,,,il,m1,m2,,ml, называемое длиной дуги из вершины xi1,i2,,il в вершину xm1,m2,,ml.