Докажите, что простой граф $%G$%, построенный на трёх или более вершинах, двусвязен тогда и только тогда, когда для любой тройки различных вершин $%(x,y,z)$% в $%G$% есть простой путь из $%x$% в $%z$%, проходящий через $%y$%.

задан 25 Мар '16 20:51

1

Допустим, что в графе есть точка сочленения. Пусть это $%y$%. Она соединена с $%k\ge2$% вершинами. Удаление $%y$% вместе с инцидентными ей рёбрами даёт несвязный граф. В нём имеются какие-то вершины $%x$% и $%z$%, которые не соединить в таком графе. Значит, в исходном графе есть тройка $%(x,y,z)$% с требуемым свойством.

Обратно, пусть любой путь из $%x$% в $%z$% ведёт через $%y$%. Выбрасываем $%y$% вместе с инцидентными рёбрами. Тогда из $%x$% в $%z$% уже не пройти.

(25 Мар '16 22:51) falcao
10|600 символов нужно символов осталось
1

простите, не очень понял - в ответе доказывается что двусвязность эквивалентна тому свойству, что в графе нет такой тройки $%x$%,$%y$%,$%z$% что любой путь из $%x$% в $%z$% проходит через $%y$%, а в вопросе говорится о другом свойстве - что для любой тройки $%x$%,$%y$%,$%z$% существует путь из $%x$% в $%z$% проходящий через $%y$%.. или эквивалентность этих свойств очевидна? для меня честно говоря нет, Вы не могли бы немного пояснить?

ссылка

отвечен 19 Окт '16 2:41

изменен 19 Окт '16 2:46

Думаю, Вы правы: я в комментарии рассмотрел нечто другое. Тогда попробуем исправить. В одну сторону: пусть есть точка сочленения. Обозначим её через z, а две точки, которые нельзя соединить иначе как через z, пусть будут x и y. Тогда из x в z нет простого пути через y, так как его начало от х до у проходило бы через z, и путь не был бы простым.

(19 Окт '16 9:33) falcao

В обратную сторону чуточку посложнее. Известно, что в двусвязном графе через любые две вершины проходит простой цикл. Тогда берём два таких цикла: один содержит х и у, второй у и z. Получаем подграф. Среди таких подграфов, в которых есть простые циклы для двух пар вершин, выбираем тот, у которого меньше всего рёбер. Тогда геометрически получаются две окружности, пересекающиеся по "дуге" (возможно, одноточечной) в окрестности точки y (в противном случае можно из подграфа что-то удалить без потери свойств). Тогда ясно, что простой путь из x в z через y имеется (опять-таки, "наглядно").

(19 Окт '16 9:36) falcao
10|600 символов нужно символов осталось
0

Спасибо! А не подскажете, нельзя ли в обратную сторону по аналогии с прямым провести рассуждение (нет ли тут ошибки): Пусть не существует простого пути между какими-то вершинами $%x$% и $%z$%, проходящего через какую-то вершину $%y$%. Тогда $%x$% является точкой сочленения, так как при его удалении не остается никакого пути из $%y$% в $%z$% (так как в исходном графе любой путь между ними мог либо проходить через $%x$%, либо вовсе не существовать - в противном случае существовал бы простой путь из $%x$% в $%z$% через $%y$%).

ссылка

отвечен 20 Окт '16 2:49

точнее, сразу можно отбросить случай когда между какими-то двумя вершинами в графе нет пути (т.к. тогда он даже не односвязный), и тогда если не существует пути из x в z через y, то это возможно лишь в силу того что любой путь из y в z проходит через x

(20 Окт '16 2:58) solitude2

хотя кажется увидел ошибку в своем рассуждении - простой путь из x в z через y может не существовать в силу того все что пути из x в y и из y в z попарно имеют какие-то общие вершины (вовсе не обязательно x), и наверное тут правда не построишь такого же рассуждения про точку сочленения..

(20 Окт '16 3:06) solitude2

@solitude2: из отсутствия простых путей x-z, проходящих через y, не следует, что x есть точка сочленения. Возьмём две окружности, соединённые "мостиком". Пусть x и z лежат на первой окружности, а y на второй. Тогда простым путём через y не пройти, но x не точка сочленения.

(20 Окт '16 9:31) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×413
×247
×142
×136
×7

задан
25 Мар '16 20:51

показан
778 раз

обновлен
20 Окт '16 9:31

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

по почте:

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

по RSS:

Ответы

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

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