Графы основные понятия способы задания графов

Если порядок соединения вершин (хi xj) является не существенным, то граф называется не ориентированным (неорграф), а пара (хi xj) — ребра этого графа. Если порядок соединения вершин (хi xj) является существенным, то граф называется ориентированным (орграф), а пара (хi xj) — дуги этого графа.. Граф, в котором имеются и дуги и ребра называется смешанным .Любое ребро не орграфа можно заменить парой дуг. Пара вершин графа (хi xj) может соединяться 2 я и более ребрами (дугами одного направления). Такие ребра (дуги) называются кратными. Количество одинаковых ребер (дуг) называется кратностью соответствующего ребра (дуги). Две вершины графа называются смежными, если существует соединяющее их ребро (дуга). 2 ребра называются смежными, если они имеют общею вершину. Петлей называются ребра, с совпадающей начальной и конечной вершиной. Граф с петлями и кратными дугами называется псевдограф, граф без петель и с кратными дугами называется мультиграф.

Подграфом графа G (х,u) называется граф G1(х1,u1), в котором множество x1 является подмножеством X, u1 является подмножеством u. Оставным подграфом графа G называется граф, содержащий все вершины графа G. Порожденный подграф состоит из подмножества вершин X_s множества вершин исходного графа и всех таких дуг графа G, у которого конечные и начальные вершины принадлежат подмножеству X_s .

Число дуг, исходящих из вершины xi ориентированного графа называется полустепенью исхода, число дуг, входящих в вершину ориентированного графа – полустепенью захода. В неор. Графах число ребер инцидентных вершине называется степенью вершины хi.

Вершина, имеющая степень 0 — изолированной., а имеющая степень 1 — висячей.

Маршрут —в не орграфе: последовательность ребер, в которой начало каждого последующего ребра совпадает с концом предыдущего. В орграфе: последовательность дуг, в которой начало каждой последующей дуги совпадает с концом предыдущей. Цепь —незамкнутый маршрут, в котором все ребра различны. Цепь, в которой все вершины различны, называется простой цепью. Путь — ориентированный маршрут, в котором все дуги различны. Замкнутый путь —контур. Цикл—замкнутая цепь. Замкнутая про стая цепь -простой цикл. Способы задания графа:

— геометрический (рисунок) – матричный. Различают также:

— матицу смежности (размерность пхп, щ = 1, если вершиныХ1И Xj смежны)

— матрицу инцидентности (размерность nxm, bjj = 1, если вершинахi инцидентна ребру Uj [для неорграфа] или b= 1, если вершина xi начальная вершина дуги uij bij = -1, если вершина xi., конечная вершина дуги и uij [для орграфа])

Основные операции над графами:

— удаление вершины (при этом удаляются все инцидентные ребра) — удаление ребра (при этом его конечные вершины не удаляются)

— добавление ре бра (обратно удалению) — слияние вершин – все ребра становятся инцидентны одной вершине

— стягивание ребра (удаление ребра и слияние его вершин) — подразбиение ребра (из графа удаляется (хi xj) и добавляется 2 новых ребра:(хi х0 и(х0 xj), где х0 — новая вершина)

Основные типы графов:

— орграф и неорграф

— граф с петлями и кратными ребрами называется псевдографом. Граф с кратными ребрами и без петель — мульти граф. Граф без петель и ребер- простой.

— граф называется взвешенным, если его ребрам (х^ xj) ставится в соответствие веса. Граф называется связным, если любые 2 вершины соединены маршрутом.

— граф называется ациклическим, если он не содержит циклов.

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

— граф называется регулярным степени к или однородным , если степени всех его вершин одинаковы и равны к.Число ребер при этом m=0.5*n*k.

— граф называется полным, если все его вершины смежные. К» —полный граф, содержащий п вершин.

— граф (X, U) называется двудольным, если множество его вершин X можно разделить на 2 подмножества Х1 Х2 таким образом, что каждое ребро графа имеет 1 конечную вершину в множестве X1, а другую —в Х2. Множества X1, Х2 — доли. Если любые 2 вершины графа из разных долей смежные, граф называется полным двудольным графом.

— граф называется эйлеровым, если он содержит эйлеров цикл —цикл, проходящий через каждое ребро графа 1 раз.

— граф называется гамипьтоновым, если он содержит гамипьтонов цикл — цикл, проходящий через каждую вершину 1 раз

— граф называется планарным, если его можно разложить на плоскости таким образом, чтобы ребра не пересекались в точке, отличной от вершины. Если он уже так расположен, то он назьшается плоским:

Укладок планерного графа на плоскости может быть несколько

— два графа G1, G2 изоморфны, если существует взаимно однозначное отображение между множествами их вершин, сохраняющее смежность. Для орграфа должна сохраняться ориентация дуг. Для псевдографов должна сохраняться кратность дуг. Изоморфные графы могут быть получены один из другого путем перенумерации вершин (пленарные и плоские графы).

125 Достижимость и связность в графе. Определение компонент связности в неорграфах и сильных компонент в орграфах.

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

Компоненты связности неорграфа называют его максимально связный подграф, т.е. подграф, не содержащийся ни в каком другом

связном подграфе этого графа. Сильные компоненты орграфа называют максимально сильный связный подграф.

Матрицей достижимости орграфа с n вершинами называется квадратная матрица R порядка n, элементы которой определяются

следующим образом , Xj достижима из xi(b противном случае, = О, ц= 1).

Матрицей контр достижимости орграфа с n вершинами называется квадратная матрица Q порядка n, элементы которой определяются: xi достижима из Xj (в противном случае, = 0, qj= 1).

МатрицыR, Q, S связаны: S=Q *R .Qтранспонированная матрица R

Матрицей сильной связности орграфа с п вершинами называется квадратная матрица S порядка п, элементы которой определяются

следующим образом Sij= 1, Хj xi— взаимно достижимы (в противном случае, = 0).

После определения матрицы S, по ней можно указать сильные компоненты графа: если Ху xi принадлежат одной сильной компоненте, то Sjj = 1, при этом строки (столбцы) соответствующие данным вершинам в матрице S одинаковы. Для не орграф а матрицы S, R, Qсовпадают.

Числом вершинной связности графа б (а) называется наименьшее число вершин, при удалении которых граф становиться не связным. Числом реберной связности графа а(а) называется наименьшее число ребер, при удалении которых граф становиться не связным. Вершина xi -точка сочленения, если при ее удалении связность графа нарушается. Ребро графа называется мостом, если его удаление приводит к нарушению связности.

127 Деревья. Построение деревьев с использованием поиска в глубину и в ширину. Алгоритмы Краскала и Прима построения кратчайшего остова графа.

Деревом называется связный ациклический граф. Ориентированным деревом называется орграф без циклов, в котором существует вершина x₀, из которой имеется единственный путь в любую другую вершину графа. Деревом графа G называется его связный ациклический подграф. Остовым деревом графа называется дерево графа G, содержащее все вершины этого графа (остов T).

Ребра остового дерева называются ветвями, а ребра графа G, не принадлежащие остовому дереву, называются хордами. K – деревом называется ациклический граф, состоящий из k-компонентов связи.

Остов существует в любом графе, при чем он может быть определен не единственным способом.

Для остового дерева T справедливо:

— T – связный граф, но он утрачивает связность при удалении хотя бы одного ребра

— T – ациклический граф, но добавление к нему хотя бы одного ребра приводит к появлению цикла

— любые 2 вершины остовного дерева связаны единственной простой цепью

— остовое дерево содержит, по крайней мере, 2 висячие вершины

— число ребер остового дерева на единицу меньше числа его вершин.

Для построения остового дерева связного графа могут быть использованы 2 стратегии: поиск в глубину и поиск в ширину.

При поиске в глубину построение остова начинается с произвольной вершины графа x₀. Затем выбирается вершина смежная с ней, например x₁ и т.д. Если на k-ом шаге поиска для вершины x_k существуют смежные вершины, которые не были еще просмотрены, происходит переход в одну из этих вершин, в противном случае, происходит возврат в предыдущею вершину x_k-1 и поиск продолжается от нее. В процессе поиска вершины соединяются ребрами. Поиск заканчивается, когда будут просмотрены все вершины графа и произведен возврат в x₀.

Поиск в ширину отличается от поиска в глубину тем, что на каждом шаге просматривается не одна, а все вершины смежные с текущей.

Кратчайшим остовом взвешенного графа называется остов, у которого сумма всех весов ребер наименьшая. Для построения кратчайшего остового дерева взвешенного графа могут быть использованы алгоритм Краскала или алгоритм Прима.

Алгоритм Краскала заключается в следующем: на начальном этапе из всех ребер графа G выбирается и включается в остов ребро U₁, имеющее наименьший вес. На каждом последующем i-ом шаге из еще не включенных в остов ребер выбирается ребро, имеющее наименьший вес и не составляющее цикл с уже имеющимися ребрами. Процесс построения остового дерева завершается, когда в него будет включено n-1 ребро (n – количество вершин графа G).

Алгоритм Прима отличается от алгоритма Краскала тем, что в процессе построения необходимо следить за связностью строящегося дерева. При этом, если дерево T_i построено, то новое ребро выбирается не из всех оставшихся ребер графа, а только из тех, которые соединяют дерево T_i с вершинами, не включенными в него.

Источник

Теория графов. Основные понятия и виды графов

О чем эта статья:

Теория графов

В переводе с греческого граф — «пишу», «описываю». В современном мире граф описывает отношения. И наоборот: любое отношение можно описать в виде графа.

Теория графов — обширный раздел дискретной математики, в котором системно изучают свойства графов.

Теория графов широко применяется в решении экономических и управленческих задач, в программировании, химии, конструировании и изучении электрических цепей, коммуникации, психологии, социологии, лингвистике и в других областях.

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

Давайте на примере.

Пусть множество A = — это множество людей, и каждый элемент отображен в виде точки. Множество B = — множество связок (прямых, дуг или отрезков).

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

Число знакомых у одних людей может отличаться от числа знакомых у других людей, некоторые могут вовсе не быть знакомы (такие элементы будут точками, не соединёнными ни с какой другой). Так получился граф:

В данном случае точки — это вершины графа, а связки — рёбра графа.

Теория графов не учитывает конкретную природу множеств A и B. Существует большое количество разных задач, при решении которых можно временно забыть о содержании множеств и их элементов. Эта специфика не отражается на ходе решения задачи.

Например, вопрос в задаче стоит так: можно ли из точки A добраться до точки E, если двигаться только по соединяющим точки линиям. Когда задача решена, мы получаем решение, верное для любого содержания, которое можно смоделировать в виде графа.

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

Графом называется система объектов произвольной природы (вершин) и связок (ребер), соединяющих некоторые пары этих объектов.

Пусть V — (непустое) множество вершин, элементы v ∈ V — вершины. Граф G = G(V) с множеством вершин V есть некоторое семейство пар вида: e = (a, b), где a, b ∈ V, указывающих, какие вершины остаются соединёнными. Каждая пара e = (a, b) — ребро графа. Множество U — множество ребер e графа. Вершины a и b — концевые точки ребра e.

Широкое применение теории графов в компьютерных науках и информационных технологиях можно объяснить понятием графа как структуры данных. В компьютерных науках и информационных технологиях граф можно описать, как нелинейную структуру данных.

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

Основные понятия теории графов

Граф — это геометрическая фигура, которая состоит из точек и линий, которые их соединяют. Точки называют вершинами графа, а линии — ребрами.

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

Лемма о рукопожатиях

В любом графе сумма степеней всех вершин равна удвоенному числу ребер.

Доказательство леммы о рукопожатиях

Если ребро соединяет две различные вершины графа, то при подсчете суммы степеней вершин мы учтем это ребро дважды.

Если же ребро является петлей — при подсчете суммы степеней вершин мы также учтем его дважды (по определению степени вершины).

Из леммы о рукопожатиях следует: в любом графе число вершин нечетной степени — четно.

Пример 1. В классе 30 человек. Может ли быть так, что у 9 из них есть 3 друга в этом классе, у 11 — 4 друга, а у 10 — 5 друзей? Учесть, что дружбы взаимные.

Если бы это было возможно, то можно было бы нарисовать граф с 30 вершинами, 9 из которых имели бы степень 3, 11 — со степенью 4, 10 — со степенью 5. Однако у такого графа 19 нечетных вершин, что противоречит следствию из леммы о рукопожатиях.

Пример 2. Каждый из 102 учеников одной школы знаком не менее чем с 68 другими. Доказать, что среди них найдутся четверо ребят с одинаковым числом знакомых.

Сначала предположим противоположное. Тогда для каждого числа от 68 до 101 есть не более трех человек с таким числом знакомых. С другой стороны, у нас есть ровно 34 натуральных числа, начиная с 68 и заканчивая 101, а 102 = 34 * 3.

Это значит, что для каждого числа от 68 до 101 есть ровно три человека, имеющих такое число знакомых. Но тогда количество людей, имеющих нечетное число знакомых, нечетно. Противоречие.

Путь и цепь в графе

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

Циклом называют путь, в котором первая и последняя вершины совпадают.

Путь или цикл называют простым, если ребра в нем не повторяются.

Если в графе любые две вершины соединены путем, то такой граф называется связным.

Можно рассмотреть такое подмножество вершин графа, что каждые две вершины этого подмножества соединены путем, а никакая другая вершина не соединена ни с какой вершиной этого подмножества.

Каждое такое подмножество, вместе со всеми ребрами исходного графа, соединяющими вершины этого подмножества, называется компонентой связности.

Один и тот же граф можно нарисовать разными способами. Вот, например, два изображения одного и того же графа, которые различаются кривизной:

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

Граф H, множество вершин V’ которого является подмножеством вершин V данного графа G и множество рёбер которого является подмножеством рёбер графа G соединяющими вершины из V’ называется подграфом графа G.

Визуализация графовых моделей

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

Графы — и есть помощники в этом деле. Они помогают представить любую информацию, которую можно промоделировать в виде объектов и связей между ними.

Граф можно нарисовать на плоскости или в трехмерном пространстве. Его можно изобразить целиком, частично или иерархически.

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

Виды изобразительных соглашений:

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

Виды графов

Виды графов можно определять по тому, как их построили или по свойствам вершин или ребер.

Ориентированные и неориентированные графы

Графы, в которых все ребра являются звеньями, то есть порядок двух концов ребра графа не существенен, называются неориентированными.

Графы, в которых все ребра являются дугами, то есть порядок двух концов ребра графа существенен, называются ориентированными графами или орграфами.

Неориентированный граф можно представить в виде ориентированного графа, если каждое его звено заменить на две дуги с противоположным направлением.

Графы с петлями, смешанные графы, пустые графы, мультиграфы, обыкновенные графы, полные графы

Если граф содержит петли — это обстоятельство важно озвучивать и добавлять к основной характеристике графа уточнение «с петлями». Если граф не содержит петель, то добавляют «без петель».

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

Пустой граф — это тот, что состоит только из голых вершин.

Мультиграфом — такой граф, в котором пары вершин соединены более, чем одним ребром. То есть есть кратные рёбра, но нет петель.

Граф без дуг, то есть неориентированный, без петель и кратных ребер называется обыкновенным.

Граф называют полным, если он содержит все возможные для этого типа рёбра при неизменном множестве вершин. Так, в полном обыкновенном графе каждая пара различных вершин соединена ровно одним звеном.

Двудольный граф

Граф называется двудольным, если множество его вершин можно разбить на два подмножества так, чтобы никакое ребро не соединяло вершины одного и того же подмножества.

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

Эйлеров граф

Эйлеров граф отличен тем, что в нем можно обойти все вершины и при этом пройти одно ребро только один раз. В нём каждая вершина должна иметь только чётное число рёбер.

Пример. Является ли полный граф с одинаковым числом n рёбер, которым инцидентна каждая вершина, эйлеровым графом?

Ответ. Если n — нечётное число, то каждая вершина инцидентна n — 1 ребрам. В таком случае наш граф — эйлеровый.

Регулярный граф

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

Число вершин регулярного графа k-й степени не может быть меньше k + 1. У регулярного графа нечётной степени может быть лишь чётное число вершин.

Пример. Построить регулярный граф, в котором самый короткий цикл имеет длину 4.

Чтобы длина цикла соответствовала заданному условию, нужно чтобы число вершин графа было кратно четырем. Если число вершин равно четырём — получится регулярный граф, в котором самый короткий цикл имеет длину 3.

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

Гамильтонов граф

Гамильтоновым графом называется граф, содержащий гамильтонов цикл.

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

Говоря проще, гамильтонов граф — это такой граф, в котором можно обойти все вершины, и каждая вершина при обходе повторяется лишь один раз.

Взвешенный граф

Взвешенным графом называется граф, вершинам и/или ребрам которого присвоены «весы» — обычно некоторые числа. Пример взвешенного графа — транспортная сеть, в которой ребрам присвоены весы: они показывают стоимость перевозки груза по ребру и пропускные способности дуг.

Графы-деревья

Деревом называется связный граф без циклов. Любые две вершины дерева соединены лишь одним маршрутом.

Число q ребер графа находится из соотношения q = n — 1, где n — число вершин дерева.

Приведенное соотношение выражает критическое значение числа рёбер дерева, так как, если мы присоединим к дереву ещё одно ребро — будет создан цикл. А если уберем одно ребро, то граф-дерево разделится на две компоненты. Граф, состоящий из компонент дерева, называется лесом.

Определение дерева

Деревом называется связный граф, который не содержит циклов.

Таким образом, в дереве невозможно вернуться в исходную вершину, перемещаясь по ребрам и не проходя по одному ребру два или более раз.

Циклом называется замкнутый путь, который не проходит дважды через одну и ту же вершину.

Простым путем называется путь, в котором никакое ребро не встречается дважды.

Легко проверить, что дерево — это граф, в котором любые две вершины соединены ровно одним простым путем. Если выкинуть любое ребро из дерева, то граф станет несвязным. Поэтому:

Дерево — минимальный по числу рёбер связный граф.

Висячей вершиной называется вершина, из которой выходит ровно одно ребро.

Определения дерева:

1. Деревом называется связный граф не содержащий простых циклов.
2. Деревом называется связный граф, содержащий n вершин и n — 1 ребро.
3. Деревом называется связный граф, который при удалении любого ребра перестает быть связным.
4. Деревом называется граф, в котором любые две вершины соединены ровно одним простым путем.

Очень часто в дереве выделяется одна вершина, которая называется корнем дерева. Дерево с выделенным корнем называют корневым или подвешенным деревом. Пример: генеалогическое дерево.

Когда изображают деревья, то часто применяют дополнительные соглашения, эстетические критерии и ограничения.

Например, при соглашении включения (рис. 1) вершины корневого дерева изображают прямоугольниками, а соглашение — опрокидывания (рис. 2) подобно классическому соглашению нисходящего плоского изображения корневого дерева. Вот так могут выглядеть разные изображения одного дерева:

Теоремы дерева и их доказательства

В дереве с более чем одной вершиной есть висячая вершина.

Доказательство первой теоремы:

Пойдем из какой-нибудь вершины по ребрам. Так как в дереве нет циклов, то мы не вернемся в вершину, в которой уже побывали. Если у каждой вершины степень больше 1, то найдется ребро, по которому можно уйти из неё после того, как мы пришли в нее.

Но поскольку количество вершин в дереве конечно, когда-нибудь мы остановимся в некоторой вершине. Противоречие. Значит, когда-нибудь мы дойдём в висячую вершину. Если же начать идти из неё, то мы найдём вторую висячую вершину.

В дереве число вершин на 1 больше числа ребер.

Доказательство второй теоремы:

Докажем по индукции по количеству вершин в дереве n. Если в дерево одна вершина, то факт верен. Предположим, что для всех n

У любого связного графа есть остовное дерево.

Доказательство третьей теоремы:

Чтобы найти остовное дерево графа G, можно найти цикл в графе G и выкинуть одно ребро цикла — потом повторить. И так пока в графе не останется циклов. Полученный граф будет связным, так как мы выкидывали рёбра, не нарушая связность, но в нём не будет циклов. Значит, он будет деревом.

Теория графов и современные прикладные задачи

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

Графы и задача о потоках

Система водопроводных труб в виде графа выглядит так:

Каждая дуга графа отображает трубу. Числа над дугами (весы) — пропускная способность труб. Узлы — места соединения труб. Вода течёт по трубам только в одном направлении. Узел S — источник воды, узел T — сток.

Задача: максимизировать объём воды, протекающей от источника к стоку.

Для решения задачи о потоках можно использовать метод Форда-Фулкерсона. Идея метода в том, чтобы найти максимальный поток по шагам.

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

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

Графы и сетевое планирование

В задачах планирования сложных процессов, где много разных параллельных и последовательных работ, часто используют взвешенные графы. Их еще называют сетью ПЕРТ (PERT).

PERT (Program (Project) Evaluation and Review Technique) — техника оценки и анализа программ (проектов), которую используют при управлении проектами.

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

Если в сети есть дуги (a, b) и (b, c), то работа, представленная дугой (a, b), должна быть завершена до начала выполнения работы, представленной дугой (b, c). Каждая вершина (vi) представляет момент времени, к которому должны быть завершены все работы, задаваемые дугами, оканчивающимися в вершине (vi).

• одна вершина, у которой нет предшественников, определяет время начала работы
• одна вершина без последователей соответствует моменту завершения комплекса работ.

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

Источник

Вам также может понравиться

Ясень семена способ распространения

Ясень обыкновенный Fraxinus excelsior – так в ботанической

Ярлыки способы создания ярлыков ос windows

Создаем ярлыки на рабочем столе Windows Создаем ярлыки

Японское удобрение фуджима способ применения

Удобрения Фуджима Знаете потрясающее удобрение, палочка

Японский чай способ заварки

Технология заваривания японского чая Известно, что