\documentclass[12pt]{article}

\usepackage{cmap}
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}
%\usepackage[russian]{olymp}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{color} % for colored text
\usepackage{import} % for changing current dir
\usepackage{epigraph}
\usepackage{daytime} % for displaying version number and date
\usepackage{wrapfig} % for having text alongside pictures
\usepackage{verbatim}
\usepackage[russian]{hyperref}
\usepackage{epstopdf}
\usepackage{indentfirst}
\usepackage{ulem}

\usepackage{amsthm}
\usepackage[russian]{hyperref}
\usepackage{datetime}
\usepackage{cmap}
\usepackage{enumerate}
\usepackage{hologo}
\usepackage{minted}
%\usepackage{unicode-math}

\sloppy

\voffset=-20mm
\textheight=220mm
\hoffset=-25mm
\textwidth=180mm

\def\EPS{\varepsilon}
\def\SO{\Rightarrow}
\def\EQ{\Leftrightarrow}
\def\t{\texttt}
\def\O{\mathcal{O}}
\newcommand{\q}[1]{\langle #1 \rangle} % <x>
\newcommand\URL[1]{{\footnotesize{\url{#1}}}}
\def\myindent{\hspace*{\parindent}}
\def\up{\vspace*{-\baselineskip}}
\def\NO{\t{\#}}
\newcommand{\ITEM}[1]{{\bf \underline{#1}}\hspace{0.5em}}

\newcommand{\npar}{$ $\par}
\newcommand{\ol}{\overline}
\newcommand{\ds}{\displaystyle}
\newcommand{\ua}{\uparrow}
\newcommand{\da}{\downarrow}
\newcommand{\eq}{\Longleftrightarrow}
\newcommand{\then}{\Longrightarrow}
\newcommand{\rthen}{\Longleftarrow}
\newcommand{\g}[1]{\mathbb{#1}}
\newcommand{\ing}[1]{\in\mathbb{#1}}
\renewcommand{\le}{\leqslant}
\renewcommand{\ge}{\geqslant}
\renewcommand{\emptyset}{\varnothing}
\DeclareMathOperator{\const}{const}
\DeclareMathOperator{\mmod}{mod}
\DeclareMathOperator{\ord}{ord}

\newenvironment{itemize*}{\begin{itemize}\setlength{\itemsep}{0pt}}{\end{itemize}}
\newenvironment{enumerate*}{\begin{enumerate}\setlength{\itemsep}{0pt}}{\end{enumerate}}

\theoremstyle{plain}
\newtheorem*{theorem}{Теорема}
\newtheorem*{statement}{Утверждение}
\newtheorem*{consequence}{Следствие}
\newtheorem*{lemma}{Лемма}

\theoremstyle{definition}
\newtheorem*{definition}{Определение}
\newcommand{\defined}[1]{\textit{#1}}
\newtheorem*{sign}{Обозначение}

\theoremstyle{remark}
\newtheorem*{problem}{Задача}
\newtheorem*{remark}{Замечание}
\newtheorem{algorithm}{Алгоритм}

\begin{document}

\begin{center}
  {\Large \bf Лекция по алгоритмам \t{\#10}} \\ 
  \vspace{0.5em}
  {\Large \bf Тема: DFS} \\
  \vspace{0.5em}
  {\large 11 ноября} \\
  \vspace{0.5em}
  {Собрано {\today} в {\currenttime}}
\end{center}

\vspace{-1em}
\noindent \underline{\hbox to 1\textwidth{{ } \hfil{ } \hfil{ } }}

\section{Компоненты рёберной двусвязности и мосты}

\subsection{Основные понятия}

Рассматриваем связный неориентированный граф $G$.

\begin{definition}
Вершины $v$ и $u$ \defined{рёберно двусвязны} ($v\sim u$) "--- существуют два простых не
пересекающихся по рёбрам пути, соединяющих $v$ и $u$.
\end{definition}

\begin{remark}
Эквивалентное определение: вершины $v$ и $u$ \defined{рёберно двусвязны} ($v\sim u$), если лежат на одном рёберно-простом цикле.
\end{remark}

\begin{statement}
$\sim$ "--- отношение эквивалентности.
\end{statement}
\begin{proof}
Симметричность ($a\sim a$) и рефлексивность ($a\sim b \then b\sim a$) очевидны из определения.
Необходимо доказать транзитивность: $a\sim b$, $b\sim c \then a\sim c$.

\begin{tabular}[c]{p{4cm}p{12cm}}
  \vskip 0.1em \includegraphics[width=4cm]{img/2014-11-11-DFS_pic.png} \vskip 0.1em & 

Рассмотрим два пути из $c$ в $b$. Найдём их места первого пересечения с циклом $a\to b \to a$. Получили вершины $x$ и $y$.
Тогда есть рёберно не пересекающиеся пути $a\to x\to c$ и $a\to y\to c$.
\end{tabular}
\end{proof}

\begin{definition}
\defined{Компоненты рёберной двусвязности} "--- графы, индуцированные вершинами классов эквивалентности отношения $\sim$.
\end{definition}

\begin{definition}
Граф $G$ \defined{рёберно двусвязен} --- $G$ состоит из одной компоненты рёберной двусвязности.
\end{definition}

\begin{definition}
$e\in E$ называется \defined{мостом} --- $G\setminus e$ несвязен.
\end{definition}

\begin{statement}
$G$ рёберно двусвязен $\eq$ в $G$ нет мостов.
\end{statement}
\begin{proof}
Если в $G$ есть мост $(vu)$, то между вершинами $v$ и $u$ только один простой путь, и $G$ не рёберно двусвязен.

Если в $G$ мостов нет, покажем по индукции, что $G$ рёберно двусвязен. Покажем, что любые две
вершины $v$ и $u$ графа рёберно двусвязны, индукция будет проводиться по расстоянию $K$ между этими вершинами.

База. $K=1$ --- в $G$ нет мостов, поэтому есть не единственный путь между соединёнными ребром вершинами $v$ и $u$.

Переход. Рассмотрим вершины $v$, $u$ на расстоянии $K+1$. $K+1>1$, поэтому можно рассмотреть вершину $w$ на кратчайшем пути между $v$ и $u$.
Расстояния между вершинами $v$ и $w$ и между $w$ и $u$ меньше $K+1$, поэтому по предположению индукции $v\sim w$ и $w\sim u$.
Тогда по транзитивности $v\sim u$.
\end{proof}


\subsection{Алгоритм нахождения компонент рёберной двусвязности}

\begin{statement}
$G$ --- связный неориентированный граф, $B$ --- множество его мостов.
Компоненты связности $G'=G\setminus B$ суть компоненты рёберной двусвязности $G$.
\end{statement}
\begin{proof}
Каждая из компонент связности $G'$ не содержала мостов в $G$, следовательно, по доказанному выше утверждению, являлась двусвязным подграфом.
При этом никакие две компоненты связности не могли лежать в одной компоненте двусвязности $C$, иначе $C$ содержала бы мост,
что противоречит доказанному утверждению.
\end{proof}

Пусть найдено множество всех мостов графа $G$ за время $T$. Тогда построим граф $G'=G\setminus B$ и найдём его компоненты связности с помощью поиска в глубину.
Итого, мы найдём компоненты рёберной двусвязности $G$ за время $T+\O(V+E)$.

Если граф $G$ несвязен, решаем задачу независимо для каждой из компонент связности.

\subsection{Алгоритмы нахождения мостов}

Граф $G$ считаем связным.

\begin{algorithm}
Переберём рёбра графа. Ребро $e$ является мостом, если $G\setminus e$ несвязен "--- проверяем за $\O(V+E)$ с помощью поиска в глубину.
Итого $\O(E(V+E))$.
\end{algorithm}

\begin{algorithm}
Построим остовное дерево графа с помощью поиска в глубину.
Заметим, что любые рёбра, не лежащие в этом дереве, мостами не являются, так как при их удалении связность графа не теряется.
Значит, достаточно перебирать (аналогично предыдущему алгоритму) только рёбра этого остовного
дерева. Но их $V-1$, поэтому итоговая сложность "---  $\O(V(V+E))$.
\end{algorithm}

\begin{algorithm}

Поиск всех мостов связного графа с помощью одного обхода в глубину за $\O(E)$.

\t{g[V]} "--- граф, хранящийся как список рёбер

\t{time\_in[V]} "--- время входа в вершину (положительно, если вершина посещена)

\t{dfs(v)} возвращает минимальное достижимое время входа по путям, начинающимся в $v$, состоящим из прямых рёбер,
кроме, возможно, последнего ребра (оно может быть обратным)

\begin{minted}{c}
vector<int> g[V];
int time_in[V];
int timer = 0;
int dfs(int v, int parent=-1){ 
    time_in[v] = ++timer;
    int min_time = time_in[v];
    for (auto u : g[v])
        if (u != parent) {
            int t;
            if (time_in[u] == 0) { // not visited yet
                t = dfs(u, v);
                if (t > time_in[v])
                    is_bridge(v, u); // edge (v, u) is a bridge
            } else
                t = time_in[u];
            min_time = min(min_time, t);
        }
    return min_time;
}
...
dfs(0);
\end{minted}

Если в графе могут быть кратные рёбра, необходимо запоминать не родителя вершины, а идентификатор ребра,
по которому мы пришли в вершину, и пропускать в цикле только это ребро.

\end{algorithm}

\begin{algorithm}

Разбиение связного графа на компноненты рёберной двусвязности с помощью одного обхода в глубину за $\O(E)$.

\begin{minted}{c}
vector<int> g[V];
vector<int> st; // stack
int time_in[V];
int timer = 0;
int dfs(int v, int parent=-1){ 
    time_in[v] = ++timer;
    int min_time = time_in[v];
    st.push_back(v);
    for (auto u : g[v])
        if (u != parent) {
            int t;
            if (time_in[u] == 0) { // not visited yet
                int cur_size = s.size();
                t = dfs(u, v);
                if (t > time_in[v]){
                	new_component(); // start new component
                    while (s.size() != cur_size){
                        add_to_component(s.back());
                        s.pop_back();
                    }
                    is_bridge(v, u); // edge (v, u) is a bridge
                }
            } else
                t = time_in[u];
            min_time = min(min_time, t);
        }
    return min_time;
}
...
dfs(0);
new_component(); // last component, includes vertex #0
while (!s.empty()){
    add_to_component(s.back());
    s.pop_back();
}
\end{minted}
\end{algorithm}


\section{Компоненты вершинной двусвязности и точки сочленения}

\subsection{Основные понятия}

Рассматриваем связный неориентированный граф $G$.

\begin{definition}
Рёбра $e$ и $f$ \defined{вершинно двусвязны} ($e\sim f$) "--- $e$ и $f$ лежат на одном вершинно-простом цикле либо совпадают.
\end{definition}

\begin{statement}
$\sim$ "--- отношение эквивалентности.
\end{statement}
\begin{proof}
Симметричность ($e\sim e$) и рефлексивность ($e\sim f \then f\sim e$) очевидны из определения.
Необходимо доказать транзитивность: $e\sim f$, $f\sim g \then e\sim g$.

Найдём места первого пересечения цикла $efe$ с циклом $fgf$. Получили вершины $x$ и $y$.
Тогда есть вершинно-простой цикл $exfye$.
\end{proof}

\begin{definition}
\defined{Компоненты вершинной двусвязности (блоки)} --- графы, индуцированные рёбрами классов эквивалентности отношения $\sim$.
\end{definition}

\begin{definition}
$G$ \defined{вершинно двусвязен}, если состоит из одного блока.
\end{definition}

\begin{definition}[1]
$v\in V$ --- \defined{точка сочленения}, если $G\setminus v$ несвязен.
\end{definition}

\begin{definition}[2]
$v\in V$ --- \defined{точка сочленения}, если принадлежит не менее чем двум блокам.
\end{definition}

\begin{statement}
Определения 1 и 2 эквивалентны.
\end{statement}
\begin{proof}
Пусть $v$ инцидентна каким-то двум рёбрам $e$ и $f$, которые не лежат на одном цикле. Тогда при удалении $v$ связность теряется.

Иначе $v$ инцидентна только рёбрам одного блока, и тогда любые два ребра, инцидентные $v$, лежат на одном цикле.
Тогда для каждой пары между их не-$v$ концами есть простой путь. Значит, при удалении $v$ связность не теряется.
\end{proof}

\begin{theorem}
$G$ вершинно двусвязен $\eq$ в $G$ нет точек сочленения.
\end{theorem}
\begin{proof}
Если есть точка сочленения --- она лежит на двух блоках.

Иначе любые два ребра с общим концом лежат в одном блоке.
Если рёбра $e$ и $f$ не имеют общего конца, то рассмотрим путь между этими рёбрами.
В таком пути каждая пара соседних рёбер лежит в одном блоке, значит, по транзитивности отношения $\sim$, рёбра $e$ и $f$ лежат в одном блоке.
\end{proof}

\subsection{Алгоритмы нахождения точек сочленения}

\setcounter{algorithm}{0}
\begin{algorithm}
Проверим для каждой вершины $v$, является ли она точкой сочленения.
Для этого запустим \texttt{DFS(v)}; если в дереве обхода у $v$ есть $\ge2$ сына --- $v$ является точкой сочленения, иначе нет.
Итоговое время работы --- $\O(VE)$.
\end{algorithm}

\begin{remark}
Этот алгоритм не получается модифицировать так, чтобы найти разбиение графа на блоки: удаление точек сочленения из графа не приводит к успеху.
\end{remark}

\begin{algorithm}
Запустим один обход в глубину, который для каждой вершины $v$ посчитает $x(v)$ --- количество детей в дереве обхода в глубину,
из поддеревьев которых нет обратных рёбер выше $v$, и $y(v)$ --- количество предков $v$ ($0$ для корня и $1$ для остальных вершин).
Тогда $v$ --- точка сочленения $\eq$ $x+y\ge 2$. (Это следует из того, что $x+y$ --- количество компонент связности в графе $G\setminus v$.)

Получаем алгоритм поиск всех точек сочленения связного графа с помощью одного обхода в глубину за $\O(E)$.

\t{g[V]} "--- граф, хранящийся как список рёбер

\t{time\_in[V]} "--- время входа в вершину (положительно, если вершина посещена)

\t{dfs(v)} возвращает минимальное достижимое время входа по путям, начинающимся в $v$, состоящим из прямых рёбер,
кроме, возможно, последнего ребра (оно может быть обратным)

\begin{minted}{c}
vector<int> g[V];
int time_in[V];
int timer = 0;
int dfs(int v, int parent=-1){ 
    time_in[v] = ++timer;
    int min_time = time_in[v], x = 0, y = (parent != -1);
    for (auto u : g[v])
        if (u != parent) {
            int t;
            if (time_in[u] == 0) { // not visited yet
                t = dfs(u, v);
                if (t >= time_in[v])
                    ++x;
            } else
                t = time_in[u];
            min_time = min(min_time, t);
        }
    if(x + y >= 2)
        is_cut(v); // v is cut vertex
    return min_time;
}
...
dfs(0);
\end{minted}
\end{algorithm}


\begin{algorithm}

Разбиение связного графа на компноненты вершинной двусвязности с помощью одного обхода в глубину за $\O(E)$.

\begin{minted}{c}
vector< pair<int, int> > g[V]; // pair = (to, edge's index)
vector<int> st; // stack
bool used[E];
int time_in[V];
int timer = 0;
int dfs(int v, int parent=-1){ 
    time_in[v] = ++timer;
    int min_time = time_in[v], x = 0, y = (parent != -1);
    for (auto p : g[v]){
        int u = p.first, id = p.second;
        if (u != parent) {
            int t, cur_size = st.size();
            if (!used[id]){
            	st.push_back(id);
                used[id] = 1;
            }
            if (time_in[u] == 0) { // not visited yet
                t = dfs(u, v);
                if (t >= time_in[v]){
                    ++x;
                    new_component();
                    while(st.size() != cur_size){
                        add_to_component(st.back());
                        st.pop_back();
                    }
                }
            } else
                t = time_in[u];
            min_time = min(min_time, t);
        }
    }
    if(x + y >= 2)
        is_cut(v); // v is cut vertex
    return min_time;
}
...
dfs(0);
\end{minted}
\end{algorithm}





\section{Эйлеровы графы}

\subsection{Основные понятия}

Рассматриваем связный неориентированный граф $G$.

\begin{definition}
\defined{Эйлеров путь} --- рёберно-простой путь, проходящий по всем рёбрам графа.
\end{definition}
\begin{definition}
\defined{Эйлеров цикл} --- рёберно-простой цикл, проходящий по всем рёбрам графа.
\end{definition}

\begin{theorem}
Эйлеров цикл существует $\eq$ степени всех вершин чётны.
\end{theorem}
\begin{proof}
$\then$. Если в графе есть эйлеров цикл, то проходя по нему, мы в каждую вершину входим и выходим, используя чётное количество инцидентных ей рёбер.
Все рёбра были использованы, значит, у каждой вершины степень четна.

$\rthen$. Рассмотрим самый длинный цикл $C$. Пусть он проходит не по всем рёбрам. Так как граф связен, то существует ребро, ведущее из вершины цикла $v\in C$.
Пойдём по этому ребру, будем идти, пока можем идти по неиспользованным рёбрам. Заметим, что в графе $G\setminus C$ все вершины также имеют чётную степень,
поэтому остановиться мы можем только в вершине $v$ --- назовём новый цикл $D$.
Построим более длинный цикл: сначала обойдём цикл $C$, начиная из вершины $v$, затем обойдём цикл $D$. Получили цикл $C+D$, более длинный, чем $C$.
Противоречие. Значит, цикл $C$ был эйлеровым.
\end{proof}

\begin{theorem}
Эйлеров путь существует $\eq$ степени не более чем двух вершин нечётны.
\end{theorem}
\begin{proof}
$\then$. Если путь --- не цикл, замкнём его дополнительным ребром. Тогда это --- эйлеров цикл в новом графе, в нём степени всех вершин четны, значит, в исходном
степени не более чем двух были нечетны.

$\rthen$. Если степени всех вершин четны, то эйлеровым путём будет эйлеров цикл.

Иначе есть ровно две вершины нечётной степени (т. к. их чётное количество в графе). Соединим их ребром $e$.
Теперь в графе степени всех вершин четны, найдём эйлеров цикл. Удалим из него ребро $e$, получился эйлеров путь в исходном графе.
\end{proof}

\begin{remark}
Аналогичные понятия и критерии существования верны для ориентированного графа.
Введём $\deg(v)=\deg_{out}(v)-\deg_{in}(v)$.

Эйлеров цикл в орграфе существует $\eq$ все вершины имеют $\deg(v)=0$.

Эйлеров путь в орграфе существует $\eq$ все вершины имеют $\deg(v)=0$, кроме, возможно, двух, которые имеют степени $1$ и $-1$.
\end{remark}

\section{Алгоритмы поиска эйлеровых циклов и путей}

\setcounter{algorithm}{0}
\begin{algorithm}
Поиск Эйлерова цикла в \textit{ориентированном} графе за $\O(E)$.

\begin{minted}{c}
vector< pair<int, int> > g[V]; // pair = (to, edge's index)
vector<int> answer; // indices of edges
void dfs(int v) { 
    while (!g[v].empty()) {
        int x = g[v].back().first, i = g[v].back().second;
        g[v].pop_back();
        dfs(x);
        answer.push_back(i);
    }
}
...
dfs(0);
\end{minted}

\end{algorithm}


\begin{algorithm}
Поиск Эйлерова цикла в \textit{неориентированном} графе за $\O(E)$.

Необходимо удалять парное ребро: граф хранится как ориентированный, для каждого неориентированного ребра хранятся две ориентированные копии.

Будем гарантировать, что ребро $k$ в неориентированном графе представляется в виде двух рёбер, имеющих индексы $2k$ и $2k+1$.

\begin{minted}{c}
bool deleted[E]; // NB: E is twice number of edges in undirected graph
vector< pair<int, int> > g[V]; // pair = (to, edge's index)
vector<int> answer; // indices of edges
void dfs(int v) { 
    while (!g[v].empty()) {
        int x = g[v].back().first, i = g[v].back().second;
        g[v].pop_back();
        if (deleted[i])
        	continue;

        deleted[i ^ 1] = 1; // 2k <-> 2k+1
        dfs(x);
        answer.push_back(i / 2); // 2k, 2k+1 -> k
    }
}
...
dfs(0);
\end{minted}
\end{algorithm}

\begin{remark}
Для поиска эйлерова пути необходимо запускаться от вершины с <<необычной>> степенью: от вершины с нечётной степенью в неориентированном графе и
от вершины со степенью $\deg(v)=\deg_{out}(v)-\deg_{in}(v)=1$ в ориентированном случае.
\end{remark}

\end{document}
