Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия, Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
Рассматривается неориентированный граф. Каждой вершине поставлено в соответствие некоторое натуральное число, которое назовем весом вершины. Необходимо каждому ребру поставить в соответствие неотрицательное целое число (назовем его количеством связей, порожденных ребром) так, чтобы 1) сумма количеств связей, порожденных ребрами выходящими из одной вершины, не превосходила веса этой вершины; 2) общее количество связей в графе было максимальным, т.е. должна быть максимальной сумма количеств связей, порожденных всеми ребрами графа.
Буду признателен за любую информацию по этой задаче.
Geen
Re: максимальное количество связей в графе
12.06.2015, 14:05
Последний раз редактировалось Geen 12.06.2015, 14:08, всего редактировалось 1 раз.
Вроде бы линейное программирование, нет? (причём, похоже, ввиду единичных коэффициентов вполне должен работать жадный алгоритм)
назовем его количеством связей, порожденных ребром
Больше похоже на "кратность" ребра
xelAlex
Re: максимальное количество связей в графе
12.06.2015, 14:52
Эту задачу, безусловно, можно сформулировать как задачу линейного программирования. Но поскольку получится достаточно специфическая матрица, обладающая рядом интересных свойств, то возникает вопрос: не имеет ли эта задача более "хорошего" решения? Меня эта задача интересует в первую очередь с теоретической точки зрения, в частности, интересно какие здесь можно сформулировать общие закономерности, какие-то характерные частные случаи, примеры и т.д. Задача возникла в прикладной области (я не спец в диск мат) и мне нужно понять, что с ней делать. Вариантов, собственно говоря, два: 1) Найти книжку или статью, где эта задача исследована; 2) Попытаться исследовать ее самостоятельно.
Поэтому, если Вы встречали такую задачу или можете подсказать где ее имеет смысл поискать (я не ориентируюсь в литературе по данной тематике), то я буду Вам очень благодарен.
Xaositect
Re: максимальное количество связей в графе
12.06.2015, 15:07
Последний раз редактировалось Xaositect 12.06.2015, 15:07, всего редактировалось 1 раз.
Задача сводится к поиску макс. потока в графе - вместо каждой вершины делаем две вершины, соединенные ребром с заданной пропускной способностью, ребра тоже раздваиваем.