4. Постановка задачи о максимальном потоке. Основные определения. 8
5. Разрез на сети. 11
6. Алгоритм решения задачи о максимальном потоке. 13
Список использованной литературы.. 21
Введение
В последнее время в различных областях знаний широко применяется теория графов. С помощью теории графов хорошо описываются задачи экономической и планово-производственной практики, как, например, календарное и сетевое планирование и управление, автоматизация управления производством, рационализация схем перевозок и грузопотоков, оптимальное размещение производства т.п.
Основные понятия теории графов
Основным объектом этой теории является граф. Наглядно граф можно представить как некоторое множество точек плоскости или пространства и множество отрезков кривых или прямых линий, соединяющих все или некоторые из этих точек. Формально граф G определяется заданием двух множеств X и U и обозначается G=(XU). Элементы xB1B, xB2B, …, xBnB множества X называются вершинами и изображаются точками. Элементами uB1B, uB2B, …, uBm множества U являются пары связанных между собой элементов множества X и изображаются отрезками. Взаимное расположение, форма и длины отрезков значения не имеют. Если в паре вершин xBiBи B BxBjBуказано направление связи, то есть указано, какая вершина является первой, то отрезок UB1 Bназывается дугой, а если ориентация не указана, — ребром.
Если в графе G все элементы множества U изображаются дугами, то граф называется ориентированным (орграф), если ребрами, — неориентированным.
На практике используются графы, в которых множества X и U состоят из конечного числа элементов, то есть конечные графы. На рисунке располагать вершины графа можно произвольно. Также произвольно выбирается и форма соединяющих их линий. Поэтому один и тот же граф (граф с одной и той же информацией) может быть представлен в различных видах. Такие графы называются изоморфными.
Смежными называют вершины графа, если они различны и существует дуга (ребро), которая соединяет эти вершины. Если две дуги (ребра) имеют общую концевую вершину, то такие дуги (ребра) смежные.
Последовательность дуг, в которой конец каждой предыдущей дуги совпадает с началом следующей, называется путем в орграфе. Путь, проходящий через все вершины и при этом только один раз, называется гамильтоновым. Путь, включающий все дуги графа, и при этом только по одному разу, называется эйлеровым. Полным путем называют любую непрерывную последовательность вершин и дуг, идущих от начальной вершины к конечной. Конечный путь, у которого начальная вершина совпадает с конечной, называется контуром.
Граф называется связным, если для любых двух его вершин существует путь, их соединяющий; в противном случае граф называется несвязным.
В экономике чаще всего используются два вида графов: дерево и сеть.
Дерево представляет собой связный граф без циклов, имеющий исходную вершину (корень) и крайние вершины; пути от исходной вершины к крайним вершинам называются ветвями.
Если граф, вообще говоря, не связный, не содержит циклов, то каждая связная его часть будет деревом. Такой граф называется лесом.
В приложении теории графов к практическим задачам дугам (ребрам) графа сопоставляют какие-то числовые характеристики. Например, пропускная способность транспортной магистрали, запас какого-либо ресурса, продолжительность выполнения какой-либо работы и т.д. Таким образом, дугам графа приписаны определенные веса и граф G называется взвешенным.
Матричные способы задания графов
Граф может быть представлен как в виде рисунка, так и в виде матрицы. Это бывает необходимо при большом числе вершин и дуг (ребер), когда рисунок теряет свою наглядность. Матричное представление графов используется при исследовании его на ЭВМ.
Пусть имеется граф G, не содержащий петель, имеющий n вершин и m дуг (ребер). Графу G можно сопоставить матрицу инциденций графа G. Строки m этой матрицы соответствуют вершинам, столбцы n – дугам (ребрам) графа. Если граф ориентированный, то элементы aBijBматрицы инциденций равны: (-1), если дуга u исходит из i-й вершины; (+1), если дуга заходит в i-ю вершину. Если граф неориентированный, то элементами матрицы будут 1 и 0. На рис. 1.2 показаны орграф и его матрица инциденций, на рис. 1.3. — неориентированный граф и матрица инциденций.
uB1B
uB2B
uB3B
uB4B
uB5B
uB6B
uB7B
xB1B
-1
0
0
0
-1
-1
0
xB2B
1
-1
0
0
0
0
0
xB3B
0
0
0
1
1
0
-1
xB4B
0
1
1
0
0
0
0
xB5BBB
0
0
-1
0
0
1
1
uB1B
uB2B
uB3B
uB4B
uB5B
uB6B
uB7B
xB1B
1
0
0
0
1
1
0
xB2B
1
1
0
0
0
0
0
xB3B
0
0
0
1
1
0
1
xB4B
0
1
1
0
0
0
0
xB5B
0
0
1
0
0
1
1
Для ориентированных и неориентированных графов можно сформировать матрицу смежности вершин. Пусть орграф G содержит n вершин. Его матрица смежности представляет собой квадратную матрицу n-го порядка. Строки и столбцы этой матрицы соответствуют вершинам орграфа G. Элементы uBijBесть число дуг, выходящих из i-й вершины и входящий в j-ю. В орграфе, не содержащем параллельных дуг, элементами матрицы будут 1 и 0. На рис. 1.4. представлен орграф и его матрица смежности вершин. Как видно из рис. 1.5, у неориентированного графа матрица смежности вершин будет симметрической. По матрице смежности вершин определяется степень вершины, т.е. число дуг, пересекающихся в этой вершине. Число входящих в i-ю вершину дуг равно сумме элементов i- го столбца; число дуг, исходящих из данной вершины, равно сумме элементов i-й строки.
xB1B
xB2B
xB3B
xB4B
xB5B
xB6B
xB7B
xB1B
0
1
0
0
0
0
0
xB2B
0
0
0
0
0
0
1
xB3B
1
0
0
1
0
0
0
xB4B
0
0
0
0
0
0
1
xB5B
0
0
1
0
0
0
0
xB6B
1
0
0
0
1
0
0
xB7B
0
0
0
1
0
1
0
xB1B
xB2B
xB3B
xB4B
xB1B
1
1
1
0
xB2B
1
0
1
1
xB3B
1
1
0
1
xB4B
0
1
1
1
Граф G также может быть задан матрицей смежности дуг (ребер). Предположим, что некоторый граф имеет m дуг (ребер). Его матрица смежности дуг (ребер) представляет собой квадратную матрицу m-го порядка. Строки и столбцы матриц соответствуют дугам (ребрам) графа. Элементами pBijBматрицы для ориентированного графа буду 1 и 0. Если дуга uB1 Bпрямо предшествует дуге BuBjB,B Bто pBijB= 1 и 0 – в остальных случаях. Матрица смежности ребер неориентированного графа своими элементами также имеет 1 и 0. Элемент pBijB = 1, если ребра uBiBи uBjBсмежные, и 0 – в остальных случаях.
Источник
Матричные способы задания графов. Упорядочение элементов орграфа
Читайте также:
B.6.4.1. Способы выделения текста.
III. Для обеспечения проверки исходного уровня знаний-умений решите 2 задания.
III. Для обеспечения проверки исходного уровня знаний-умений решите 2 задания.
III. Для обеспечения проверки исходного уровня знаний-умений решите 2 задания.
V. Способы и методы обеззараживания и/или обезвреживания медицинских отходов классов Б и В
VII. Выполнение задания на развитие внимания, смекалки.
VII.2.2) Способы приобретения права собственности.
XII. Способы оплаты труда
Алгоритм. Свойства алгоритма. Способы описания алгоритма. Примеры.
Амортизация ОС. Способы
При большом числе элементов рисунок графа теряет наглядность. В таком случае граф целесообразно задать матричным способом. Этот способ также удобен и для решения задачи на компьютере.
Определение 12.3. Матрицей инцидентности орграфа без петель с n вершинами и m дугами называется матрица, любой элемент которой определяется по следующей формуле:
Для неориентированного графа вместо «–1» ставится «1».
Пример.Для заданного ориентированного графа (рис. 12.10) построить матрицу инцидентности:
Матрица инцидентности орграфа:
.
Определение 12.4. Матрица смежности вершин орграфа – квадратная матрица n-го порядка (n – число вершин). Строки и столбцы матрицы соответствуют вершинам графа. Элементы Sij матрицы равны числу дуг, направленных из i-й вершины в j-ю.
В случае неориентированного графа ему вместе с ребром (xi,xj) принадлежит и ребро (xj,xi), поэтому матрица будет симметрической.
Пример.Для заданного ориентированного графа (рис. 12.11) построить матрицу смежности вершин:
Матрица смежности вершин орграфа:
.
Определение 12.5. Матрица смежности дуг орграфа – квадратная матрица m-го порядка (m – число дуг). Строки и столбцы матрицы соответствуют дугам графа. Элементы qij равны 1, если дуга ui непосредственно предшествует дуге uj, и нулю в остальных случаях.
Для неориентированного графа матрица смежности дуг симметрическая с элементами равными 1, если ребра имеют общую вершину, и 0 в остальных случаях.
Пример.Для заданного ориентированного графа (рис. 12.12) построить матрицу смежности дуг:
Матрица смежности дуг орграфа:
.
Расчеты в задачах, связанных с графами, заметно упрощаются, если их элементы упорядочены.
Определение 12.6. Вершина xi предшествует вершине xj, если существует путь из xi в xj, тогда xi называется предшествующей вершине xj, а xj – последующей за xi.
Под упорядочением вершин связного орграфа без контуров понимают такое разбиение его вершин на группы, при котором:
1) вершины первой группы не имеют предшествующих, а вершины последней – последующих;
2) вершины любой другой группы не имеют предшествующих в следующей группе;
3) вершины одной и той же группы дугами не соединяются.
В результате упорядочения элементов получают граф, изоморфный данному.
Графический способ упорядочения вершин – алгоритм Фалкерсона:
1) Находят вершины графа, в которые не входит ни одна дуга. Они образуют первую группу.
2) Вершины и исходящие из них дуги исключают из дальнейшего рассмотрения (то есть вычеркивают).
3) Устанавливается следующая группа вершин, в которую не входит ни одна дуга. Этот шаг повторяют до тех пор, пока все вершины не будут упорядочены.
Пример.Упорядочить вершины орграфа (рис. 12.13):
Упорядочим вершины орграфа по алгоритму Фалкерсона (рис. 12.14):
Дата добавления: 2014-12-03 ; просмотров: 340 ; Нарушение авторских прав
.
.
.
