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

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

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

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

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

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


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

Программа построения графа Герца - C++
добрый вечер! вот есть такая задачка Ориентированный граф сильно связен, если для любой пары вершин u,v существует путь из u в v....

Считать граф из файла (граф задан матрицей) представить его в виде списка и записать список заново в файл - C++
помогите очень срочно надо. считать граф из файла (граф задан матрицей) представить его в виде списка и записать список заново в файл ...

Граф - C++
Дан граф в виде матрицы смежности 7х7(вводится вручную либо загружается из файла) нужно реализовать только такие функции: вычислить: ...

Граф в С - C++
Не могли бы помочь.. как можно построить граф в С ? или где модно прочесть про то как создать файл в который этот граф нарисуется?

Граф - C++
Помогите описать граф в С++ списками. По какому принципу это делается ?

Граф - C++
Найти все вершины неориентированного графа, к которым существует путь заданной длины от выделенной его вершины. не могу разобраться,...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
odip
Эксперт С++
7157 / 3297 / 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
Эксперт С++
7157 / 3297 / 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
кто-нибудь может знает?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.12.2009, 18:12
Привет! Вот еще темы с ответами:

Граф - C++
2. Имеется N населенных пунктов (N≤15), и сеть авиалиний, соединяющих эти города. Сеть задана матрицей связности M(N,N), где M(i,j) =0,...

Граф - C++
В городе N площадей. Любые две площади соединены между собой ровно одной дорогой с двусторонним движением. В этом городе живет Штирлиц. У...

Покрашенный граф - C++
Привет для вот такого условия Дан ориентированный граф, у которого каждая дуга покрашена в один из трех цветов. Требуется найти длину...

Двудольный граф?? - C++
Проверка является ли граф двудольным))


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
08.12.2009, 18:12
Ответ Создать тему
Опции темы

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