Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
ШПОР СС Якубова на печать.doc
Скачиваний:
0
Добавлен:
01.07.2025
Размер:
3 Мб
Скачать
☆

19 Построение кратчайших путей. Дерево путей. Маршрутизация

19 Ең қысқа жолдарды құру. Жолдар ағашы. Маршруттеу

Путь, имеющий наименьшую характеристику среди множества путей MST, соединяющих вершины S и T, называется кратчайшим.

Длина кратчайшего пути между S и T называется расстоянием dST между S и T, т. е.

Для определения кратчайших путей разработано множество методов, рассмотрим один из них – метод пометок.

Пусть дан граф, на дугах которого записаны цифры – длины дуг. Определить расстояние между вершинами 1 и 5.

Рисунок 7.1

Помечаем вершины:

Определим  (из вершины 4)

  (из вершины 2)

μ={1,2,4,5}

lμ- расстояние между вершинами 1 и 5.

Наиболее часто встречающийся частичный граф – это дерево, содержащее все вершины графа и ребра, не образующие циклов. Число дуг дерева на единицу меньше числа вершин.

Граф называется сильно связным, если между каждой парой его вершин существует путь, и связным, если существует цепь. Каждый сильно связный граф связен, обратное утверждение несправедливо.

Степенью связности называется минимальное число h независимых путей, имеющихся между каждой парой узлов сети. Понятие связности может быть отнесено не ко всей сети, а к заданной паре вершин, или к путям, обладающим заданным свойством.

20 Сечения

20 Кесінділер, кесінділер рангі

Сечением графа называется минимальная совокупность ребер, изъятие которой нарушает его связность. Сечение записывается множеством входящих в него ребер, например,

Число этих ребер определяет ранг сечения

Если граф имеет хотя бы одну пару вершин xi и xj, соединенных m ребрами (или дугами) одного направления, он называется мультиграфом.

Если ребро  графа G=(X, U) соединяет вершины , т.е. , то говорят, что ребро инцидентно вершинам . Справедливо и обратное – вершины  инцидентны ребру.

Если две вершины  соединены ребром, то они называются смежными.

Если два ребра инцидентны одной вершине, то они называются смежными. Следовательно, отношения инцидентности и смежности имеют место как на множестве вершин, так и на множестве дуг.

Число ребер, инцидентных вершине , называется локальной степенью этой вершины.

Цикломатическим числом графа называется наименьшее число ребер, которое необходимо удалить из графа G=(X, U), чтобы он стал деревом (т. е. ациклическим). Цикломатическое число v=|U|-|X|+1 

где |X| - число вершин графа, |X|=n;

|U| - число дуг графа, |U|=m,

v=m-n+1 

Сечением s сети назовем минимальную совокупность ребер, которые надо изъять из сети, чтобы нарушилось ее связность. Сечением sST  по отношению к узлам S и Т будем называть такие сечения, при которых названные узлы будут находиться в разных подсетях. Рангом сечения называется число входящих в него ребер.

21 Путь и методы их построения

21 Жол және оны құру әдістері

Для ориентированного графа введено понятие пути, т. е. последовательности дуг, причем конец каждой предыдущей совпадает с началом последующей.

Путь называется простым, если никакая дуга не встречается дважды, и составным – в противном случае; элементарным – если никакая вершина не встречается дважды. В технических приложениях используются только простые, элементарные пути, и эти определения обычно опускаются. Замкнутый путь называется контуром.

Последовательность ребер и разнонаправленных дуг называется цепью. Замкнутая цепь называется циклом.

Рангом пути будем называть число дуг, составляющих путь.

Если каждой дуге поставить в соответствие некоторую характеристику, называемую весом дуги (например, длину, стоимость, вес и т. д.), то сумму этих весов будем называть длиной пути

Путь, имеющий наименьшую характеристику среди множества путей MST, соединяющих вершины S и T, называется кратчайшим.

Длина кратчайшего пути между S и T называется расстоянием dST между S и T, т. е.

Для определения кратчайших путей разработано множество методов, рассмотрим один из них – метод пометок.

Пусть дан граф, на дугах которого записаны цифры – длины дуг. Определить расстояние между вершинами 1 и 5.

Рисунок 7.1

Помечаем вершины:

Определим  (из вершины 4)

  (из вершины 2)

μ={1,2,4,5}

lμ- расстояние между вершинами 1 и 5.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]