Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 3 ] 
Автор Сообщение
 Заголовок сообщения: Перебор всех связных подмножеств в графе
СообщениеДобавлено: 18 май 2014, 20:06 
Не в сети
Начинающий
Зарегистрирован:
18 май 2014, 19:52
Сообщений: 3
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Здравствуйте. Мне необходимо написать алгоритм, который будет находить все возможные связные подграфы в неориентированном графе. Перебор всевозможных подграфов в графе осуществить не особо сложно, но хотелось бы, чтобы каждый вариант проходил проверку на то, является ли он связным, иначе слишком много места занимать будут данные, да и дольше алгоритм работать будет. И как потом посчитать временную сложность алгоритма? Читал, что если задать граф списками смежности, то программа будет работать быстрей, только вот какие тогда алгоритмы использовать...

Я нашел информацию, что для проверки на связность можно использовать алгоритм Дейкстры без указания (проверки) конечной точки. Но посмотрев сам алгоритм, не совсем понимаю, как его использовать, чтобы определить что граф связный или нет. В каком виде данные нам даны и как сделать выводы?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Перебор всех связных подмножеств в графе
СообщениеДобавлено: 18 май 2014, 23:03 
Не в сети
Начинающий
Зарегистрирован:
18 май 2014, 19:52
Сообщений: 3
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
В общем, придумал такой вот выход из ситуации:
1) Забиваем граф в программу через матрицу смежности, предположим так:
М24М
2М6М
46М3
ММ3М
2) теперь мы начинаем перебор всевозможных подграфов (Вот этот момент я не совсем могу сделать)
3) когда мы перебираем подграфы, мы производим следующие действия:
допустим первая пара вершин 1 и 2, составляем матрицу а11,а12,а21,а22:

М2


Суть в том, что если имеется хотя бы любая одна строка в которой все элементы равны М и хотя бы один столбец, в котором все элементы равны М, то граф несвязный. Если же нет таких строк и таких столбцов, то граф связный.
Таким образом, проверив все подграфы, мы найдем все несвязные.

Это слишком ужасно? И мб по перебору полному подскажете алгоритм подходящий или кусок кода на С++?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Перебор всех связных подмножеств в графе
СообщениеДобавлено: 19 май 2014, 10:49 
Не в сети
Верховный модератор
Аватара пользователя
Зарегистрирован:
13 окт 2010, 13:09
Сообщений: 19961
Откуда: Пермь + Одесса
Cпасибо сказано: 11721
Спасибо получено:
5319 раз в 4796 сообщениях
Очков репутации: 708

Добавить очки репутацииУменьшить очки репутации
Может можно как-то переделать алгоритмы для нахождения остовного дерева:
http://ru.wikipedia.org/wiki/%D0%9E%D1% ... 0%B2%D0%BE
http://www.algolib.narod.ru/Graph/Ostov.html

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 3 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Алгоритм поиска всех деревьев в графе

в форуме Дискретная математика, Теория множеств и Логика

Aquilo

0

235

02 ноя 2014, 15:47

Счётность множества всех подмножеств счетного множества

в форуме Дискретная математика, Теория множеств и Логика

Uebermarginal

4

111

08 фев 2024, 19:56

Перебор делителей

в форуме Комбинаторика и Теория вероятностей

Fyodor272000

1

226

16 окт 2022, 16:27

Перебор k комбинаций из n шаров в b корзинах

в форуме Комбинаторика и Теория вероятностей

aryaStark

9

222

24 мар 2022, 22:40

Перебор крайних точек с заданным шагом

в форуме Линейная и Абстрактная алгебра

Brook_m

7

483

28 окт 2015, 16:35

Перебор точек используя три вложенных цикла

в форуме MathCad

George_Smith

1

303

24 ноя 2016, 10:08

Перебор сумм, которые будут максимально близки к таргету

в форуме Линейная и Абстрактная алгебра

donny_hipp

1

129

09 ноя 2021, 23:29

Множество подмножеств

в форуме Дискретная математика, Теория множеств и Логика

Quintessencion

5

478

01 апр 2017, 20:28

Мощность разности подмножеств

в форуме Дискретная математика, Теория множеств и Логика

e7min

6

159

30 июн 2019, 21:07

Граф с вершинами из подмножеств

в форуме Дискретная математика, Теория множеств и Логика

e7min

10

243

30 июн 2019, 20:48


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 10


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved