Лекция 7. Определение связности узлов коммутации сети связи на основе теории графов Учебные и воспитательные цели: 1.Уяснить алгоритмы определения связности.

Презентация:



Advertisements
Похожие презентации
Теория графов Основные определения. Дуга Пусть имеется множество вершин V={V 1,V 2,…,V n } и пусть на нем задано бинарное отношение Г V×V, – V i Г V j.
Advertisements

Раскраски графов Раскраска вершин Пусть Г (V,E,Ф) – граф, раскраска вершин Г в n цветов – отображение f : V {1,2,…,n } Правильная раскраска вершин графа.
Двусвязность Лекция 14. Связность компонент Граф G называется k-связным (k 1), если не существует набора из k-1 или меньшего числа узлов V` V, такого,
Презентация по Информатике Тема: «Графы» Выполнил: Бычков Георгий.
Теория графов Основные определения. Дуга Пусть имеется множество вершин V={V 1,V 2,…,V n } и пусть на нем задано бинарное отношение Г V×V, – V i Г V j.
Введение в теорию графов. ЗАДАЧА ПРОКЛАДКИ КОММУНИКАЦИЙ
АВТОМАТИЧЕСКОЕ ФОРМИРОВАНИЕ УЗЛОВЫХ И КОНТУРНЫХ УРАВНЕНИЙ СЕТЕВОГО ОБЪЕКТА Назаренко Д.А., Чередникова О.Ю.
Теория графов. Теория графов – обширный самостоятельный раздел дискретной математики. Используется при проектировании компьютерных сетей, трубопроводов,
Теория графов Основные определения. Задание графов Графический способ – Привести пример графического задания графа, состоящего из вершин А, В и С, связанных.
Алгоритмы сканирования и обхода Лекция 3. Алгоритм сканирования графа Input: Орграф (граф) G и вершина s. Output: Множество R вершин, достижимых из s,
Построение остовного (покрывающего) дерева графа Преподаватель «И и ИКТ» ГБОУ лицея 1557 Куленчик Олеся Николаевна.
Графы Кенигсбергские мосты К XVIII веку через реку, на которой стоял город Кенигсберг (ныне Калининград), было построено 7 мостов, которые связывали.
Задача построения расписания конфигураций с ограниченной глубиной узлов для беспроводных сенсорных сетей Евгений Наградов.
Алгоритмы на графах. Задача о максимальном потоке в сетях Требуется от источника к стоку передать максимальное количество энергии. В условиях задачи о.
Списки, деревья, графы. Простой Индексированный список Связный и двусвязный список.
ХНУРЭ, кафедра ПО ЭВМ, Тел , Лекции Н.В. Белоус Факультет компьютерных наук Кафедра ПО ЭВМ, ХНУРЭ Компьютерная.
Алгоритм Флойда-Уоршалла Находит кратчайшие расстояния между всеми парами вершин графа Идея: Строится специальная матрица D, элементы которой – кратчайшие.
АЛГОРИТМЫ НАХОЖДЕНИЯ КРАТЧАЙШИХ ПУТЕЙ НА ГРАФАХ..
Алгоритмы на графах Волновой метод. Постановка задачи Постановка задачи. Пусть G – неориентированный связный граф, а и b – две его вершины. Требуется.
Задача построения расписания конфигураций с ограниченной глубиной узлов для беспроводных сенсорных сетей Евгений Наградов.
Транксрипт:

Лекция 7. Определение связности узлов коммутации сети связи на основе теории графов Учебные и воспитательные цели: 1. Уяснить алгоритмы определения связности вершин в ориентиро­ванных и неориентированных графах сетей связи.

Учебные вопросы 1. Поиск в глубину в графе. 2. Поиск в ширину в графе. 3. Метод построения дерева путей.

Вопрос 1. Поиск в глубину в графе. Алгоритм поиска: Поиск начинается с некоторой фиксированной вершины V o. Затем выбирается некоторая вершина V i смежная с V o и процесс повторяется от V i.

Вопрос 1. Поиск в глубину в графе. Алгоритм поиска: Пусть мы находимся в вершине V k. В стеке хранится список вершин через которые мы попали в V k. Если существует новая не просмотренная вершина (которой еще нет в стеке) и нет V k, то V k помещается в стек, поиск ведется далее от новой вершины, которая перестает быть новой.

Вопрос 1. Поиск в глубину в графе. Алгоритм поиска: Если же не существует ни одной новой вершины, смежной с V k, то мы считаем, что вершина V k использована, возвращаемся в вершину, из которой мы попали в V k и продолжаем процесс.

Вопрос 1. Поиск в глубину в графе. Алгоритм поиска: В ходе процесса будет формироваться список использованных вершин. Окончание процесса произойдет тогда, когда мы вернемся в вершину V o и отметим ее как использованную.

Вопрос 1. Поиск в глубину в графе

Вопрос 2. Поиск в ширину в графе. Алгоритм поиска: Процесс начинается с вершины V o - она тут же считается использованной. Далее ищутся все вершины, связанные с V o и они тут же считаются использованными. После этого делается третий шаг поиска. При этом использованными считаются только новые вершины, то есть те, которых нет в списке уже использованных. Процесс прекращается, когда на очередном шаге не находится ни одна новая вершина.

Вопрос 1. Поиск в глубину в графе

Вопрос 3. Метод построения дерева путей. Алгоритм поиска: 1. Корню дерева путей, образованному узлом- источником, присваивается нулевой уровень. 2. Из корня дерева путей строятся ветви первого уровня, на концах которых помещаются узлы первого уровня, непосредственно связанные в графе с узлом-источником.

Вопрос 3. Метод построения дерева путей. Алгоритм поиска: 3. Ветви второго уровня дерева путей строят из узлов, находящихся на первом уровне дерева, являющихся для этих ветвей корневыми. При этом из каждого узла первого уровня дерева путей выходит столько путей, со сколькими узлами графа непосредственно связан данный узел первого уровня, исключая узел-источник.

Вопрос 3. Метод построения дерева путей. Алгоритм поиска: 4. Строятся ветви и узлы третьего и последующих уровней аналогично пункту 3. При этом всякий узел графа может включаться в очередной уровень дерева путей, если этот узел в соответствующем образующемся пути ранее не встречался.

Вопрос 3. Метод построения дерева путей. Алгоритм поиска: 5. Построение дерева путей заканчивается тогда, когда в каждом пути будут охвачены все связи в графе. Как правило, в неориентированном графе это означает, что в каждом пути будут содержаться все узлы.

Вопрос 3. Метод построения дерева путей