Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 3 ] |
|
Автор | Сообщение | |
---|---|---|
Vladislav |
|
|
Я нашел информацию, что для проверки на связность можно использовать алгоритм Дейкстры без указания (проверки) конечной точки. Но посмотрев сам алгоритм, не совсем понимаю, как его использовать, чтобы определить что граф связный или нет. В каком виде данные нам даны и как сделать выводы? |
||
Вернуться к началу | ||
Vladislav |
|
|
В общем, придумал такой вот выход из ситуации:
1) Забиваем граф в программу через матрицу смежности, предположим так: М24М 2М6М 46М3 ММ3М 2) теперь мы начинаем перебор всевозможных подграфов (Вот этот момент я не совсем могу сделать) 3) когда мы перебираем подграфы, мы производим следующие действия: допустим первая пара вершин 1 и 2, составляем матрицу а11,а12,а21,а22: М2 2М Суть в том, что если имеется хотя бы любая одна строка в которой все элементы равны М и хотя бы один столбец, в котором все элементы равны М, то граф несвязный. Если же нет таких строк и таких столбцов, то граф связный. Таким образом, проверив все подграфы, мы найдем все несвязные. Это слишком ужасно? И мб по перебору полному подскажете алгоритм подходящий или кусок кода на С++? |
||
Вернуться к началу | ||
mad_math |
|
|
Может можно как-то переделать алгоритмы для нахождения остовного дерева:
http://ru.wikipedia.org/wiki/%D0%9E%D1% ... 0%B2%D0%BE http://www.algolib.narod.ru/Graph/Ostov.html |
||
Вернуться к началу | ||
[ Сообщений: 3 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Алгоритм поиска всех деревьев в графе | 0 |
235 |
02 ноя 2014, 15:47 |
|
Счётность множества всех подмножеств счетного множества | 4 |
111 |
08 фев 2024, 19:56 |
|
Перебор делителей
в форуме Комбинаторика и Теория вероятностей |
1 |
226 |
16 окт 2022, 16:27 |
|
Перебор k комбинаций из n шаров в b корзинах
в форуме Комбинаторика и Теория вероятностей |
9 |
222 |
24 мар 2022, 22:40 |
|
Перебор крайних точек с заданным шагом
в форуме Линейная и Абстрактная алгебра |
7 |
483 |
28 окт 2015, 16:35 |
|
Перебор точек используя три вложенных цикла
в форуме MathCad |
1 |
303 |
24 ноя 2016, 10:08 |
|
Перебор сумм, которые будут максимально близки к таргету
в форуме Линейная и Абстрактная алгебра |
1 |
129 |
09 ноя 2021, 23:29 |
|
Множество подмножеств | 5 |
478 |
01 апр 2017, 20:28 |
|
Мощность разности подмножеств | 6 |
159 |
30 июн 2019, 21:07 |
|
Граф с вершинами из подмножеств | 10 |
243 |
30 июн 2019, 20:48 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 10 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |