| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Максимальная клика в графе |
| Автор: Аланта 29.12.2005, 14:55 |
| Как найти максимальную клику в графе? Что-то я не соображу алгоритм. Может кто знает? |
| Автор: esperant0 29.12.2005, 22:34 |
| перебором не пробовали:? |
| Автор: дентомед:) 9.1.2006, 15:01 |
| А что такое клика? |
| Автор: poor_yorik 15.1.2006, 23:13 |
| Клика - это полный подграф данного графа. Самое лучшее решение такое. Строим граф Г* - дополнение нашего графа, то есть там где ребра в графе были там их не будет, а где их не было будут.  Тогда задача нахождения максимальных клик нашего графа, будет аналогичной нахождению максимальных независимых подмножеств в графе Г* (то бишь таких множеств вершин, среди которых никакие две не смежны, и все другие вершины графа смежны хотя бы одной вершине множества). Тогда нашим решением будет макимальное независимое подмножество графа Г*. Если неизвестен алгоритм нахождения максимальных независимых подмножеств графа, могу скинуть.  |
| Автор: esperant0 16.1.2006, 01:29 | ||
Это не самое лучшее решение. Я все тот же перебор, экспоненциальный. Кроме того что используется перебор еще нужно и редукцию делать. И еще если вы пишите самое лучшее решение то пишите по какому критерию оно лучшее, а то имхо на самое худшее тянет |
| Автор: poor_yorik 16.1.2006, 13:30 |
| esperant0 Интересно, где ты тут редукцию увидел??? Поделись... Я не спорю, что задача нахождения максимальных подмножеств это вообщем перебор, но довольно усеченнный  Если сравнить скорость алгоритма нахождения макисмального независимого подмножества и простого перебора, то для случаев где количество вершин побольше, перебор работает заметно (!!!)дольше. Если у вас есть другой более эфективный вариант усечения перебора, прошу поделится. А непереборного решения задачи про клики насколько мне известно, до сих пор найдено не было. |