Всем привет! Разбирается тут кто-то в графах? Мне нужно создать

Question

Всем привет! Разбирается тут кто-то в графах? Мне нужно создать

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

#database #programming #russian #software

0

09.03.2021

8 ответов

10 просмотров

Nikolay Prokopev

Только не бейте меня, но prolog. Подобные задачи на нем решаются очень быстро. Практически у каждого языка программирования есть библиотеки для интегрирования кода пролога

0

09.03.2021

Dima Автор вопроса

Даниил Агниашвили
Красно-черное дерево?

Почитал сейчас, но как мне показалось, это немного другая тема

0

09.03.2021

Даниил Агниашвили

Dima
Почитал сейчас, но как мне показалось, это немного...

О, показалось что то же самое, но хорошо, помог чем смог

0

09.03.2021

Ihor

Я, конечно, дилетант в графах и уже жду море критики но все же)))) Что, если построить матрицу графа, и делать так: - берём первую интересующую нас красную вершину и находим путь с помощью поиска в глубину/ширину до интересующих нас синих вершин. Нашли-обнулили колонки соответствующих вершин, по которым прошлись. - повторяем процедуру, пока: а) сумма по колонкам хотя бы из одной категории (синие, красные) будет равняться 0 б) нельзя будет соединить пару вершин. Можно добавить условие, что, если есть несколько соединений для одной красной вершины, то должна выбираться та, после которой сумма/ранг матрицы будет максимальным...

0

09.03.2021

Михаил Адигеев

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

0

10.03.2021

Dima Автор вопроса

Михаил Адигеев
Добрый вечер. На рисунке у вас не просто графы, а ...

Здравствуйте, да именно для деревьев, забыл уточнить

0

10.03.2021

Михаил Адигеев

Dima
Здравствуйте, да именно для деревьев, забыл уточни...

У деревьев есть такое свойство: любые две вершины соединены ровно одним путем. То есть, по крайней мере разные пути перебирать не придется. Можно построить множество путей, соединяющих синие вершины с красными, их будет br штук, где b - количество синих вершин, r - количество красных. И построить новый граф, в котором вершинами будут эти самые пути, а ребра соединяют любые две вершины, для которых соответствующие пути на исходном графе пересекаются. И на полученном графе найти наибольшее независимое множество вершин. Это и будет точное решение. Правда, поиск наибольшего независимого множества вершин - вычислительно сложная задача :(

0

11.03.2021

Даниил Агниашвили · Accepted Answer

Даниил Агниашвили

Красно-черное дерево?

0

09.03.2021

215 похожих чатов

Всем привет! Разбирается тут кто-то в графах? Мне нужно создать

8 ответов

Похожие вопросы