рефераты конспекты курсовые дипломные лекции шпоры

  • Раздел Образование
  •  / 
  • Вид работы: Лекции
  •  / 
  • Нахождение транзитивных замыканий по матрице смежности

Реферат Курсовая Конспект

Нахождение транзитивных замыканий по матрице смежности

Нахождение транзитивных замыканий по матрице смежности - Лекция, раздел Образование, Введение в теорию графов 1. Лекция: Графы и способы их представления Рассмотрим Метод Нахождения Прямого Транзитивного Замыкания По Матрице Смежно...

Рассмотрим метод нахождения прямого транзитивного замыкания по матрице смежности, показанной на рис. 3.3,а для вершины х2графа, изображенного на рис. 3.3,б. На 1-м шаге итерации заносим 0 в столбец Т+для элемента х2и просматриваем 2-ю строку матрицы. Находим, что элементы a22=1и a25=1. Заносим 1 в 5-ю клетку Т+. 2-я клетка уже занята нулем, поэтому 1 не заносим. 2-й шаг начинается просмотром 5-й строки матрицы смежности, соответствующий вершине х5графа. Находим, что элементы a51=1 и a54=1, т. е. из вершины х5 имеются дуги в вершины х1 и х4 или иначе из вершины х2 имеются пути длиной 2 в вершины х1 и х4. Длину пути 2 заносим в 1-ю и 4-ю клетки столбца T+(х2). На 3-м шаге анализируются 1-я и 4-я строки матрицы смежности А. Находим элементы a12=1, a13=1, a43=1. В соответствующие свободные клетки заносим значения

 

Рис. 3.3. Построение прямого (а) и обратного (в) транзитивных замыканий для графа (б)

Это возможно сделать только для вершины х3, так как вторая клетка уже занята. Анализ 3-й строки матрицы на 4-м шаге показывает, что из вершины х3нет исходящих дуг, следовательно, процесс формирования прямого транзитивного замыкания завершен.

Таким образом, в столбце T+(х2)стоят числа равные длине пути от вершины х2 к соответствующим вершинам графа. Путь от х2 к х3равный 3 показан штриховой линией на рис. 3.3,б. В столбце T+(х2) отмечены все вершины, достижимые из вершины х2, следовательно, они входят в T+(х2).

T+( х2 ) = { х1, х2, х3, х4, х5 }.

Во втором столбце показано построение прямого транзитивного замыкания вершины х1 – T+(х1).

T+( х1 ) = { х1, х2, х3, х4, х5 }.

Нахождение обратного транзитивного замыкания по матрице смежности показано на рис. 3.1,в. Рассмотрим нахождение обратного транзитивного замыкания вершины х3 – T-( х3 ), которое на-чинается с занесения 0 в 3-ю клетку строки T-( х3 ). На 1-м шаге алгоритма, помеченного стрелкой с цифрой 1, просматриваем 3-й столбец матрицы А. Определяем элементы равные 1, т. е. a13=1 и a43=1. Следовательно, в графе из вершин х1 и х4 есть дуги в вершину х3. Заносим 1 в 1-ю и 4-ю клетки T-(х3). На втором шаге просматриваем 1-й и 4-й столбцы матрицы A. Находим a51=1, a61=1, a54=1и проставляем 2 (так как длина пути от этих вершин до вершины х3 равна 2) в свободные клетки T-(х3), т. е. в 5-ю и 6-ю клетки. 3-й шаг заключается в просмотре 5-го и 6-го столбцов матрицы A. Элементы a25=1, a65=1, a66=1 позволяют поставить 3 во 2-ю клетку строки T-( х3 ). 4-й шаг просмотра 2-го столбца дает элементы a12 = 1 и a22 = 1, уже вошедшие в T-(х3). Итак, сфор-мировано обратное транзитивное замыкание для вершины х3.

T-( х3 ) = { х1, х2, х3, х4, х5, х6 }.

Числа, стоящие в клетках T-( х3 ), показывают длину кратчайшего пути от соответствующих вершин до вершины х3.

Во второй строке показано формирование обратного транзитивного замыкания вершины х1.

T-( х1 ) = { х1, х2, х5, х6 }.

 

Развернуть
Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

Введение в теорию графов 1. Лекция: Графы и способы их представления

Введение в теорию графов Лекция Графы и способы их представления... Приводятся начальные сведения о графах и основные понятия и определения такие как орграф смешанный граф дубликат графа дуга петля полустепени...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Нахождение транзитивных замыканий по матрице смежности

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Основные определения
Граф задается множеством точек или вершин х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

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

Нахождение множества вершин, входящих в путь
Если необходимо узнать о вершинах графа, входящих в эти пути, то следует вспомнить определения прямого и обратного транзитивных замыканий. Так как 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. Находим Г(х8) = { х1, х5, х6, х9 }. Метки вершин х5, х6 и х9 временные, следовательно, пересчитываем

Пятая итерация
Ш А Г 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 временная, следовательно, пересчитываем ее значение:

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги