Конспект лекций по предмету "Теория графов"

Узнать цену работы по вашей теме


Метод Мальгранжа

Пусть дан граф G=(X, A), где X={ хi }, i =1, 2, ... , n – множество вершин, а A={ ai }, i =1, 2, ..., m – где множество дуг, описанных матрицей смежности. Алгоритм разбиения заключается в следующем [4].
Для произвольной вершины хi X находим прямое T+(хi) и обратное T-(хi) транзитивные замыкания. Находим T+(хi) T-(хi). Множество вершин этого пересечения составляют вершины максимального сильно связного подграфа G1 = (Х1, A1). Из исходного графа вычитаем подграф G1:G '=GG1, Х'=XХ1 . Граф G 'принимаем за исходный граф и пока X ' Ø пункты 1, 2, 3 алгоритма повторяются. Рассмотрим этот алгоритм более подробно на примере разбиения графа, представленного на рис. 7.1,a, матрица смежности которого показана на рис. 7.1,б.

Рис. 7.1.
РАЗБИЕНИЕ – 1 .
Таблица 7.1.


X1
X7
X11

X1



A7=
X7




X11



Начальной вершиной первого разбиения выберем х1 . Построим прямое и обратное транзитивные замыкания. T+(х1)– столбец, показанный справа от матрицы А, а T-(х1) – строка, находящаяся ниже матрицы смежности. T+(х1) = {х1, х4, х5, х6, х7, х8, х11 },
T-(х1) = {х1, х2, х3, х7, х9, х10, х11}.
Находим T+(х1) T-(х1) = {х1, х7, х11}. Эти вершины и составляют первый выделенный, максимальный сильно связный подграф G1 = (Х1, A1), где Х1 = {х1, х7, х11}, а матрица смежности A1 подграфа G1 показана на таблица 7.1. Из исходного графа G вычитаем подграф G1 G ' = G G1 ; G ' = (X ', A'), X ' = { х2, х3, х4, х5, х6, х8, х9, х10 }.
Так как X ' не пустое множество, то G' принимаем за G и переходим ко второму разбиению. РАЗБИЕНИЕ – 2
Таблица 7.2.


X2
X3
X4
X5
X6
X8
X9
X10

T+(x2)

X2











X3











X4











X5










A=
X6











X8











X9











X10























T-(x2)










Выбираем любую вершину, принадлежащую X, например, х2 , и находим T+(х2) и T-(х2). Это показано в таблице 7.2. T+(х2) = { х2, х8 }; T-(х2) = { х2 }. T+(х2) T-(х2) = { х2 }. Следовательно, второй выделенный подграф G2 состоит из одной вершины х2 . G ' = G G2; G ' = (X ', A'); X ' = { х3, х4, х5, х6, х8, х9, х10 }. Так как X ' не пустое множество, то G ' принимаем за G и процесс разбиения продолжается.


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


Не сдавайте скачаную работу преподавателю!
Данный конспект лекций Вы можете использовать для создания шпаргалок и подготовки к экзаменам.

Доработать Узнать цену работы по вашей теме
Поделись с друзьями, за репост + 100 мильонов к студенческой карме:

Пишем конспект самостоятельно:
! Как написать конспект Как правильно подойти к написанию чтобы быстро и информативно все зафиксировать.

Другие популярные конспекты:

Конспект Основные проблемы и этапы развития средневековой философии
Конспект Проблема познаваемости мира. Гносеологический оптимизм, скептицизм, агностицизм. Взаимосвязь субъекта и объекта познания
Конспект Понятие финансовой устойчивости организации
Конспект Внутренняя политика первых Романовых.
Конспект ПРОБЛЕМЫ КВАЛИФИКАЦИИ ПРЕСТУПЛЕНИЙ
Конспект Понятие мировоззрения, его уровни и структура. Исторические типы мировоззрения
Конспект Синтагматические, парадигматические и иерархические отношения в языке
Конспект Тема 1.2. Плоская система сходящихся сил. Определение равнодействующей геометрическим способом 13
Конспект Происхождение человека. Основные концепции антропосоциогенеза. Антропогенез и культурогенез.
Конспект Общая характеристика процессов сбора, передачи, обработки и накопления информации