------------> LECTION-01

Дан орграф.

Сводимость
Ранжировка = выделен корень (source), можно занумеровать вершины так,
  что по любому пути из корня номера взорастают.

------------> LECTION-02

Фрагмент
Луч
Альт.
Интервал
Иерархия

------------> LECTION-03

* Def

Бикомпонента = макс. по включению сильносвязное множество
Зона = любое сильносвязное множество

* Theorem:

Граф не сводим <=> Существует зона B: |Entry(B)| > 1
Entry - количество вершин, в которые что-то входит.

* Def

Область = R(v) = {u : N(v) <= N(u) and u --> v (и на пути не встречаются вершины с меньшими номерами) }
N - порядок по убыванию времени выхода.
M - порядок по возрастанию времени входа.
Области определены на конкретном остовном дереве dfs-а в графе!

* Утверждение: R(v) - сильносвязно. (т.к. M(v) тоже <= M(u), R(v) = циклы проходящие через v по поддереву v)

Док-во: (1) 'u' лежит в поддереве, (2) вместе с 'u' можно добавить цикл.

* Утверждение: R(v) (т.е. области) образуют иерархию (R(u) <= R(v), если u лежит в R(v))

T-нумерация.
Определяется алгоритмом: Дана N-нумерация. Обходим граф рекурсивно.
Когда входим в 'v' сперва перечисляем вершины R(v) (в том же порядке, что и в N).

По фиксированной N-нумерации можно построить T-нумерацию такую, что все дуги имеют по N и по T нумерациям одинаковое направление.

* Def.
Иерархия вложеннах зон (B). Для любых i и j. Множество входов не пересекаются.

Для сводимого графа.
1) Области не зависят от дерева
2) Вход в каждую область единственный
3) Области задают иерархия вложенных зон

Алгоритм посотроения иерархии областей за O(E):
1) Иерархия = ссылка для каждой вершины v : prev[v]
2) Обходим граф в глубину.
3) Стягиваем области
4) Ребра в графе храним только те, которые идут между областями.
5) Чтобы найти цикл, который расширяет область от v, просматриваем его ребра в обратном порядке.

* Гамак. Def.

Гамак = Альт с единым стоком. (End(H) <= 1)

* Theorem: пусть есть область и гамак, тогда они или не пересекаются, или вкладываются.

* Линейная компонента. Def.

Граф разбивается на линейные компоненты.
Как цепочка.
Каждая линейная компонента - гамак.
Разбиение максимально подробно и дизъюнктно.

Можно определить по-другому.
Линейная компонента - такой гамак, что любой путь из фиктивного начала в фиктивный конец проходит через гамак.
И нет подгамака, обладающего тем же свойством.
И из конца нельзя попасть в начало.

------------> LECTION-04

КОНТРОЛЬНАЯ РАБОТА.
Зачет >= 50 Баллов.
                       
------------> LECTION-05

Гамак = один вход, один выход = кусок кода, который можно вынести в функцию.
Гамаки (все) не образуют иерархию: берем цепочку, любая ее подцепь - гамак.
Гамак - прежде всего альт.
Объединение гамаков (пересекающихся по вершине) = гамак.
Max гамаки: H(v) - иерархия.
Пересечение гамаков - почти всегда гамак. Но не всегда. (Может быть 2 выхода)

Пусть у нас есть области.

****
Определок:
Все вершины орграфа достижимы из истока S.
Зафиксируем дерево обхода в глубину.
Область от вершины = R(v) = множество вершин поддерева v, из которых достижима v "не выходя из дерева".
****

Области построены по dfs-обходу, т.е. есть N нумерация (убывание времени выхода).
Можно повторить обход dfs-ом с некоторым изменением нумерации:
T-нумерация получается так: обходим сперва всю бикомпоненту.
T-нумерация получается так: обходим сперва всю область.

Алгоритм получения иерархии областей:
1) Обходим дерево снизу
2) Уже найденные области храним сжатыми в одну вершину.
3) Ребро добавляем в граф, только тогда, когда поднялись до LCA его концов.
4) Чтобы найти очередной цикл откатываемся по обратным ребрам вниз по дереву и сжимаем все, что находим.


---------------------> sites.google.com/~shkredov

Алгоритмы построения:
1) Ранжировки
2) Дерево доминирования
3) Зоны т.е. Циклы (на дереве доминирования). Цикл проходит через поддерево v и возвращается в v.



------------> LECTION-06 (10-10-06)

LCA = Наименьший общий предок.
M(v) - нумерация в порядке возрастания времени входа
N(v) - нумерация в порядке убывания времени выхода.

Любое ребро (v,u) : M(v) < M(u) прямое в дереве обхода.

Theorem: в произвольном графе, для произвольного дерева обхода в глубину M(v) < M(u) =>
  => любой (v,u) путь проходит через LCA(v,u) или еще более высокую вершину.

Ребра дерева доминирования по отношению к произвольному глубинному дереву:
Ребра или прямые, или древесные.

Полудоминирование: sdom(x) = {v : M(v) = min, exists path : {v = v0...vk = x } M(vi) >= M(x) for i >= 1 }

Доминант или сопадает с полудоминантом, или выше его по дереву обхода.

Любой путь из полудомината(x) в x проходит через общего предка (полудомината(x), x)
Т.к. M(sdom(x)) <= M(x)

Стягиванием можно получить из dfs-дерева ---> sdom-дерево ---> dom-дерево.


--------> Алгоритм поиска дерева доминирования:

За O(E)

1) Взяли произвольное дерево обхода в глубину
2) Неправильный способ:
     sdom[v] = LCA(v,in1[v],in2[v]...) где in[v] - входящие ребра 
   Правильный способ:
     sdom[v] = min sdom[x] по всем достижимым x по большим номерам + 1 ребро  
3) Если на отрезке (sdom[v]..v) есть ссылки sdom[x] наверх (за пределы отрезка), берем самую верхнюю ссылку (x).
   Тогда dom[v] = dom[x], иначе dom[v] = sdom[v]