Четвертая итерация - Лекция, раздел Образование, Введение в теорию графов 1. Лекция: Графы и способы их представления Ш А Г 2. Находим Г(Х8) = { Х1, Х5, Х6...
Ш А Г 2. Находим Г(х8) = { х1, х5, х6, х9 }. Метки вершин х5, х6 и х9 временные, следовательно, пересчитываем их значения:
L(х5) = min [ ∞ , 6 + 23 ] = 29,
L(х6) = min [ 17, 6 + 15 ] = 17,
L(х9) = min [ 12, 6 + 5 ] = 11.
Ш А Г 3. На данном шаге итерации имеем следующие временные метки вершин:
L(х3) = 23, L(х4) = 7,
L(х5) = 29, L(х6) = 17, L(х9) = 11.
Очевидно, что минимальную метку, равную 7 имеет вершина х4 .
Ш А Г 4. За следующую текущую метку принимаем вершину х4 , т. е. p = х4 , а ее метка становится постоянной, L(х4) = 7+ .
Ш А Г 5. Так как не все вершины графа имеют постоянные метки, переходим к шагу 2.
Введение в теорию графов Лекция Графы и способы их представления... Приводятся начальные сведения о графах и основные понятия и определения такие как орграф смешанный граф дубликат графа дуга петля полустепени...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Четвертая итерация
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Основные определения
Граф задается множеством точек или вершин х1, х2, ..., хn и множеством линий или ребер a1, a2, ... , am, соеди
Прямые отображения
Прямым отображением 1-го порядка вершины хi является множество таких вершин графа, для которых существует дуга (хi, xj), т. е Г1( х
Обратные отображения
Обратным отображением 1-го порядка для вершины хiявляется множество элементов xjтаких, что существует дуга(xj, хi), принадлежащая множеству дуг графа, т.
Прямое транзитивное замыкание
Прямым транзитивным замыканием некоторой вершины хi – T+( хi )является объединение самой вершины хiс прямыми отображениями 1-го поря
Обратное транзитивное замыкание
Обратным транзитивным замыканием некоторой вершины хi –T-( хi )является объединение этой вершины с обратными отображениями 1-го, 2-го и т. д. n
Нахождение транзитивных замыканий по матрице смежности
Рассмотрим метод нахождения прямого транзитивного замыкания по матрице смежности, показанной на рис. 3.3,а для вершины х2графа, изображенного на рис. 3.3,б. На 1-м шаге итерации заносим
Достижимость и контрдостижимость
Задач, в которых используется понятие достижимости, довольно много. Вот одна из них. Граф может быть моделью какой-то организации, в которой люди представлены вершинами, а дуги интерпретирую
Нахождение множества вершин, входящих в путь
Если необходимо узнать о вершинах графа, входящих в эти пути, то следует вспомнить определения прямого и обратного транзитивных замыканий. Так как T+(xi) – это множество верши
Матричный метод нахождения путей в графах
Матрица смежности полностью определяет структуру графа. Возведем матрицу смежности в квадрат по правилам математики. Каждый элемент матрицы А2 определяется по формуле
a(2)
Доказательство
1. Необходимость. Поскольку множество X разбивается на две части Xа и Xb , то Xа Xb = X и Xа Xb = Ø .
Пусть существ
Лекция: Виды подграфов
Пусть дан граф G = (X, A), где X = {хi}, i = 1, 2, ..., n – множество вершин, A = { ai }, i = 1, 2, ..., m – множество дуг.
Подграфом
Сильно связные графы и компоненты графа
Кроме классификации типов графов данной в п. 3.1 графы могут быть классифицированы по связности: сильно связные, односторонне связные, слабо связные и несвязные.
Орграф называется
Метод Мальгранжа
Пусть дан граф G=(X, A), где X={ хi }, i =1, 2, ... , n – множество вершин, а A={ ai }, i =1, 2, ..., m – где множество дуг, описанных матрицей смежности. Алгоритм разбиени
Пути и маршруты
Путем в орграфе называется последовательность дуг, в которой конечная вершина всякой дуги, кроме последней, является начальной вершиной следующей дуги.
Например, для г
Вес и длина пути
Иногда дугам графа сопоставляют числа ai сi , называемые весом или длиной, или стоимостью или ценой. В каждом конкретном случае выбирается то слово, которое ближе подходит по
Орциклы и циклы
Особую группу составляют замкнутые пути. Путь a1, a2, ...,aq называется замкнутым, если в нем начальная вершина a1 и конечная вер
Лекция: Алгоритм Дейкстра поиска кратчайших путей в графе
Наиболее эффективный алгоритм решения задачи о кратчайшем пути первоначально дал Дейкстра . В общем случае этот метод основан на приписывании вершинам временных пометок, причем поме
Превращение пометки в постоянную
Ш А Г 3. Среди всех вершин с временными пометками найти такую, для которой
L(x*i)=min[L(xi)].
Ш А Г 4. Считать пометку вершины x*i
Первая итерация
Ш А Г 2. Найдем прямое отображение для текущей рассматриваемой вершины: Г(р) = Г(х1) = { х2, х7, х8, х9 }. Все вершины, входящие в прямое отоб
Вторая итерация
Граф с текущими значениями меток вершин показан на рис. 9.3
Рис. 9.3. Пометки в конце первой итерации
Ш А Г 2. Находим Г(х7) = { х
Третья итерация
Граф с текущими значениями меток вершин показан на рис. 9.4.
Рис. 9.4. Пометки в конце второй итерации
Ш А Г 2. Находим Г(х2) = {х
Пятая итерация
Ш А Г 2. Находим Г(х4) = { х3, х5, х6, х7 }. Метки вершин х3, х5 и х6 временные, следовательно, пересчитываем
Шестая итерация
Ш А Г 2. Находим Г(х9) = {х1, х2, х6, х7, х8}. Метка вершины х6 временная, следовательно пересчитываем ее значение:
Седьмая итерация
Ш А Г 2. Находим Г(х5) = { х4, х6 }. Метка вершины х6 временная, следовательно, пересчитываем ее значение:
L(х6)= min [17, 12 + 10 ]
Восьмая итерация
Ш А Г 2. Находим Г(х6) = { х3, х5, х7, х8, х9 }. Метка вершины х3 временная, следовательно, пересчитываем ее значение:
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов