Читайте также:
|
19 Ең қысқа жолдарды құру. Жолдар ағашы. Маршруттеу
Путь, имеющий наименьшую характеристику среди множества путей MST, соединяющих вершины S и T, называется кратчайшим.
Длина кратчайшего пути между S и T называется расстоянием dST между S и T, т. е.
Для определения кратчайших путей разработано множество методов, рассмотрим один из них – метод пометок.
Пусть дан граф, на дугах которого записаны цифры – длины дуг. Определить расстояние между вершинами 1 и 5.
Рисунок 7.1
Помечаем вершины:
Определим 
(из вершины 4)
(из вершины 2)
μ={1,2,4,5}
lμ- расстояние между вершинами 1 и 5.
Наиболее часто встречающийся частичный граф – это дерево, содержащее все вершины графа и ребра, не образующие циклов. Число дуг дерева на единицу меньше числа вершин.
Граф называется сильно связным, если между каждой парой его вершин существует путь, и связным, если существует цепь. Каждый сильно связный граф связен, обратное утверждение несправедливо.
Степенью связности называется минимальное число h независимых путей, имеющихся между каждой парой узлов сети. Понятие связности может быть отнесено не ко всей сети, а к заданной паре вершин, или к путям, обладающим заданным свойством.
Дата добавления: 2015-07-17; просмотров: 100 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Возможность и целесообразность интеграции сетей | | | Сечения |