Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Елизавет Андрее
1 / 1 / 0
Регистрация: 09.11.2009
Сообщений: 73
#1

Граф Герца - C++

05.12.2009, 15:21. Просмотров 1011. Ответов 5
Метки нет (Все метки)

Всем привет!
не могли бы вы помочь с написанием задачи вот на такую тему.


ориентированный граф сильно связен, если для любой пары вершин u,v существует путь из u в v. Компонентой сильной связности назовем произвольный максимальный сильно связный подграф. Конденсацией ориентированного графа (или графом герца или фактор-графом) называется орграф, который получается стягиванием в одну вершину каждой компоненты сильной связности графа. написать прогу построения графа Герца
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.12.2009, 15:21     Граф Герца
Посмотрите здесь:

Программа построения графа Герца C++
Граф C++
C++ Граф
Считать граф из файла (граф задан матрицей) представить его в виде списка и записать список заново в файл C++
C++ Двудольный граф??
Вроде бы граф C++
Граф C++
C++ Граф в С
Граф C++
Покрашенный граф C++
подсвязный граф в си++ C++
Граф C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
05.12.2009, 17:03     Граф Герца #2
Задача такая в форуме была.
Но вот решил кто или нет не знаю
Елизавет Андрее
1 / 1 / 0
Регистрация: 09.11.2009
Сообщений: 73
05.12.2009, 17:45  [ТС]     Граф Герца #3
я писала ее недавно,но никто не ответил,думаю может сейчас кто поможет ...
эх
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
05.12.2009, 21:08     Граф Герца #4
А какие трудности ?
Оптимальный алгоритм не знаю какой, а на вид задачу можно решить в лоб.

Добавлено через 5 минут
Берем произвольную вершину, строим вокруг нее максимальный сильно связный подграф (МССП).
И так далее - пока не обойдем все вершины.
В итоге у нас будет куча МССП и просто вершины, которые не удалось расширить.
Если подумать, то одна вершина которую невозможно расширить, тоже является МССП.

Значит у нас есть набор МССП.
Осталось сделать конденсацию.
В качестве вершин выберем набор МССП. Один МCCП - одна вершина.
Связи же между МССП установим как связи между вершинами, входящими в МССП.
Елизавет Андрее
1 / 1 / 0
Регистрация: 09.11.2009
Сообщений: 73
07.12.2009, 10:13  [ТС]     Граф Герца #5
трудности в том,что я еще не умею ничего писать =(
Елизавет Андрее
1 / 1 / 0
Регистрация: 09.11.2009
Сообщений: 73
08.12.2009, 18:12  [ТС]     Граф Герца #6
кто-нибудь может знает?
Yandex
Объявления
08.12.2009, 18:12     Граф Герца
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru