ещё такое дело, на связанном взвешенном графе можно создать minimal spanning tree, то есть соединить все узлы рёбрами с минимальными весами, каждый узел будет иметь хотя бы одно ребро. из-за отсутсвия циклов получается дерево. допустим мне нужна подобная структура, но каждый узел хочу соединить хотя бы двумя рёбрами с остальным графом. появятся циклы и это уже не будет называтся деревом. в какую сторону копать?

а в чем проблема? алгоритмы базовые-то все равно сработают

кроме того, необязательно будут циклы, если ребра направленные

ещё такое дело, на связанном взвешенном графе можно создать minimal spanning tree, то есть соединить все узлы рёбрами с минимальными весами, каждый узел будет иметь хотя бы одно ребро. из-за отсутсвия циклов получается дерево. допустим мне нужна подобная структура, но каждый узел хочу соединить хотя бы двумя рёбрами с остальным графом. появятся циклы и это уже не будет называтся деревом. в какую сторону копать?

а это вообще возможно в общем случае?

какие там стандартные алгоритмы, Прим/Крускал?

кроме того, необязательно будут циклы, если ребра направленные

рёбра ненаправленые.

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

а это вообще возможно в общем случае?

ну а почему бы нет.

рёбра ненаправленые.

тогда тем более Прим/Крускал

тогда тем более Прим/Крускал

ну по приму я уже создал MST, нужно покумекать, как его обобщить.

ну а почему бы нет.

Ну докажи.

обобщить на что?

на N>1

ты вроде никаких изменений не назвал, которые его сломают :)

или я плохо понял

Кстати из поределения MST проистекает что добавить в него ребер без того, чтобы образовались циклы, нельзя.

Кстати из поределения MST проистекает что добавить в него ребер без того, чтобы образовались циклы, нельзя.

да, ибо результат это дерево.

Максимальное дерево

Кстати из поределения MST проистекает что добавить в него ребер без того, чтобы образовались циклы, нельзя.

я думаю, это из определения любого дерева так)

>допустим мне нужна подобная структура, но каждый узел хочу соединить хотя бы двумя рёбрами с остальным графом.

подобная эта какая?

структура, в которой каждая вершина имеет минимум два ребра, с минимальным общим весом?

не факт, что такая существует

я думаю, это из определения любого дерева так)

существуют такие деревья, в которые можно добавить ребра, и они останутся деревьями.

существуют такие деревья, в которые можно добавить ребра, и они останутся деревьями.

можно пример?

существуют такие деревья, в которые можно добавить ребра, и они останутся деревьями.

нет

существуют такие леса

Пустое дерево например

забыл уточнить, подобность в том, что помимо минимального ребра, добавить второе, следующее по "минимальности" веса ребро (и соответсвующий узел) ребро.

все равно непонятно, что нужно

Пустое дерево например

ну добавь ребро в пустое дерево

Пустое дерево например

если пустое дерево - это одна нода корня, то добавление ребра, ведущего в ту же ноду, добавляет в дерево цикл

Почему в ту же ноду?

если ноды корня нет - то это не дерево вообще

Почему в ту же ноду?

потому что если больше одной ноды - это уже не пустое дерево

Ладно, дерево из одного корня.

Ладно, дерево из одного корня.

см выше

Ладно, дерево из одного корня.

тогда по определению графа

Блин, вы не понимаете? Есть граф, есть дерево на нем.

Блин, вы не понимаете? Есть граф, есть дерево на нем.

мы понимаем :) сейчас мы тебе просто пытаемся доказать, что добавление ребра в дерево ВСЕГДА создает цикл

дерево и есть граф

неважно, остовное оно или какое еще

чувак говорит про подграф

типа, можно в графе сделать подграф-дерево

ребят, у меня знаний по теории графом почти нет. проблемму можно в принципе охарактеризовать примерно так: соедините все острова (каждый хотя бы двумя мостами) так, чтобы длина всех мостом была минимальна и все острова были соединены.

и если в нем не все вершины, то в него можно добавлять еще вершины с ребрами до них

мы понимаем :) сейчас мы тебе просто пытаемся доказать, что добавление ребра в дерево ВСЕГДА создает цикл

Только если все вершины графа уже в дереве.

ребят, у меня знаний по теории графом почти нет. проблемму можно в принципе охарактеризовать примерно так: соедините все острова (каждый хотя бы двумя мостами) так, чтобы длина всех мостом была минимальна и все острова были соединены.

задача коммивояжера, нет?

задача коммивояжера, нет?

Нет

Только если все вершины графа уже в дереве.

есть структура - дерево. Добавление ребра в дерево всегда создает цикл. Есть там при этом рядом где-то граф или нет - неважно

"существуют такие деревья, в которые можно добавить ребра, и они останутся деревьями."

Нет

почему?

вот твое утверждение, оно неверное

а хотя да, согласен

не она

это именно MST

есть структура - дерево. Добавление ребра в дерево всегда создает цикл. Есть там при этом рядом где-то граф или нет - неважно

А можно я добавлю вершину и к ней добавлю ребро?

А можно я добавлю вершину и к ней добавлю ребро?

тогда ты не просто добавишь ребро

задача коммивояжера, нет?

в комивояжоре нужно хотя бы один раз пройти, тут же два раза, и просто узлы соединить.

А можно я добавлю вершину и к ней добавлю ребро?

можно, но это будет уже не "добавление ребра"

а добавишь вершину и ребро

А где было про "только"

в комивояжоре нужно хотя бы один раз пройти, тут же два раза, и просто узлы соединить.

тут даже пройти не надо, задача не на путь, а на дерево минимальное

ребят, у меня знаний по теории графом почти нет. проблемму можно в принципе охарактеризовать примерно так: соедините все острова (каждый хотя бы двумя мостами) так, чтобы длина всех мостом была минимальна и все острова были соединены.

честно сказать - я до сих пор не понимаю, чем тебя не устраивает Крускал

тут даже пройти не надо, задача не на путь, а на дерево минимальное

если бы было бы дерево, это решалось простым MST, то соединений должно быть хотя бы два.

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

если бы было бы дерево, это решалось простым MST, то соединений должно быть хотя бы два.

а, то есть ты хочешь не остовное дерево, а граф, в котором из каждой ноды минимум два ребра?

ERROR: S client not available

Короче топикстартеру: представь у тебя не направленный граф с вершинами A,B,C и ребрами AB, BC, CD. Тогда построить на нем твою структуру (минимум два ребра для каждною вершину) без циклов нельзя.

а, то есть ты хочешь не остовное дерево, а граф, в котором из каждой ноды минимум два ребра?

именно.

Короче топикстартеру: представь у тебя не направленный граф с вершинами A,B,C и ребрами AB, BC, CD. Тогда построить на нем твою структуру (минимум два ребра для каждною вершину) без циклов нельзя.

тогда его структура совпадает с этим графом

все условия соблюдены

Только если все вершины графа уже в дереве.

Дерево и есть граф

Дерево и есть граф

лол

лол

ты ебана ребячишь нас?

Короче топикстартеру: представь у тебя не направленный граф с вершинами A,B,C и ребрами AB, BC, CD. Тогда построить на нем твою структуру (минимум два ребра для каждною вершину) без циклов нельзя.

топикстартер не прочь циклов.

топикстартер не прочь циклов.

то есть в твоей структуре могут быть ребра, которых не было в начальном графе?

и насколько я могу судить дерево и есть граф, но не каждый граф дерево.

и насколько я могу судить дерево и есть граф, но не каждый граф дерево.

все так

Да, но я боюсь это не то что Vasiliy имел в виду.

я подозреваю, что он именно это и имел в виду

просто немного не поняли друг друга

Да, но я боюсь это не то что Vasiliy имел в виду.

Определение: дерево - связный граф без циклов

Всё

Никакого ещё одного графа побольше там нет

Определение: дерево - связный граф без циклов

немного хитрее с направленными

то есть в твоей структуре могут быть ребра, которых не было в начальном графе?

ну как бы есть просто задача, соединить все острова мостами, если допустить условие "соединить всё хотя бы одним мостом" то решение тривиальное - MST, я подумал, а что если условие поменять на "каждый остров соединить хотя бы двумя мостами" - как же это можно решать?

топикстартер не прочь циклов.

короче, если у тебя нельзя в результат добавлять дополнительные ребра, то структура, которую ты хочешь получить, запросто может и не существовать, как написали выше

немного хитрее с направленными

Ну это строго говоря ориентированное дерево

Граф может быть деревом, но не ориентированным деревом

Ну это строго говоря ориентированное дерево

это я к тому, что в графе может не быть циклов и все равно он не будет деревом при этом

там где даги

там напряги

ну как бы есть просто задача, соединить все острова мостами, если допустить условие "соединить всё хотя бы одним мостом" то решение тривиальное - MST, я подумал, а что если условие поменять на "каждый остров соединить хотя бы двумя мостами" - как же это можно решать?

ты определись, тебе надо на существующем графе посчитать или тебе надо построить руками граф с нуля по имеющимся вершинам

Давайте я переформулирую задачу топикстартера. Есть ненаправленный граф G (V, E) со тепенью вершин не менее 2. Построить граф G1 (V, E1) такой что E1 подмножество E, стемень всех вершин равна 2 и сумма весов ребер E1 минимальна.

https://e-maxx.ru/algo/mst_kruskal

Давайте я переформулирую задачу топикстартера. Есть ненаправленный граф G (V, E) со тепенью вершин не менее 2. Построить граф G1 (V, E1) такой что E1 подмножество E, стемень всех вершин равна 2 и сумма весов ребер E1 минимальна.

задача нерешаема при данной постановке, вот в чем проблема :)

https://e-maxx.ru/algo/mst_kruskal

да я писал уже это выше, тут не про то

задача нерешаема при данной постановке, вот в чем проблема :)

Ну давай контрпример.

а, хотя бы двумя мостами