Граф Герца

@Елизавет Андрее · Регистрация: 09.11.2009

Студворк — интернет-сервис помощи студентам

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

ориентированный граф сильно связен, если для любой пары вершин u,v существует путь из u в v. Компонентой сильной связности назовем произвольный максимальный сильно связный подграф. Конденсацией ориентированного графа (или графом герца или фактор-графом) называется орграф, который получается стягиванием в одну вершину каждой компоненты сильной связности графа. написать прогу построения графа Герца

@odip · 05.12.2009, 17:03

Задача такая в форуме была.
Но вот решил кто или нет не знаю

@Елизавет Андрее · 05.12.2009, 17:45 **[ТС]**

я писала ее недавно,но никто не ответил,думаю может сейчас кто поможет ...
эх

@odip · 05.12.2009, 21:08

А какие трудности ?
Оптимальный алгоритм не знаю какой, а на вид задачу можно решить в лоб.

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

Значит у нас есть набор МССП.
Осталось сделать конденсацию.
В качестве вершин выберем набор МССП. Один МCCП - одна вершина.
Связи же между МССП установим как связи между вершинами, входящими в МССП.

@Елизавет Андрее · 07.12.2009, 10:13 **[ТС]**

трудности в том,что я еще не умею ничего писать =(

@Елизавет Андрее · 08.12.2009, 18:12 **[ТС]**

кто-нибудь может знает?

Новые блоги и статьи Все статьи Все блоги /
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом	http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .

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

	Граф Герца 05.12.2009, 15:21. Показов 2729. Ответов 5 Метки нет (Все метки) Всем привет! не могли бы вы помочь с написанием задачи вот на такую тему. ориентированный граф сильно связен, если для любой пары вершин u,v существует путь из u в v. Компонентой сильной связности назовем произвольный максимальный сильно связный подграф. Конденсацией ориентированного графа (или графом герца или фактор-графом) называется орграф, который получается стягиванием в одну вершину каждой компоненты сильной связности графа. написать прогу построения графа Герца 0

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164
	05.12.2009, 17:03
	Задача такая в форуме была. Но вот решил кто или нет не знаю 0

@Елизавет Андрее 1 / 1 / 0 Регистрация: 09.11.2009 Сообщений: 73
	05.12.2009, 17:45 [ТС]
	я писала ее недавно,но никто не ответил,думаю может сейчас кто поможет ... эх 0

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164
	05.12.2009, 21:08
	А какие трудности ? Оптимальный алгоритм не знаю какой, а на вид задачу можно решить в лоб. Добавлено через 5 минут Берем произвольную вершину, строим вокруг нее максимальный сильно связный подграф (МССП). И так далее - пока не обойдем все вершины. В итоге у нас будет куча МССП и просто вершины, которые не удалось расширить. Если подумать, то одна вершина которую невозможно расширить, тоже является МССП. Значит у нас есть набор МССП. Осталось сделать конденсацию. В качестве вершин выберем набор МССП. Один МCCП - одна вершина. Связи же между МССП установим как связи между вершинами, входящими в МССП. 0

@Елизавет Андрее 1 / 1 / 0 Регистрация: 09.11.2009 Сообщений: 73
	07.12.2009, 10:13 [ТС]
	трудности в том,что я еще не умею ничего писать =( 0

@Елизавет Андрее 1 / 1 / 0 Регистрация: 09.11.2009 Сообщений: 73
	08.12.2009, 18:12 [ТС]
	кто-нибудь может знает? 0