Двусвязный компонент неор. графа — максимальное множество рёбер, такое что любые два ребра принадлежат общему простому циклу.
Удаление мостов из графа раскладывает граф на двусвязные компоненты.
Собственно со вторым утверждением проблемы. Подскажите как доказать, что любой компонент после удаления мостов двусвязен?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
Если в граф добавить ребро из одной компоненты в другую, ребра, которые были мостами, останутся мостами.Пускай есть ребро, которое до удаления всех мостов не было мостом, а потом стало. Добавим все мосты обратно, противоречие с предыдущим утверждением.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 рёберно двусвязных компоненты.
а, понял. С вашим определением плохо согласуется, да.
Потому что есть две двусвязности. Реберная и вершинная. Утверждение верно для реберной, в посте определение реберной. То, о чем вы думаете — видимо вершинная.Да, согласился, что определением в топике не согласуется.
Видимо нужно изменить простому на "непересекающемуся по ребрам".
А куда можно попытаться сдать, не подскажите?