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, Супермодераторы



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

Сейчас этот форум просматривают: Bing [bot]


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

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