Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


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




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

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

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

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

Рис. 12.10

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

.

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

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

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

Рис 12.11

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

.

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

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

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

Рис.12.12

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

.

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 12.13

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

Рис. 12.14


Поделиться:

Дата добавления: 2014-12-03; просмотров: 631; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты