Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

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

Многоцелевая оптимизация (многокритериальная): оптимизация по одному критерию (важнейшему), построение интегрального критерия | Задачи синтеза: а) алгоритм структурного синтеза; б) синтез централизованных сетей; в) синтез втричных сетей. | Параметры и функции. Критерии и ограничения | Стадии проектирования | Свойства больших систем | Задачи анализа и синтеза | Стратегия построения ЦСИО | Этапы развития цифровых сетей | Путь и методы их построения | Матрица смежности, расстояний, структурная. |


Читайте также:
  1. Бинарное дерево. Построение бинарного дерева
  2. Божья сила и колдовское дерево
  3. В) Построение оценки эмпирической функции распределения и формирование классификационной шкалы
  4. Вопрос 8 Если в конструкторе печати указано имя процедуры, которая будет выполнять построение печатной формы, и такая процедура уже присутствует в модуле...
  5. Вставка элемента в АВЛ-дерево
  6. Глава пятая Я загоняю свою собаку в дерево
  7. Говорящее дерево

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 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Возможность и целесообразность интеграции сетей| Сечения

mybiblioteka.su - 2015-2024 год. (0.006 сек.)