Здравствуйте!
Помогите, пожалуйста, найти какой нибудь разрез и разделяющее множество вершин графа:

alt text

задан 5 Май '15 21:09

изменен 5 Май '15 21:41

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

Определение. Вершина графа, удаление которой увеличивает число компонент связности, называется разделяющейся. Получается множество {4} - разделяющее множество вершин.

(5 Май '15 21:28) 685597
1

Определение. Разделяющим множеством связного графа G называется такое множество его ребер, удаление которого приводит к несвязному графу. Определение. Разрезом называется такое разделяющее множество, никакое собственное подмножество которого не является разделяющим. Определение. Разрез, состоящий из одного ребра, называется мостом (перешейком).

{x4, x6} - разрез? {x5} - мост?

(5 Май '15 21:52) 685597
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×999

задан
5 Май '15 21:09

показан
422 раза

обновлен
5 Май '15 21:54

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru