Способы задания графов матрицами

Матричные способы задания графов. Упорядочение элементов орграфа

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

Определение 12.3. Матрицей инцидентности орграфа без петель с n вершинами и m дугами называется матрица, любой элемент которой определяется по следующей формуле:

Для неориентированного графа вместо «–1» ставится «1».

Пример.Для заданного ориентированного графа (рис. 12.10) построить матрицу инцидентности:

Матрица инцидентности орграфа:

.

Определение 12.4. Матрица смежности вершин орграфа – квадратная матрица n-го порядка (n – число вершин). Строки и столбцы матрицы соответствуют вершинам графа. Элементы S_ij матрицы равны числу дуг, направленных из i-й вершины в j-ю.

В случае неориентированного графа ему вместе с ребром (x_i,x_j) принадлежит и ребро (x_j,x_i), поэтому матрица будет симметрической.

Пример.Для заданного ориентированного графа (рис. 12.11) построить матрицу смежности вершин:

Матрица смежности вершин орграфа:

.

Определение 12.5. Матрица смежности дуг орграфа – квадратная матрица m-го порядка (m – число дуг). Строки и столбцы матрицы соответствуют дугам графа. Элементы q_ij равны 1, если дуга u_i непосредственно предшествует дуге u_j, и нулю в остальных случаях.

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

Пример.Для заданного ориентированного графа (рис. 12.12) построить матрицу смежности дуг:

Матрица смежности дуг орграфа:

.

Расчеты в задачах, связанных с графами, заметно упрощаются, если их элементы упорядочены.

Определение 12.6. Вершина x_i предшествует вершине x_j, если существует путь из x_i в x_j, тогда x_i называется предшествующей вершине x_j, а x_j – последующей за x_i.

Под упорядочением вершин связного орграфа без контуров понимают такое разбиение его вершин на группы, при котором:

1) вершины первой группы не имеют предшествующих, а вершины последней – последующих;

2) вершины любой другой группы не имеют предшествующих в следующей группе;

3) вершины одной и той же группы дугами не соединяются.

В результате упорядочения элементов получают граф, изоморфный данному.

Графический способ упорядочения вершин – алгоритм Фалкерсона:

1) Находят вершины графа, в которые не входит ни одна дуга. Они образуют первую группу.

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

3) Устанавливается следующая группа вершин, в которую не входит ни одна дуга. Этот шаг повторяют до тех пор, пока все вершины не будут упорядочены.

Пример.Упорядочить вершины орграфа (рис. 12.13):

Упорядочим вершины орграфа по алгоритму Фалкерсона (рис. 12.14):

Дата добавления: 2014-12-03 ; просмотров: 340 ; Нарушение авторских прав

Источник

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

Содержание:

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

2. Матричные способы задания графов. 4

3. Упорядочение элементов орграфа. 6

4. Постановка задачи о максимальном потоке. Основные определения. 8

5. Разрез на сети. 11

6. Алгоритм решения задачи о максимальном потоке. 13

Список использованной литературы.. 21

Введение

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

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

Основным объектом этой теории является граф. Наглядно граф можно представить как некоторое множество точек плоскости или пространства и множество отрезков кривых или прямых линий, соединяющих все или некоторые из этих точек. Формально граф G определяется заданием двух множеств X и U и обозначается G=(XU). Элементы xB_1B, xB_2B, …, xB_{n B} множества X называются вершинами и изображаются точками. Элементами uB_1B, uB_2B, …, uB_m множества U являются пары связанных между собой элементов множества X и изображаются отрезками. Взаимное расположение, форма и длины отрезков значения не имеют. Если в паре вершин xB_{i B}и B _BxB_{j B}указано направление связи, то есть указано, какая вершина является первой, то отрезок UB_{1 B}называется дугой, а если ориентация не указана, — ребром.

Если в графе G все элементы множества U изображаются дугами, то граф называется ориентированным (орграф), если ребрами, — неориентированным.

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

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

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

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

В экономике чаще всего используются два вида графов: дерево и сеть.

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

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

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

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

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

Пусть имеется граф G, не содержащий петель, имеющий n вершин и m дуг (ребер). Графу G можно сопоставить матрицу инциденций графа G. Строки m этой матрицы соответствуют вершинам, столбцы n – дугам (ребрам) графа. Если граф ориентированный, то элементы aB_{ij B}матрицы инциденций равны: (-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 xB5B 0 0 1 0 0 1 1 Для ориентированных и неориентированных графов можно сформировать матрицу смежности вершин. Пусть орграф G содержит n вершин. Его матрица смежности представляет собой квадратную матрицу n-го порядка. Строки и столбцы этой матрицы соответствуют вершинам орграфа G. Элементы uBij Bесть число дуг, выходящих из 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-го порядка. Строки и столбцы матриц соответствуют дугам (ребрам) графа. Элементами pBij Bматрицы для ориентированного графа буду 1 и 0. Если дуга uB1 Bпрямо предшествует дуге BuBjB,B Bто pBij B= 1 и 0 – в остальных случаях. Матрица смежности ребер неориентированного графа своими элементами также имеет 1 и 0. Элемент pBijB = 1, если ребра uBi Bи uBj Bсмежные, и 0 – в остальных случаях. Источник Читайте также:  Способы снижения случайной погрешности Оцените статью Вам также может понравиться Ясень семена способ распространения Ясень обыкновенный Fraxinus excelsior – так в ботанической Ярлыки способы создания ярлыков ос windows Создаем ярлыки на рабочем столе Windows Создаем ярлыки Японское удобрение фуджима способ применения Удобрения Фуджима Знаете потрясающее удобрение, палочка Японский чай способ заварки Технология заваривания японского чая Известно, что Правообладателям Политика конфиденциальности Контакты