2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Найти наибольшее число попарно связанных вершин графа
Сообщение24.11.2014, 19:11 
Аватара пользователя
Здравствуйте. Я с теорией графов почти не знаком, но вот наткнулся на такую задачу. Я полагаю, должны существовать стандартные алгоритмы решения таких задач.

Каждое ребро графа связывает 2 различные вершины. Между каждой парой вершин может быть не более одного ребра. Нужно найти множество максимальной мощности, такое, что любая пара вершин из этого множества связана графом. Например, есть граф из пяти вершин (обозначенных цифрами):
{1, 2, 3, 4, 5}
и 8 рёбер:
1-2
1-3
1-4
1-5
2-3
2-4
3-4
3-4
В результате мы должны получить множество {1, 2, 3, 4}. Вершина 5 в это множество не войдёт, т.к. она не связана с вершинами {2, 3, 4}.

 
 
 
 Re: Найти наибольшее число попарно связанных вершин графа
Сообщение24.11.2014, 19:39 
Аватара пользователя
Такие подмножества называются кликами. Ваша задача - о поиске максимальной клики. Это, кажется, NP-сложная задача.

 
 
 
 Re: Найти наибольшее число попарно связанных вершин графа
Сообщение26.11.2014, 19:01 
Аватара пользователя
Да, это задача о поиске максимальной клики. Решается при помощи метода ветвей и границ (алгоритм Брона-Кербоша). Сложность в худшем случае $O(3^{n/3})$.

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group