|
|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail | |||||||
| Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
||||
 |
|
|
Опции темы | Поиск в этой теме |
22.01.2010, 22:50
|
#1 |
|
Регистрация: 19.07.2009
Сообщений: 9
|
Генерация связного графа
Может поможет кто...В процедуру передаётся количество вершин, и количество рёбер которые нужно сгенерировать. Граф задан матрицей смежности. Необходимо написать процедуру которая будет генерировать такую матрицу смежности, содержащую n-вершин и m-рёбер. Желательно быстрый алгоритм.Он в дальнейшем нужен для анализа работы алгоритмов поиска Гамильтонового и Эйлерова циклов, и подсчёта за определённое время сгенерированных графов разного типа. Буду благодарен за подсказки...
|
|
|
|
23.01.2010, 00:30
|
#2 |
|
Регистрация: 19.07.2009
Сообщений: 9
|
Никто не подскажет?
|
|
|
|
|
23.01.2010, 00:57
|
#3 |
|
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Граф должен быть средневероятностным по какому признаку? Просто написать генератор графа за параметрами не сложно, но если графы должны быть разного типа и различатся в пределах одного типа, то по каким признакам как раз различать эти графы? Важны случайность количества циклов, размеров циклов, количества мостов и т.д.?
|
|
|
|
|
23.01.2010, 01:46
|
#4 |
|
Регистрация: 19.07.2009
Сообщений: 9
|
Ничего не важно..Главное чтобы граф содержал n-вершин и m-рёбер..причём был связным...граф неориентированный..я представляю этот код небольшим, но так почему-то неполучилось чего-то толкового..
|
|
|
|
|
23.01.2010, 12:17
|
#5 |
|
Регистрация: 19.07.2009
Сообщений: 9
|
Подскажет кто-нибудь что-нибудь по этому поводу?
|
|
|
|
|
23.01.2010, 13:16
|
#6 |
|
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Простой способ генерации - делаем нужное количество вершин, розганяем их по подмножествам и объеденем все подмножества в одно поочередно (алгоритм Таржана) с рендомной базой каркаса. Когда будет одно - у нас уже есть связный граф с необходимым количеством вершин и на 1 меньшим количеством ребер. Если нужные еще ребра - можна банально рэндомно выбирать пару вершин и, если она не соедена ребром - соеденять, пока не будет достаточно ребер.
|
|
|
|
|
23.01.2010, 15:46
|
#7 |
|
Регистрация: 19.07.2009
Сообщений: 9
|
Можно по простому как-то? Без всяких там замудрёных алгоритмов. Рандомно не получится потому что не все вершины захватываются..Нужно во первых же чтобы все n вершин использовались, а во вторых чтобы они были связаны все между собой
|
|
|
|
|
Похожие темы
|
||||
| Тема | Автор | Раздел | Ответов | Последнее сообщение |
| Создание связного списка на Си | zx11 | Общие вопросы C/C++ | 9 | 17.03.2014 00:54 |
| Рисование графа | templllar | Общие вопросы .NET | 0 | 16.12.2009 12:17 |
| сортировка узлов связного списка | pavelstraut | Общие вопросы C/C++ | 5 | 28.07.2009 23:27 |
| Связность графа. | Пaвeл | Помощь студентам | 0 | 26.04.2009 10:42 |
