2014 dxdy logo

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

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




 
 Графы(множество разделяющих вершин)
Сообщение21.12.2008, 15:13 
Помогите пожалуйста, мне нужен алгоритм нахождения в связном графе множества разделяющих вершин (подскажите литературу или интернет-ресурс).
По этой задаче есть вопрос , который не могу решить :
Что такое множество разделяющих вершин (не могу нигде найти определение)?

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

 
 
 
 
Сообщение21.12.2008, 22:31 
У меня проблема с тем что я никак не могу найти определения множества разделяющих вершин ,а поэтому не понятна задача.
Нашел определение разделяющей вершины (точки сочленения что одно и тоже)
Точкой сочленения графа называется вершина, удаление которой увеличивает число компонент связности.
Поэтому я понял так, что необходимо найти все вершины связного графа, обладающие таким свойством. Не знаю верна ли такая постановка задачи.

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


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