|
|
| Строка 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
| |
| − | -й вершины.
| |
| − |
| |
| − | Научимся понимать, какое ребро - ребро ДФС, а какое обратное. Если ребро ведет в уже использованную вершины, то это обратное ребро, иначе ребро ДФС.
| |