|
|
Строка 1: |
Строка 1: |
− | Пусть дан связный неориентированный граф. Мост - ребро, при удалении которой граф становится несвязным.
| |
| | | |
− | Первым делом введем новые виды ребер :
| |
− |
| |
− | Ребра самого ДФС (tree edge или ребро дерева).
| |
− |
| |
− | Ребра не посещенные в ДФС (back edge или. обратное ребро).
| |
− |
| |
− | Пусть есть ребро
| |
− | u
| |
− | →
| |
− | v
| |
− | , в каком случае оно является мостом, понятно, что обратное ребро не может быть мостом, потому что мы уже посещали обе вершины и следовательно есть путь по ребрам самого ДФС. Теперь разберемся с ребрами ДФС. Они являются мостом, только если нет пути по обратным ребрам в какого-то из предков
| |
− | v
| |
− | . Так как иначе мы можем удалить это ребро, но при этом останется путь по обратным ребрам.
| |
− |
| |
− | Давайте докажем, что если путь до предка существует, то существует и путь, такой, что нам достаточно пройти по одному обратному ребру. Пусть такого пути не существует, но при этом есть какой-то путь из
| |
− | n
| |
− | обратных ребер, тогда давайте посмотрим куда могут вести эти ребра, они могут вести либо в поддерево вершины
| |
− | u
| |
− | , либо в нее саму, либо в наддерево, в случае поддерева или самой вершины мы можем их убрать, так как есть путь по ребрам ДФС, в случае наддерева же нам достаточно сохранить только одно ребро в наддерево.
| |
− |
| |
− | Тогда давайте введем
| |
− | d
| |
− | p
| |
− | i
| |
− | - минимальный
| |
− |
| |
− | t
| |
− | i
| |
− | n
| |
− | такой вершины, до которой мы можем добраться за какое-то количество ребер ДФС и одно обратное. Как его пересчитывать. Очень просто : у нас есть три возможных значения динамики.
| |
− |
| |
− | d
| |
− | p
| |
− | i
| |
− | =
| |
− | m
| |
− | i
| |
− | n
| |
− | (
| |
− | t
| |
− | i
| |
− | n
| |
− | i
| |
− | ,
| |
− | d
| |
− | p
| |
− | i
| |
− | )
| |
− |
| |
− | d
| |
− | p
| |
− | i
| |
− | =
| |
− | m
| |
− | i
| |
− | n
| |
− | (
| |
− | d
| |
− | p
| |
− | i
| |
− | ,
| |
− | d
| |
− | p
| |
− | s
| |
− | o
| |
− | n
| |
− | )
| |
− | , где
| |
− | s
| |
− | o
| |
− | n
| |
− | - сын
| |
− | i
| |
− | -й вершины
| |
− |
| |
− | d
| |
− | p
| |
− | i
| |
− | =
| |
− | m
| |
− | i
| |
− | n
| |
− | (
| |
− | d
| |
− | p
| |
− | i
| |
− | ,
| |
− | t
| |
− | i
| |
− | n
| |
− | b
| |
− | a
| |
− | c
| |
− | k
| |
− | )
| |
− | , где
| |
− | b
| |
− | a
| |
− | c
| |
− | k
| |
− | - вершина, для которой есть обратное ребро из
| |
− | i
| |
− | -й вершины.
| |
− |
| |
− | Научимся понимать, какое ребро - ребро ДФС, а какое обратное. Если ребро ведет в уже использованную вершины, то это обратное ребро, иначе ребро ДФС.
| |