Тема: Свойство бисвязности ориентированного графа
Характеристики работы
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
📋 Содержание
Графо-теоретические понятия 4
Связность, достижимость 5
Поиск в глубину 8
Алгоритм Косарайю 13
Реализация алгоритмов Габова и Тарьяна 17
Заключение 19
Список литературы 20
📖 Введение
Мне было поручено сделать обзор имеющихся алгоритмов анализа связности ориентированного графов.
В этом анализе большую роль играют понятия «шарниры» и «компоненты сильной связности». Грубо говоря, шарниры - это вершины, такие, что разделение графа в них делит граф на сильно-связные компоненты.
Мне нужно было выяснить, какие сейчас приняты методы выделения в графе сильно¬связных компонент.
Оказалось, есть три известных популярных алгоритма, которые и описываются в этой работе. К сожалению, конкурировать с этими алгоритмами я не смогла.
Основное внимание в работе уделено алгоритму Косарайю.
✅ Заключение
В литературе есть программы этих методов, построенных на популярном методе в глубину.
Алгоритмы настолько маленькие, что их оказалось возможным привести полностью.