6.4. Другие способы задания графа |
211 |
|
|
|
|
2.Семантическая сеть : L – имена объектов, C – имена отношений между ними.
3.Потоки в сетях: каждой дуге сети ставится в соответствие ее пропускная способность и величина потока по дуге.
6.4Другие способы задания графа
Представления графов с помощью матриц инциденций и матриц смежности, при всех их достоинствах, не лишены и ряда недостатков. Рассмотрим матрицы инциденций для графа Бержа (1- орграфа) и обыкновенного графа. Для 1-орграфа без петель можно положить
°> = 1, °< = ¡1, °± = 0, °» = 0,
а для обыкновенного графа
°> = 1, °< = 1, °» = 1, °± = 0.
Пример 6.15.
1 |
G |
|
3 |
1 |
|
G1 |
3 |
r |
|
¡ |
rK |
r |
|
|
r |
|
|
¡µ |
|
|
|
|
|
|
¡ |
|
|
|
|
|
|
|
¡ |
|
|
|
|
|
|
?¡ |
|
? |
|
|
|
|
|
¡¾ |
|
r4 |
r |
2 |
|
r4 |
|
r |
2 |
|
|
||||
Для графа Бержа G и обыкновенного графа G1 матрицы инциденций имеют следующий вид:
|
|
! ! ! ! ! |
||||
|
A |
12 |
13 |
34 |
41 |
43 |
A = |
1 |
1 |
1 |
0 |
-1 |
0 |
|
2 |
-1 |
0 |
0 |
0 |
0 |
|
3 |
0 |
-1 |
1 |
0 |
-1 |
|
4 |
0 |
0 |
-1 |
1 |
1 |
|
|
|
|
|
|
|
6.4. Другие способы задания графа |
213 |
|
|
|
|
2¶³1 |
3 |
- |
|
1 |
|
|
3 |
||
|
r |
|
4 |
¡ r |
b |
r |
|
|
¡ r |
|
la |
|
*¡µ |
|
|
|
µ¡ K |
||
µ´ |
|
|
|
|
|
|
¡ |
||
6 |
5 |
7¡¡ |
|
|
|
|
|||
|
|
|
|
¡ |
|||||
|
|
¡ |
8 |
9 |
|
|
|
¡ |
|
|
? |
|
|
? |
? |
||||
|
|
|
|
|
|
||||
|
cr¡9 |
|
rd |
¡¾ |
r4 |
||||
|
|
r |
2 |
|
|||||
G1 |
G2 |
Граф Бержа G2 представлен в виде массива пар, упорядоченного в лексикографическом порядке:
[(1; 2); (2; 3); (3; 4); (4; 2); (4; 3)]:
Граф общего вида G1 представлен в виде массива троек, также упорядоченного в лексикографическом порядке:
[(a; 1; a); (a; 2; a); (a; 3; b); (a; 4; b); (a; 5; c); (a; 6; c);
(b; 4; a); (b; 9; c); (c; 6; a); (c; 7; b); (c; 8; b)]:
Заметим, что звенья (вместе с парой инцидентных им вершин) в массиве представлены дважды.
В некоторых случаях граф удобно представлять в виде списков смежности. Каждый список содержит саму вершину x и подсписок, представляющий ее окружение ¡x. Размерность такого представления равна m + n.
Граф G2, например, можно представить в виде такого списка:
[1; [2]]; [2; [3]]; [3; [4]]; [4; [2; 3]]. J
З а м е ч а н и е. Напомним, что последним элементом списка и, следовательно, любого подсписка является (и подразумевается по умолчанию) пустой список nil или [ ].
Описанные выше способы представления графа аналогичны способам представления множества: представление графа с помощью матриц есть задание характеристических функций (функций принадлежности), а представление в виде массивов и списков – это перечисление элементов графа.
Возможен и дескриптивный (предикатный, высказывательный) способ представления графа.
Выбор способа представления является существенной частью разработки алгоритма решения конкретной задачи и всегда является компромиссом между размерностью представления и эффективностью алгоритма.