
\Section{Компоненты двусвязности}{13 ноября}{Андрей Тонких}

\Subsection{Поиск компонент реберной двусвязности.}

    \begin{Def}{Реберная двусвязность:} \\
        Две вершины называются \textbf{реберно двусвязными}, если между ними существуют два реберно непересекающихся пути 

        $\EQ$ они лежат на реберно простом цикле.

        $\EQ$ при удалении любого ребра они останутся в одной компоненте связности.
    \end{Def}

    \begin{Thm}{\emph{Реберная двусвязность - отношение эквивалентности.}}

        \THE{Доказательство:}

            Рефлексивность и симметричность очевидны. 

            \medskip
            Докажем транзитивность.

            $(u, v)$, $(v, w)$ - реберно двусвязны.
            
            \medskip
            Доказать: $(u, w)$ - реберно двусвязны.

            \medskip
            Из $w$ в $v$ есть два реберно непересекающихся пути, $P_1$ и $P_2$ соответственно.
            Обозначим за $C$ объединение двух реберно непересекающихся путей из $u$ в $v$. $C$ будет реберно-простым циклом. 
            Пусть вершины $a$ и $b$ - первые со стороны $w$ вершины на пересечении $P_1$ и $P_2$ с $C$ соответственно.
            Рассмотрим два пути $w - a - u$ и $w - b - u$, такие, что части $a - u$ и $b - u$ идут в разные стороны по циклу $C$. Наличие двух таких реберно непересекающихся путей очевидно, а значит $u$ и $w$ реберно двусвязны.

            \begin{tikzpicture}
                
                \draw [line width=2pt]
                    (0,3) node [above left] {$v$} -- 
                    (3,1) -- 
                    (6,3) node [above right] {$u$} -- 
                    (3,5) -- 
                    cycle;
                
                \draw
                    (1.5,0) node [below left]  {$w$} -- 
                    (4,0) -- 
                    (4,1.6666666) node [below right] {$b$} -- 
                    (3.5,1.333333) -- 
                    (2,5) -- 
                    (0,3);

                \draw
                    (1.5,0) -- 
                    (1.5,2) node [above right] {$a$} -- 
                    (1.5,3) -- 
                    (0, 3);
                

                \draw
                    (1.5,-0.1) -- 
                    (4.1,-0.1) -- 
                    (4.1,1.5666666) -- 
                    (6.1,2.9);
                
                \draw
                    (1.4,0) -- 
                    (1.4,1.9) -- 
                    (-0.2,3) --
                    (3,5.2) -- 
                    (6.1,3.1);

            \end{tikzpicture}

    \end{Thm}

    \bigskip
    $\forall e = (u, v):$ e - мост $\EQ$ $u$ и $v$ в разных компонентах реберной двусвязности.

    \medskip
    \THE{Алгоритм 1:}
    
    \medskip
    Нашли мосты, удалили мосты. Компоненты связности в итоговом графе - это компоненты реберной двусвязности в исходном.

    \medskip
    $\O(V + E)$

    \medskip
    \THE{Однопроходный алгоритм со стеком:}
    
    \medskip
    Алгоритм строится на базе алгоритма поиска мостов. Во-первых, создадим глобальный стек, и при спуске по дереву dfs добавляем в него вершины. Во-вторых, когда возвращаемся назад, проверяем не является ли ребро мостом. Если это так, то все вершины, находящиеся до текущего потомка в стеке, принадлежат одной компоненте. Заметим, что эта компонента будет висячей вершиной в дереве конденсации, так как обходили граф поиском в глубину. Значит, ее можно выкинуть и продолжить поиск в оставшемся графе. Действуя по аналогии в получившемся графе, найдем оставшиеся компоненты реберной двусвязности.

    \medskip
    Код:
    \begin{code}{c}
    void newComp(size_t size = 0) {
        comp.emplace_back(); // create new empty component
        while (st.size() > size) {
            comp.back().push_back(st.back());
            st.pop_back();
        }
    }

    void find_bridges(int v, int parentEdge = -1) {
        if (up[v] != 0) { // visited
            return;
        }

        up[v] = tin[v] = ++timer;
        st.push_back(v); // st - stack

        for (edge e : g[v]) {
            if (e.id == parentEdge) {
                continue;
            }

            int u = e.to;

            if (tin[u] == 0) {
                int size = st.size();
                find_bridges(u, e.id);
                if (up[u] > tin[v]) {
                    newComp(size);
                }
            }

            up[v] = min(up[v], up[u]);
        }
    }

    int main() {
        ...
        fori (n) {
            if (up[i] == 0) {
                find_bridges(i);
                newComp(); // dfs root component  
            }
        }
        ...
    }
    \end{code}    

    \medskip
    $\O(V + E)$

\Subsection{Поиск компонент вершинной двусвязности.}

    \begin{Def}{Вершинная двусвязность:} \\
        Два ребра графа называются \textbf{вершинно двусвязными}, если между ними существует два [вершинно] непересекающихся пути

        $\EQ$ они лежат в одном простом цикле.

        $\EQ$ при удалении любой вершины они останутся в одной компоненте связности.
    \end{Def}

    Пусть $e = (u, v),\ g = (v, w)$ // два смежных ребра

    $e$ и $g$ в разных компонентах вершинной двусвязности $\EQ$ нет пути ($u - w$) без $v$. 

    \medskip
    Доказательство:

    \medskip
    $\Leftarrow$ : 

    (очевидно)

    \medskip
    $\Rightarrow$ : 

    От противного: пусть они в одной компоненте $\SO \exists$ два вершинно-непересекающихся пути $\SO$ один не содержит $v$.

    \medskip
    Замечание:

    $e$ и $g$ в разных компонентах $\SO$ $v$ - точка сочленения.

    $v$ - точка сочленения $\not \SO$ $e$ и $g$ в разных компонентах.

    \bigskip
    \begin{Thm}{\emph{Вершинная двусвязность - отношение эквивалентности.}}
        
        \THE{Доказательство:}

            Рефлексивность и симметричность очевидны. 
            Доказательство транзитивности аналогично с отношением реберной двусвязности. 
            Идем до первого пересечения с циклом, после чего идем по циклу в разные стороны. 
    \end{Thm}

    \THE{Алгоритм поиска за $\O(V + E)$:}

    Алгоритм строится на базе алгоритма поиска точек сочленения. Во-первых, первый раз проходя по ребру, будем класть его на стек. Во-вторых, если видим, что спустившись по ребру нельзя подняться выше текущей вершины по дереву dfs(это говорит, что вершина - точка сочленения), то помечаем все, что лежит на стеке до этого ребра как новую компоненту. Отдельно, как и в алгоритме поиска точек сочленения, стоит рассмотреть случай корня dfs.  

    \medskip
    Код:

    \begin{code}{c}
    void newComp(size_t size = 0) {
        while (st.size() > size) {
            color[st.back()] = compCnt;
            st.pop_back();
        }
        ++compCnt;
    }

    void find_points(int v, bool root = true) {
        if (up[v] != 0) {
            return;
        }

        up[v] = tin[v] = ++timer;
        int cnt = 0;
        
        for (edge e : g[v]) {
            if (used[e.id]) {
                continue;
            }

            int u = e.to;
            st.push_back(e.id); // st - stack
            used[e.id] = true;

            if (tin[u] == 0) {
                ++cnt;
                size_t size = st.size() - 1; // minus this edge

                find_points(u, false);
                
                if (up[u] >= tin[v] && (!root || cnt >= 2)) {
                    newComp(size);
                }
                
                up[v] = min(up[v], up[u]);
            } else {
                up[v] = min(up[v], tin[u]);
            }
        }

        if (root && !g[v].empty()) {
            newComp();
        }
    }

    int main() {
        ...
        fori (n) {
            find_points(i);
        }
        ...
    }
    \end{code}

\Subsection{Про 2-sat:}

    Есть формула в 2-КНФ.

    Хотим найти выполняющий набор или сказать, что формула противоречива.

    \medskip
    Построим граф. Вершины графа - литералы ($x$ или $\neg x$, где $x$ - переменная).

    Для каждого дизъюнкта $(a \vee b)$ добавим в граф ребра:

    $\bar{a} \to b$

    $\bar{b} \to a$

    \medskip
    Формула противоречива $\EQ$ $\exists x$: $x$ и $\neg x$ лежат в одной компоненте сильной связности.

    \medskip
    \THE{Замечание 1:}

    В таком графе если есть путь из литерала $la$ в литерал $lb$, то есть и путь из $\neg lb$ в $\neg la$.

    \medskip
    \THE{Замечание 2:}

    По сути, мы заменили один дизъюнкт на две импликации. 
    Таким образом, набор значений переменных выполняющий $\EQ$ нет ребер из выполненных литералов в невыполненные.

    \bigskip
    \THE{Решение:}

    \medskip
    Сделаем конденсацию графа.

    Проверим формулу на выполнимость(что $\forall x$: $x$ и $\neg x$ в разных компонентах сильной связности).

    Оттопсортим.

    Пойдем по компонентам в обратном топсорту порядке.

    Берем любой литерал ($lx$). Хотим его выполнить(если $lx = x$, то установить $x = 1$, иначе ($lx = \neg x$), установить $x = 0$). Если нет противоречий, выполняем все литералы этой компоненты. Иначе - не трогаем эту компоненту и идем дальше.

    \bigskip
    \THE{Утверждение 1:}
    
    Или мы сможем выполнить все литералы одной компоненты, или ни одного(для всех переменных этой компоненты уже были установлены противоположные значения).

    \medskip
    Доказательство:

    $\forall x, y:$ $lx$ и $ly$ в одной компоненте $\SO$ $\neg ly$ и $\neg lx$ тоже лежат в одной компоненте.

    \bigskip
    \THE{Утверждение 2:}

    Если мы не смогли выполнить компоненту $A$, то мы не сможем выполнить и ни одну компоненту, из которой есть ребра в $A$.

    \medskip
    Доказательство:

    Предположим обратное. Рассмотрим первый случай, когда все плохо.

    $\forall lx \in A$ знаем, что $\neg lx$ встречался ранее. Значит, для любого ребра $ly \to lx:$ $\neg ly$ тоже встречался ранее. 
    Причем существует ребро $\neg lx \to \neg ly$ и $\neg lx$ был выполнен. Тогда и $\neg ly$ был выполнен, т.к. мы рассматриваем первый плохой момент. 
    $\SO$ $ly$ не будет выполнен.

    \bigskip
    Получили, что для любого ребра $lx \to ly$ если выполнен литерал $lx$, то выполнен и $ly$ $\SO$ полученный набор значений переменных выполняющий.

