2014 dxdy logo

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

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




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


30/07/10
254
Здравствуйте. Я с теорией графов почти не знаком, но вот наткнулся на такую задачу. Я полагаю, должны существовать стандартные алгоритмы решения таких задач.

Каждое ребро графа связывает 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 
Заслуженный участник
Аватара пользователя


18/01/13
11962
Казань
Такие подмножества называются кликами. Ваша задача - о поиске максимальной клики. Это, кажется, NP-сложная задача.

 Профиль  
                  
 
 Re: Найти наибольшее число попарно связанных вершин графа
Сообщение26.11.2014, 19:01 
Аватара пользователя


27/07/14
39
Да, это задача о поиске максимальной клики. Решается при помощи метода ветвей и границ (алгоритм Брона-Кербоша). Сложность в худшем случае $O(3^{n/3})$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Toucan, maxal, PAV, Karan, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group