|
Докажите, что простой граф $%G$%, построенный на трёх или более вершинах, двусвязен тогда и только тогда, когда для любой тройки различных вершин $%(x,y,z)$% в $%G$% есть простой путь из $%x$% в $%z$%, проходящий через $%y$%. задан 25 Мар '16 20:51 
gus |
|
простите, не очень понял - в ответе доказывается что двусвязность эквивалентна тому свойству, что в графе нет такой тройки $%x$%,$%y$%,$%z$% что любой путь из $%x$% в $%z$% проходит через $%y$%, а в вопросе говорится о другом свойстве - что для любой тройки $%x$%,$%y$%,$%z$% существует путь из $%x$% в $%z$% проходящий через $%y$%.. или эквивалентность этих свойств очевидна? для меня честно говоря нет, Вы не могли бы немного пояснить? отвечен 19 Окт '16 2:41 
solitude2 Думаю, Вы правы: я в комментарии рассмотрел нечто другое. Тогда попробуем исправить. В одну сторону: пусть есть точка сочленения. Обозначим её через z, а две точки, которые нельзя соединить иначе как через z, пусть будут x и y. Тогда из x в z нет простого пути через y, так как его начало от х до у проходило бы через z, и путь не был бы простым.
(19 Окт '16 9:33)
falcao
В обратную сторону чуточку посложнее. Известно, что в двусвязном графе через любые две вершины проходит простой цикл. Тогда берём два таких цикла: один содержит х и у, второй у и z. Получаем подграф. Среди таких подграфов, в которых есть простые циклы для двух пар вершин, выбираем тот, у которого меньше всего рёбер. Тогда геометрически получаются две окружности, пересекающиеся по "дуге" (возможно, одноточечной) в окрестности точки y (в противном случае можно из подграфа что-то удалить без потери свойств). Тогда ясно, что простой путь из x в z через y имеется (опять-таки, "наглядно").
(19 Окт '16 9:36)
falcao
|
|
Спасибо! А не подскажете, нельзя ли в обратную сторону по аналогии с прямым провести рассуждение (нет ли тут ошибки): Пусть не существует простого пути между какими-то вершинами $%x$% и $%z$%, проходящего через какую-то вершину $%y$%. Тогда $%x$% является точкой сочленения, так как при его удалении не остается никакого пути из $%y$% в $%z$% (так как в исходном графе любой путь между ними мог либо проходить через $%x$%, либо вовсе не существовать - в противном случае существовал бы простой путь из $%x$% в $%z$% через $%y$%). отвечен 20 Окт '16 2:49
solitude2 точнее, сразу можно отбросить случай когда между какими-то двумя вершинами в графе нет пути (т.к. тогда он даже не односвязный), и тогда если не существует пути из 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
|
Допустим, что в графе есть точка сочленения. Пусть это $%y$%. Она соединена с $%k\ge2$% вершинами. Удаление $%y$% вместе с инцидентными ей рёбрами даёт несвязный граф. В нём имеются какие-то вершины $%x$% и $%z$%, которые не соединить в таком графе. Значит, в исходном графе есть тройка $%(x,y,z)$% с требуемым свойством.
Обратно, пусть любой путь из $%x$% в $%z$% ведёт через $%y$%. Выбрасываем $%y$% вместе с инцидентными рёбрами. Тогда из $%x$% в $%z$% уже не пройти.