Составители:
Рубрика:
92
Встречаются и различные комбинации приведенных графов, напри
мер графы с кратными ребрами и петлями, графы с направленными и
ненаправленными переходами (ребрами) и т. п.
5.3. Способы задания графов
Для того чтобы использовать задания в виде графов при решении
разнообразных оптимизационных задач, применяют различные экви
валентные способы задания. Основным требованием является взаим
ная однозначность графического изображения и выбранного способа
задания. Чаще всего используются следующие виды задания графа:
– матрица инциденции;
– список ребер;
– матрица смежности.
Рассмотрим эти виды задания.
1. Матрица инциденции. Нумеруются все ребра графа (например,
арабскими цифрами) и все вершины (например, буквами). Строится
матрица, каждой строке которой сопоставляется ребро, а каждому
столбцу – вершина. Символами (например, единицами), отмечаются
вершины, связанные ребрами. Так, для графов типа a, b (см. рис. 5.2)
матрицы инциденции имеют вид (табл. 5.1, 5.2).
В табл. 5.2 два кратных ребра, связывающие вершины B и C, заме
нены одним ребром с двойной связью (обозначены цифрой 2).
В графе с (см. рис. 5.2) имеются петли. Для их указания можно ис
пользовать любые символы, отличные от 1. Мы использовали символ
*
.
В вершине D имеются две петли. Их можно указывать отдельно (табл.
5.3) либо объединить две петли в одну и отметить какимлибо новым
символом, например
**
.
При построении матрицы инциденции для направленного графа d
(см. рис. 5.2) необходимо было указать направление перехода. Для это
го в столбце, соответствующем вершине, из которой выходит стрелка,
Таблица 5.2
b)
Таблица 5.1
a)
орбеР
ABCDEF
1
11
2
11
3
11
4
11
5
11
6
11
7
11
8
11
орбеР
ABCDE
1
11
2
22
3
11
4
11
5
11
6
11
Страницы
- « первая
- ‹ предыдущая
- …
- 90
- 91
- 92
- 93
- 94
- …
- следующая ›
- последняя »
