Составители:
73
графа, рассмотренного в примерах
2.1.1 и 2.1.2, после замены соот-
ветствующих пар дуг эквивалент-
ными им ребрами приведена на
рис. 2.1.2.
Определение 2.1.10. Граф
G = <X, U >, множество U которо-
го содержит только дуги, называ-
ется ориентированным графом
(орграфом).
Определение 2.1.11. Граф
G = < X, U >, множество U кото-
рого содержит только ребра, на-
зывается неориентированным графом.
Определение 2.1.12. Граф G = < X, U >, множество U которого со-
держит как ребра, так и дуги, называется смешанным графом.
Матричное представление неориентированных графов имеет свои
особенности. Элемент матрицы смежности неориентированного графа
равен 1, если в графе существует ребро, соединяющее вершины, со-
ответствующие строке и столбцу, и 0, если такого ребра не суще-
ствует. Элементы матрицы инцидентности такого графа равны 1, если
вершина, соответствующая строке, инцидентна ребру, соответству-
ющему столбцу, и 0, если соответствующие вершина и ребро не ин-
цидентны. Поэтому матрицы смежности ориентированных и неори-
ентированных графов совпадают по внешнему виду, так как содер-
жат только нули и единицы, а матрицы инцидентности оказываются
различными, так как элементами такой матрицы ориентированного
графа являются элементы множества {–1, 0, +1}, а неориентирован-
ного графа – элементы множества {0,1}.
Для неориентированного графа с кратными дугами элемент мат-
рицы смежности равен числу ребер, соединяющих соответствующие
вершины.
Рис. 2.1.2. Диаграмма графа, приведенного
в примерах 2.1.1 и 2.1.2, после замены
пар дуг ребрами
x
1
x
2
x
5
x
4
x
3
Страницы
- « первая
- ‹ предыдущая
- …
- 71
- 72
- 73
- 74
- 75
- …
- следующая ›
- последняя »
