Алгоритм Мальгранжа
Поделись знанием:
– Нельзя ли достать книгу? – сказал он.
– Какую книгу?
– Евангелие! У меня нет.
Доктор обещался достать и стал расспрашивать князя о том, что он чувствует. Князь Андрей неохотно, но разумно отвечал на все вопросы доктора и потом сказал, что ему надо бы подложить валик, а то неловко и очень больно. Доктор и камердинер подняли шинель, которою он был накрыт, и, морщась от тяжкого запаха гнилого мяса, распространявшегося от раны, стали рассматривать это страшное место. Доктор чем то очень остался недоволен, что то иначе переделал, перевернул раненого так, что тот опять застонал и от боли во время поворачивания опять потерял сознание и стал бредить. Он все говорил о том, чтобы ему достали поскорее эту книгу и подложили бы ее туда.
– И что это вам стоит! – говорил он. – У меня ее нет, – достаньте, пожалуйста, подложите на минуточку, – говорил он жалким голосом.
Доктор вышел в сени, чтобы умыть руки.
– Ах, бессовестные, право, – говорил доктор камердинеру, лившему ему воду на руки. – Только на минуту не досмотрел. Ведь вы его прямо на рану положили. Ведь это такая боль, что я удивляюсь, как он терпит.
Алгоритм Мальгранжа — метод для разбиения графа на сильно связные подграфы.
Алгоритм
Пусть дан граф G=(X, A), где X={ хi }, i =1, 2, … , n — множество вершин, а A={ ai }, i =1, 2, …, m — где множество дуг, описанных матрицей смежности. Алгоритм разбиения заключается в следующем .
- Для произвольной вершины хi ∈ X находим прямое T+(хi) и обратное T-(хi) транзитивные замыкания.
- Находим T+(хi) ∩ T-(хi). Множество вершин этого пересечения составляют вершины максимального сильно связного подграфа G1 = (Х1, A1).
- Из исходного графа вычитаем подграф G1:G '=G\G1, Х=X\Х1 .
- Граф G 'принимаем за исходный граф и пока X ' ≠ Ø пункты 1, 2, 3 алгоритма повторяются.
Напишите отзыв о статье "Алгоритм Мальгранжа"
Литература
- А. Кофман. Введение в прикладную комбинаторику. — М.: Наука, 1975. — С. 166. — 480 с.
Ссылки
- Тамара Волченская, Владимир Князьков, [www.intuit.ru/studies/courses/1033/241/lecture/6220 Курс «Введение в теорию графов», Лекция 7: «Методы разбиения графа на максимальные сильно связные подграфы»] // Интуит.ру, 2008
<imagemap>: неверное или отсутствующее изображение |
Для улучшения этой статьи по математике желательно?:
|
Отрывок, характеризующий Алгоритм Мальгранжа
– Моя то с? Ничего. Вот вы то? – Князь Андрей опять задумался, как будто припоминая что то.– Нельзя ли достать книгу? – сказал он.
– Какую книгу?
– Евангелие! У меня нет.
Доктор обещался достать и стал расспрашивать князя о том, что он чувствует. Князь Андрей неохотно, но разумно отвечал на все вопросы доктора и потом сказал, что ему надо бы подложить валик, а то неловко и очень больно. Доктор и камердинер подняли шинель, которою он был накрыт, и, морщась от тяжкого запаха гнилого мяса, распространявшегося от раны, стали рассматривать это страшное место. Доктор чем то очень остался недоволен, что то иначе переделал, перевернул раненого так, что тот опять застонал и от боли во время поворачивания опять потерял сознание и стал бредить. Он все говорил о том, чтобы ему достали поскорее эту книгу и подложили бы ее туда.
– И что это вам стоит! – говорил он. – У меня ее нет, – достаньте, пожалуйста, подложите на минуточку, – говорил он жалким голосом.
Доктор вышел в сени, чтобы умыть руки.
– Ах, бессовестные, право, – говорил доктор камердинеру, лившему ему воду на руки. – Только на минуту не досмотрел. Ведь вы его прямо на рану положили. Ведь это такая боль, что я удивляюсь, как он терпит.
