ВУЗ:
Составители:
62
7. Для многих практиче-
ских задач удобным является
понятие взвешенного графа.
Граф называется взвешенным,
если каждому его ребру (ду-
ге) (x
i
,x
j
) поставлен в соот-
ветствие определенный математический объект p(x
i
,x
j
), называемый
весом (длиной, стоимостью и т.п.) этого ребра. Для такого графа по
аналогии с матрицей смежности определяется матрица весов. Веса
несуществующих ребер считаются равными нулю. Иногда веса при-
писываются вершинам x
i
графа, тогда получается граф взвешенный
по вершинам. Могут быть взвешены и дуги, и вершины. Примером
взвешенного графа может служить сигнальный граф и транспортная
сеть (см. подраздел 2.6 ).
8. Орграф называют сильносвязным или сильным, если для лю-
бых вершин x
i
и x
j
существует хотя бы один путь, соединяющий их.
Орграф называют одностороннесвязным или односторонним, если
для любых вершин x
i
и x
j
существует путь из x
i
в x
j
или из x
j
в x
i
.
Орграф называют слабосвязным или слабым, если для любых двух
различных вершин существует хотя бы один маршрут.
Если для некоторой пары вершин не существует маршрута, со-
единяющего их, то такой орграф называют несвязным. Пример силь-
носвязного графа приведен на рис. 2.20.
Следующим пунктом будет рассмотрен
граф, который служит примером односто-
роннесвязанного графа. Пример несвязно-
го приведен на рис. 2.29.
9. Деревья. Связный граф, в котором нет циклов, называется
деревом. Одним из отличительных свойств дерева является то, что в
K
5
K
3,3
Рис. 2.28
Рис. 2.29
Страницы
- « первая
- ‹ предыдущая
- …
- 64
- 65
- 66
- 67
- 68
- …
- следующая ›
- последняя »
