Главная \ Методичні вказівки \ Методические указания \ 23 Практическая работа №6 Задачи анализа сетей

Практическая работа №6 Задачи анализа сетей

« Назад

23 Практическая работа №6 Задачи анализа сетей 20.03.2018 13:44

Практическая работа №6

с курса Цифровые системы коммутации

на тему: Задачи анализа сетей

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

Деревья. Представление структуры дерева

Множество задач, таких как задачи маршрутизации, проектирования и оптимизации структуры сетей решаются методом построения деревьев в графе (генерация деревьев, минимальное остовное дерево, дерево кратчайших путей и др.).

Введем определение дерева и рассмотрим структуры данных для его представления.

Можно дать три эквивалентных определения дерева:

- Связный граф с n вершинами и n-1 ребрами называется деревом.

- Связный граф, не содержащий циклов, называется деревом.

- Граф, в котором каждая пара вершин связана одной простой цепью, называется деревом.

Неориентированный граф без циклов называется лесом.

Свойства деревьев, вытекающие из определения дерева:

- Дерево содержит n вершин и n-1 ребер.

- Любые две вершины дерева связаны единственной цепью.

- Добавление ребра к дереву приводит к образованию цикла.

- Удаление ребра в дереве приводит к нарушению связности.

Примеры деревьев представлены на рисунке 3.

Рис. 4 – Построение основных деревьев

Связный подграф с n вершинами и n-1 ребрами называется остовным деревом или остовом графа.

Другими словами, остов получается из связного неориентированного графа путем удаления ребер до тех пор, пока в графе не останется n-1 ребер.

Остовные деревья для графа G=(V,E) приведены на рисунке 4.

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

Пример ориентированного дерева предлагается на рисунке 3(в).

Если в ориентированном дереве есть вершина, в которую не входит ни одно ребро, то оно называется корневым, а вершина – корнем дерева.

Корневым деревом является дерево на рисунке 3(в).

Для взвешенного графа остовное дерево с минимальным суммарным весом ребер называется минимальным остовным деревом или кратчайшей связующей сетью.

Пример минимального остовного дерева приведен на рисунке 4(в).

Структура данных для представления дерева

Структура дерева может быть представлена массивом из n элементов по числу вершин в дереве. В этом случае требуется отобразить все связи вершин в дереве с учетом того, что каждая вершина имеет только одну предшествующую ей вершину. Используемый массив является массивом целых чисел, в котором индекс элемента массива (i) задает номер вершины дерева, а значение этого элемента соответствует номеру вершины, которая предшествует вершине i в дереве. Если i – корень дерева, то элемент не должен содержать номера вершины для чего можно задать значение "-1". Данные о ребрах дерева можно получить из массива следующим образом: начало ребра соответствует значению элемента массива, а конец ребра – индексу этого элемента.

Графическое представление структуры данных для графа изображено на рисунках 5(а) и 5(б). Пример описания массива на языке С++ представлен ниже,

int D[n], где D[i] – номер вершины, предшествующей вершине i в дереве.

D[i] = -1, если i – корень дерева

D[i] = j, если в дереве есть ребро e (v_j, v_i).

Таким образом, пара (D[i], i) определяет ребро дерева.

Поиски на графах. Поиск в глубину. Волновой алгоритм. Примеры программ

Рассмотрим вариант использования структуры данных представления дерева на примере реализации алгоритмов нахождения остовных ориентированных деревьев в неориентированном графе – "поиск в ширину" и "поиск в глубину". Техника этих алгоритмов используется в других алгоритмах решения задач на графах. Например, "поиск в ширину" является основой в алгоритме построения дерева кратчайших путей. "Поиск в глубину" решает задачу нахождения связных компонент в графе.

Рис. 6 – Структуры данных алгоритма «поиск в ширину»

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

Алгоритм 1. Алгоритм построения остовного дерева – "волновой алгоритм" ("поиск в ширину").

Шаг 1. Выбрать начальную (корневую) вершину. Объявить её помеченной и текущей.

Шаг 2. Образуем цикл просмотра всех смежных вершин, для чего от текущей вершины рассматриваем ее список смежности.

2.1. Проверка условия. Если смежная вершина не помеченная, то сделать ее помеченной, т.е. включить в дерево.

Шаг 3.

3.1. После просмотра всех вершин смежных с текущей вершиной объявить её просмотренной.

3.2. Из списка помеченных вершин выбрать любую непросмотренную и объявить ее текущей.

3.3. Если есть непросмотренные вершины, то перейти на шаг 2.

2.2. Проверка условия выхода из цикла. Если все вершины просмотрены, то конец алгоритма. Дерево построено.

Пример работы алгоритма "поиск в ширину" и формирования массива дерева представлен на рисунке 6.

Алгоритм 2. Алгоритм построения остовного дерева – "поиск в глубину".

Шаг 1. Выбрать исходную (корневую) вершину. Объявить помеченной и текущей.

Шаг 2. Образуем цикл просмотра смежных вершин от текущей вершины.

Шаг 3.

3.1. Проверка условия. Если в списке смежности текущей вершины непомеченных вершин нет, то

3.2. вернуться к ее предшественнику;

3.3. объявить предшественника текущей вершиной;

3.4. перейти на шаг 2.

Иначе,

3.5. объявить выбранную вершину помеченной и текущей;

3.6. Перейти на шаг 2.

3.7. Проверка условия. Если в результате поиска вернулись в исходную вершину и все вершины просмотрены, то конец алгоритма. Дерево построено.

Пример работы алгоритма "поиск в глубину" и формирования массива дерева представлен на рисунке 7.

Рис. 8 – Структуры данных алгоритма поиска связных компонент

Вариант 1

1. Построить модель сети в виде графа. Задать нумерацию вершин с 0. Задать граф в виде матрицы смежности. Задать граф в виде списка ребер с указателями. Найти степени вершин.

2. От вершины № 3 построить остовное дерево с применением алгоритмов «поиск в ширину», «поиск в глубину». Представить структуры деревьев в виде массивов.

3. Дать определения понятиям: Граф, цепь, остовное дерево.

Вариант 2

1. Построить модель сети в виде графа. Задать нумерацию вершин с 0. Задать граф в виде матрицы инциденций. Задать граф в виде списка ребер с указателями. Найти степени вершин.

2. От вершины № 2 построить остовное дерево с применением алгоритмов «поиск в ширину», «поиск в глубину». Представить структуры деревьев в виде массивов.

3. Дать определения понятиям: Плоский граф, маршрут, дерево.

Вариант 3

2. От вершины № 4 построить остовное дерево с применением алгоритмов «поиск в ширину», «поиск в глубину». Представить структуры деревьев в виде массивов.

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

Вариант 4

2. От вершины № 1 построить остовное дерево с применением алгоритмов «поиск в ширину», «поиск в глубину». Представить структуры деревьев в виде массивов.

3. Дать определения понятиям: Граф, цепь, остовное дерево.

Вариант 5

3. Дать определения понятиям: Граф, мультиграф, перечислить свойства дерева.

Вариант 6

2. От вершины № 6 построить остовное дерево с применением алгоритмов «поиск в ширину», «поиск в глубину». Представить структуры деревьев в виде массивов.

3. Дать определения понятиям: Суграф, цепь, остовное дерево.