Составители:
Рубрика:
8
что ребро (дуга) и его граничные точки инцидентны друг другу, иначе
говоря, вершины, инцидентные ребру (дуге), являются его концевыми
точками. Понятие инцидентности ребер (дуг) и их концевых вершин
является фундаментальным в теории графов, которая построена с уче-
том именно этой особенности и не учитывает реальной природы вер-
шин и ребер (дуг).
Структурное различие между неориентированным графом и оргра-
фом состоит в том, что в первом случае граничные точки ребра образу-
ют неупорядоченную, а во втором – упорядоченную пару вершин. Реб-
ро эквивалентно противоположно направленным дугам.
Геометрическое представление графов, являясь наглядным, трудно
поддается математической обработке, поэтому описание графа форма-
лизуют и представляют в общем виде:
G = (V,
U
) или G = (V, U ),
где V – непустое множество вершин графа v
i
∈ V;
U
– множество ребер
для неориентированного графа; U – множество дуг орграфа. Любой граф
в абстрактном смысле эквивалентен (по отношению к свойствам, изу-
чаемым в теории графов) некоторому геометрическому графу.
Для удобства обработки графов с использованием ЭВМ лучше всего
подходит матричная форма представления структурных свойств графа.
Матрица смежности вершин графа – это квадратная матрица || S ||
размера n×n (n – количество вершин), где строки и столбцы соответ-
ствуют вершинам графа, а элемент s
ij
для неориентированного графа
равен числу ребер, соединяющих одновременно вершины i и j, а для
орграфа s
ij
равен количеству дуг (v
i
,
v
j
).
Матрица смежности неориентированного графа без петель (ребер, зам-
кнутых на одну вершину) симметрична относительно главной диагонали,
Рис. 1. Геометрическое представление графов:
а) неориентированный граф; б) ориентированный граф
а)
v
3
1
u
4
u
v
2
v
1
2
u
v
4
u
4
u
2
u
3
u
5
u
6
u
1
v
1
v
2
v
3
б)
3
u
Страницы
- « первая
- ‹ предыдущая
- …
- 8
- 9
- 10
- 11
- 12
- …
- следующая ›
- последняя »
