2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Графы(множество разделяющих вершин)
Сообщение21.12.2008, 15:13 


16/08/07
65
Помогите пожалуйста, мне нужен алгоритм нахождения в связном графе множества разделяющих вершин (подскажите литературу или интернет-ресурс).
По этой задаче есть вопрос , который не могу решить :
Что такое множество разделяющих вершин (не могу нигде найти определение)?

 Профиль  
                  
 
 
Сообщение21.12.2008, 20:32 
Модератор
Аватара пользователя


11/01/06
5710
Скорее всего, имеется в виду задача минимального вершинного разреза:
http://www.nist.gov/dads/HTML/minvertexcut.html
Другими словами, вам нужно найти минимальное множество вершин, при удалении которых граф перестает быть связным, так?

 Профиль  
                  
 
 
Сообщение21.12.2008, 22:31 


16/08/07
65
У меня проблема с тем что я никак не могу найти определения множества разделяющих вершин ,а поэтому не понятна задача.
Нашел определение разделяющей вершины (точки сочленения что одно и тоже)
Точкой сочленения графа называется вершина, удаление которой увеличивает число компонент связности.
Поэтому я понял так, что необходимо найти все вершины связного графа, обладающие таким свойством. Не знаю верна ли такая постановка задачи.

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

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



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

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


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

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