Двусвязный компонент неор. графа — максимальное множество рёбер, такое что любые два ребра принадлежат общему простому циклу.
Удаление мостов из графа раскладывает граф на двусвязные компоненты.
Собственно со вторым утверждением проблемы. Подскажите как доказать, что любой компонент после удаления мостов двусвязен?
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
3 дня
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
3 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 2 | maomao90 | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 20.11.2024 10:24:43 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
Если в граф добавить ребро из одной компоненты в другую, ребра, которые были мостами, останутся мостами.Пускай есть ребро, которое до удаления всех мостов не было мостом, а потом стало. Добавим все мосты обратно, противоречие с предыдущим утверждением.Irrelevant.
Рассмотрим произвольные 2 вершины(u,v) из 1 компоненты. Проведем произвольный непересек.путь между ними. Рассмотрим самую дальнюю вершину от u по этому пути, до которой можно добраться по ребрам не из этого пути. Пусть это не v, а x. уберем ребро (xy) в этом пути, начинающееся в x. xy не мост. Значит существует путь от x до куда-то из пути yv. Если были пересечения с путем ux то, от них несложно избавиться. взяв только куски пути
Если компонент не двусвязен то он либо не связен вообще либо в нем есть мост.
Господа, второе утверждение, я думаю, не совсем корректно написано.
В исходной постановке утверждение звучит так: "Докажите, что двусвязные компоненты графа G составляют разбиение множества всех рёбер графа, не являющихся мостами".
Как следует правильно понять его? Следует ли из него ровно то, что из оставшихся рёбер, можно образовать двусвязные компоненты?
То есть я, наверное, погорячился со словом "раскладывает", потому что под ним я понимал, что оставшиеся рёбра образуют связные компоненты, которые в свою очередь являются двусвязными. Но на это есть контрпример.
Приведите контрпример, может я чего-то не понял, но мне показалось что вам доказали что утверждение верно.
Graph
Очевидно, что удалив мост CE, останется 3 двусвязных компонента. При этом связных 2.
FGHEI — 1 компонента по вашему определению.
У меня их два(определния). Одно неверно (то, что в топике). По крайней мере оно противоречиво данному примеру. Компонента два(ABCD, FGHEI). Двусвязных — 3 (ABCD, FGE, EIH).
речь идет о рёберной двусвязности. для рёберной двусвязности у тебя 2 связных компоненты и 2 рёберно двусвязных компоненты.
а, понял. С вашим определением плохо согласуется, да.
Потому что есть две двусвязности. Реберная и вершинная. Утверждение верно для реберной, в посте определение реберной. То, о чем вы думаете — видимо вершинная.Да, согласился, что определением в топике не согласуется.
Видимо нужно изменить простому на "непересекающемуся по ребрам".
А куда можно попытаться сдать, не подскажите?