Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия, Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
Помогите пожалуйста, мне нужен алгоритм нахождения в связном графе множества разделяющих вершин (подскажите литературу или интернет-ресурс).
По этой задаче есть вопрос , который не могу решить :
Что такое множество разделяющих вершин (не могу нигде найти определение)?
maxal
21.12.2008, 20:32
Скорее всего, имеется в виду задача минимального вершинного разреза:
http://www.nist.gov/dads/HTML/minvertexcut.html Другими словами, вам нужно найти минимальное множество вершин, при удалении которых граф перестает быть связным, так?
mvb13
21.12.2008, 22:31
У меня проблема с тем что я никак не могу найти определения множества разделяющих вершин ,а поэтому не понятна задача.
Нашел определение разделяющей вершины (точки сочленения что одно и тоже)
Точкой сочленения графа называется вершина, удаление которой увеличивает число компонент связности.
Поэтому я понял так, что необходимо найти все вершины связного графа, обладающие таким свойством. Не знаю верна ли такая постановка задачи.