GraphTheoryIntro.tex

\setchapterpreamble[u]{\margintoc}
\chapter{Некоторые сведения из теории графов}
\label{chpt:GraphTheoryIntro}
\tikzsetfigurename{GraphTheoryIntro_}

В данном разделе мы дадим определения базовым понятиям из теории графов, рассмотрим несколько классических задач из области анализа графов и алгоритмы их решения.
Кроме этого, поговорим о связи между линейной алгеброй и некоторыми задачами анализа графов.
Всё это понадобится нам при последующей работе.

\section{Основные определения}

\begin{definition}[Помеченный ориентированный граф]
    \emph{Помеченный ориентированный граф} $\mbfscrG = \langle V, E, L \rangle$, где $V$~--- конечное множество вершин, $E$~--- конечное множество рёбер, т.ч. $E \subseteq V \times L \times V$, $L$~--- конечное множество меток на рёбрах.
    В некоторых случаях метки называют \emph{весами}%
    \sidenote{Весами метки называют, как правило, тогда, когда они берутся из какого-либо числового множества, например $\BbbR$ или $\BbbN$.}
    и тогда говорят о \emph{взвешенном} графе.
\end{definition}

\begin{definition}[Помеченный неориентированный граф]
    В случае, если для любого ребра $(u, l, v)$ в графе также содержится ребро $(v, l, u)$, говорят, что граф \emph{неориентированный}.
\end{definition}

\begin{example}\label{exmpl:garph_visualization}
    Пусть дан граф
    \begin{align*}
        \mbfscrG_1 = \langle V & =\{0, 1, 2, 3\},                    \\
        E                      & =\{(0, a, 1), (1, a, 2), (2, a, 0), \\
                               & \ \ \ (2, b, 3), (3, b, 2)\},       \\
        L                      & =\{a, b\} \rangle.
    \end{align*}
    Графическое представление графа $\mbfscrG_1$ представлено на рисунке~\ref{gr:garph_visualization}.
    \begin{marginfigure}
        \begin{center}
            \resizebox{\marginparwidth}{!}{\input{figures/graph/graph0}}
        \end{center}
        \caption{Визуальное представление графа из примера~\ref{exmpl:garph_visualization}}
        \label{gr:garph_visualization}
    \end{marginfigure}

    Тогда $(0, a, 1)$ и $(3,b,2)$~--- это рёбра графа $\mbfscrG_1$.
    При этом $(3, b, 2)$ и $(2, b, 3)$~--- это разные рёбра.
\end{example}

В дальнейшем речь будет идти о конечных ориентированных помеченных графах.
Мы будем использовать термин \emph{граф} подразумевая именно конечный ориентированный помеченный граф, если только не оговорено противное.

Также мы будем считать, что все вершины занумерованы подряд с нуля.
То есть можно считать, что $V$~--- это отрезок $[0 \rng |V| - 1]$, где $|V|$~--- мощность множества $V$.

\begin{definition}[Путь]
    \label{def:path}
    \emph{Путём} $\pi$ в графе $\mbfscrG$ будем называть непустую последовательность рёбер такую, что для любых двух последовательных рёбер $e_1 = (u_1, l_1, v_1)$ и $e_2 = (u_2, l_2, v_2)$ в этой последовательности, конечная вершина первого ребра является начальной вершиной второго, то есть $v_1 = u_2$.
    Будем обозначать путь из вершины $v_0$ в вершину $v_n$ как $v_0 \pi v_n$.
    Иными совами,
    \[v_0 \pi v_n = e_0,e_1, \dots, e_{n-1} = (v_0, l_0, v_1),(v_1,l_1,v_2),\dots,(v_{n-1},l_{n-1},v_n).\]
\end{definition}
Часто для представления пути мы буем использовать следующие нотации:
\begin{center}
    \input{figures/graph/path0.tex}
\end{center}
или
\[
    v_0 \xrightarrow[]{l_0} v_1 \xrightarrow[]{l_1} v_2 \xrightarrow[]{l_2} \ldots \xrightarrow[]{l_{n-2}} v_{n-1} \xrightarrow[]{l_{n-1}} v_n.
\]

\begin{example}
    $(0,a,1), (1,a,2) = 0 \pi_1 2$~--- путь из вершины 0 в вершину 2 в графе $\mbfscrG_1$.
    При этом $(0, a, 1), (1, a, 2), (2, b, 3), (3, b, 2) = 0 \pi_2 2$~--- это тоже путь из вершины 0 в вершину 2 в графе $\mbfscrG_1$, но он не равен $0 \pi_1 2$.
\end{example}

Кроме того, нам потребуется отношение, отражающее факт существования пути между двумя вершинами.

\begin{definition}[Достижимость в графе]
    \label{def:reach}
    Пусть дан граф $\mbfscrG = \langle V, E, L \rangle$. \emph{Отношение достижимости} в графе $\mbfscrG$ --- это отношение $P \subseteq V \times V$, такое, что $(v_i,v_j) \in P \iff \exists v_i \pi v_j$.
\end{definition}

Отметим, что в некоторых задачах удобно считать по умолчанию, что $P$ является рефлексивным (то есть $(v_i,v_i) \in P$), однако наше определение такого не допускает\sidenote{Так как путь --- \emph{непустая} последовательность рёбер~(см. \ref{def:path}).}.
Исправить ситуацию можно явно добавив петли $(v_i,l,v_i)$ для всех вершин.

Один из способов задать граф~--- это задать его \emph{матрицу смежности}.
Неформально говоря, матрица смежности графа $\mbfscrG = \langle V, E, L \rangle$~--- это квадратная матрица $M$ размера $n \times n$, где $|V| = n$,
такая, что ячейка $M[i,j]$ хранит информацию о рёбрах из вершины $v_i$ в вершину $v_j$.
Далее мы приведём несколько классических примеров таких матриц, после чего обобщим понятие матрицы смежности удобным для дальнейшего изложения образом.

\begin{marginfigure}
    \begin{center}
        \resizebox{\marginparwidth}{!}{\input{figures/graph/graph1.tex}}
    \end{center}
    \caption{Неориентированный граф}
    \label{gr:graph1}
\end{marginfigure}
\begin{example}[Пример матрицы смежности неориентированного графа]
    \label{exmpl:undirectedGraphMatrix}
    Пусть дан неориентированный граф $\mbfscrG = \langle V, E\rangle$ без каких-либо меток на рёбрах (см. рисунок \ref{gr:graph1}).
    Его матрица смежности~--- булева матрица, в ячейке которой хранится $1$ только если соответствующие вершины соединены ребром:
    \[
        \begin{pmatrix}
            0 & 1 & 1 & 0 \\
            1 & 0 & 1 & 0 \\
            1 & 1 & 0 & 1 \\
            0 & 0 & 1 & 0
        \end{pmatrix}
    \]
    То есть $M[i,j] = 1 \iff (v_i,v_j) \in E$.
    Таким образом, единственная информация о ребрах~--- это факт их наличия, так как никакой дополнительной информации (меток) у рёбер нету.
    Заметим, что матрица смежности неориентированного графа всегда симметрична относительно главной диагонали.
\end{example}

\begin{marginfigure}
    \begin{center}
        \resizebox{\marginparwidth}{!}{\input{figures/graph/graph2.tex}}
    \end{center}
    \caption{Ориентированный граф}
    \label{gr:graph2}
\end{marginfigure}
\begin{example}[Пример матрицы смежности ориентированного графа]
    \label{example:diGraph}
    Дан ориентированный граф (см. рисунок \ref{gr:graph2}).
    Построить его булеву матрицу смежности можно применив рассуждения из предыдущего примера (\ref{exmpl:undirectedGraphMatrix}) и выглядеть она будет следующим образом:
    \[
        \begin{pmatrix}
            0 & 1 & 0 & 0 \\
            0 & 0 & 1 & 0 \\
            1 & 0 & 0 & 1 \\
            0 & 0 & 1 & 0
        \end{pmatrix}.
    \]
\end{example}

\begin{marginfigure}
    \begin{center}
        \resizebox{\marginparwidth}{!}{\input{figures/graph/graph3.tex}}
    \end{center}
    \caption{Помеченный граф}
    \label{gr:graph3}
\end{marginfigure}
\begin{example}[Пример матрицы смежности помеченного графа]
    Пусть дан помеченный граф (см. рисунок \ref{gr:graph3}).
    В данном случае $L = \{a,b\}$.
    Так как мы не будем в данном примере запрещать параллельные рёбра, то ячейки матрицы будут содержать множества меток: метки для всех параллельных рёбер между парой вершин.
    Соответственно,  $\varnothing$ означает, что рёбер между соответствующей парой вершин нету.

    В итоге матрица смежности исходного графа выглядит следующим образом:
    \[
        \begin{pmatrix}
            \varnothing & \{a\}       & \varnothing & \varnothing \\
            \varnothing & \varnothing & \{a\}       & \varnothing \\
            \{a\}       & \varnothing & \varnothing & \{a,b\}     \\
            \varnothing & \varnothing & \{b\}       & \varnothing
        \end{pmatrix}.
    \]
\end{example}

\begin{marginfigure}
    \begin{center}
        \resizebox{\marginparwidth}{!}{\input{figures/graph/graph4.tex}}
    \end{center}
    \caption{Взвешенный граф}
    \label{gr:graph4}
\end{marginfigure}
\begin{example}[Пример матрицы смежности взвешенного графа]
    \label{example:apspGraph}
    Пусть дан взвешенный граф (см. рисунок \ref{gr:graph4}).
    Будем считать, что веса берутся из $\BbbR \ (L \subseteq \BbbR$).
    Нужно придумать специальное значение, которое будет храниться в ячейках, соответствующих вершинам, между которыми нету рёбер\sidenote{
        Выбрать какое-то значение из $\BbbR$ не получится, так как в общем слуае любое такое значение может быть корректной меткой существующего ребра, так как у нас метки~--- это \emph{произвольные} значения из $\BbbR$.
        В частности, не сработает <<интуитивное>> желание сказать, что в ячейках для вершин, между которыми нет рёбер, хранится $0$.
    }.
    Часто матрица смежности взвешенного графа возникает в контексте задачи поиска кратчайших расстояний между вершинами.
    В таком случае естественно предположить, что для любой вершины $v_i$ существует петля $(v_i, 0, v_i)$, хоть она явно и не изображена.
    Далее, исходя из свойств решаемой задачи\sidenote{
        Здесь нужно обратить внимание на то, что мы конструируем матрицу опираясь на решаемую задачу.
        Для иной задачи мы часто должны будем выбрать другое специальное значение.
    }, в качестве специального значения, показывающего, что рёбер нет, возьмём $+\infty$: расстояние между несоединёнными вершинами равно бесконечности.

    В результате мы получим следующую матрицу смежности:
    \[
        \begin{pmatrix}
            0       & -1.4    & +\infty & +\infty \\
            +\infty & 0       & 2.2     & +\infty \\
            0.5     & +\infty & 0       & 1.85    \\
            +\infty & +\infty & -0.76   & 0
        \end{pmatrix}.
    \]
\end{example}

В нашем последнем примере (\ref{example:apspGraph}) мы обратили внимание на то, что детали построения матрицы смежности могут зависеть от того, для решения какой задачи её планируется использовать.
В действительности, именно так и происходит: матрица смежности --- удобный инструмент для описания некоторых свойств графа, важных при решении той или иной задачи.
Исходя из такого взгляда мы и попробуем построить обобщённое определение матрицы смежности.

Во-первых\sidenote{
    Ещё раз обратим внимание, что кроме ячеек, хранящих значения из множества меток, есть ячейки, нранящие некое <<ничего>>, когда ребро между соответствующими вершинами отсутсвует.
}, нам нужен унифицированный способ из множества меток рёбер строить множество, из элементов которого будут выбираться значения ячеек матрицы смежности.
Для этого введём множество $\Opt{L}$: для графа $\mbfscrG = \langle V, E, L \rangle$, $\Opt{L}=\{\Bbbzero\} \cup L$, где $\Bbbzero \notin L$ --- дополнительное значение, соответствующее отсутствию ребра\sidenote{
    Естественным способом реализовать такую конструкцию в языках с алгебраическими типами данных является использование типа Option (OCaml, F\#), или Maybe (Haskell), или аналогов.
    Данные типы как раз предназначены для выражения того, что что-то может присутствовать (есть ребро с меткой) либо отсутсвовать (нет ребра).
}: $M[i,j] = \Bbbzero \iff (v_i, _ ,v_j) \notin E$.

Во-вторых, матрица смежности редко нужна <<сама по себе>>.
Как правило, над ней необходимо выполнять какие-либо операции в рамках решения какой-то задачи.
Более того, часто операции над элементами матрицы нужны просто для того, чтобы аккуратно определить, как именно сохраняется информация о метках параллельных рёбер.
Дабы обеспечить эту возможность, мы будем либо сразу говорить, что матрица определена над какой-либо алгебраической структурой\sidenote{
    Конкретный тип структуры будет зависеть от решаемой задачи. Где-то хватит моноида, где-то потребуется полукольцо, а где-то ещё более сложная структура.
}, использующей в качестве носителя $\Opt{L}$, либо определять соответствующую структуру отдельно\sidenote{
    Такой подход может быть удобен с точки рения разделения данных и операций над ними.
    В частности, мы можем опеределить несколько структур с одинаковым носителем и разными операциями.
}.

Нам будет удобно пользоваться первым вариантом, так как он позволяет естественным образом получить представление для параллельных рёбер.
В итоге мы получим следующее определение.

\begin{definition}[Матрица смежности]
    \emph{Матрица смежности} графа $\mbfscrG = \langle V, E, L \rangle$~--- это квадратная матрица $M$ размера $n \times n$, где $|V| = n$, построенная над коммутативным моноидом $\BbbG = (\Opt{L}, \circ)$.
    При этом \[M[i,j] = \underset{{(i, l, j) \in E}}{\bigcirc} l\], где $\underset{\varnothing}{\bigcirc} = \Bbbzero$ и $\Bbbzero$ --- нейтральный элемент относительно $\circ$.
\end{definition}

Заметим, что наше определение матрицы смежности требует некоторой аккуратности при соотнесении с ним данных выше примеров.
Во-первых, в нашем определении присутствует моноид, который в примерах не фигурировал вовсе.
Во-вторых, выбор специального значения и способ представления информации о параллельных рёбрах в примерах выбирался исходя из некоторой интуитивной <<естественности>>, но в реальности нам необходимо аккуратно согласовывать даный выбор с решаемой задачей и соответствующими алгебраическими структурами.
Таким образом, свойства структуры $\BbbG$, а значит и детали её построения, зависят от задачи, в рамках которой рассматривается граф.
А значит, и матрица смежности конструируется исходя из задачи.

Как итог, уже можно заметить, что введение алгебраических структур как абстракции позволяет достаточно унифицированным образом смотреть на различные графы и их матрицы смежности.
Далее мы увидим, что данный путь позволит решать унифицированным образом достаточно широкий круг задач, связанных с анализом путей в графах.
Но сперва мы рассмотрим некоторые классические задачи анализа графов, которые понадобятся нам далее, и покажем их связь с линейной алгеброй.

\section{Обход графа в ширину}

Обход графа в ширину (Breadth-First Search, BFS)~--- это одна из фундаментальных задач анализа графов, для решения которой существуют хороши известные алгоритмы, изложенные в классической литературе\sidenote{
    Например, в книге <<Алгоритмы. Построение и анализ>>~\cite{кормен2009алгоритмы} Томаса Кормена и других.
}.
Более того, данный алгоритм является основой для многих алгоритмов поиска в графе.

В общих чертах, задача заключается в том, чтобы начиная с некоторой заданной вершины графа (источника) обойти все достижимые из неё вершины в некотором порядке.
Обход в ширину решает эту задачу и задаёт порядок посещения вершин с использованием \emph{фронта обхода} (или просто \emph{фронта}).
\begin{definition}[Фронт обхода]
    \emph{Фронт обхода} графа $\mbfscrG = \langle V, E, L \rangle$~--- это вектор размера $|V|$, содержащий информацию%
    \sidenote{В самом простом случае это будет булев вектор $F$ такой, что $F[i] = 1$ тогда и только тогда, когда \circled{$v_i$} достижима из стартовой вершины за заданное число шагов.}
    о вершинах графа, достижимых из стартовой ровно за $k$ шагов для заданного $k$.
    Иными словами, все вершины, информация о которых есть во фронте, достижимы из стартовой вершины за одинаковое число шагов.
\end{definition}

Один шаг алгоритма заключается в рассмотрении всех вершин, смежных со всеми вершинами текущего фронта и формировании из него нового фронта.
При формировании нового фронта необходимо учесть, что в процессе обхода не нужно посещать одну и ту же вершину несколько раз%
\sidenote{Как правило не нужно.
    Существуют алгоритмы, использующие аналогичную конструкцию с фронтом, но посещающие некоторые вершины несколько раз.
    Например, поиск кратчайших путей от заданной вершины.}.
Схематичное изображение такого шага приведено на рисунке~\ref{fig:bfs_schema}.
\begin{marginfigure}
    \begin{tikzpicture}
        \begin{scope}
            \node [circle, draw] (p1)                             {};
            \node [text width=0.1cm] (p2) [below = 0.3 of p1]     {$\vdots$};
            \node [circle, draw] (p3) [below = 0.3 of p2]         {};
            \node [text width=0.1cm] (p4) [below = 0.3 of p3]     {$\vdots$};
            \node [text width=0.1cm] (p5) [left = 0.8 of p2]     {$\vdots$};
            \begin{pgfonlayer}{background}
                \path[fill=green,rounded corners]
                ([yshift=5pt,xshift=-2pt] p1.north west) rectangle ([yshift=-5pt,xshift=2pt] p4.south east);
            \end{pgfonlayer}
        \end{scope}

        \begin{scope}
            \node [circle, draw] (q1) [right = of p1]                          {};
            \node [text width=0.1cm] (q2)     [below = 0.3 of q1]              {$\vdots$};
            \node [text width=0.1cm] (q4)     [right = 0.8 of q2]              {$\vdots$};
            \node [circle, draw] (q3) [below = 0.3 of q2]                      {};
            \begin{pgfonlayer}{background}
                \path[fill=yellow,rounded corners]
                ([yshift=5pt,xshift=-2pt] q1.north west) rectangle ([yshift=-5pt,xshift=2pt] q3.south east);
            \end{pgfonlayer}
        \end{scope}
        \node[text width=2.5cm] (new) [below right = 0.4 of q3] {\scriptsize{новый фронт}};
        \node[text width=2.5cm] (current) [below right = 0.1 of p4] {\scriptsize{текущий фронт}};

        \path[->]
        (p1) edge (q1)
        (p1) edge (q3)
        (p3) edge (q3)
        (p2) edge (q2)
        (p4) edge (q2)
        (p5) edge (p2)
        (p5) edge (p4)
        (q2) edge (q4)
        (new) edge [dashed] ([yshift=-5pt,xshift=-2.5pt] q3.south east)
        (current) edge [dashed] ([yshift=2.5pt, xshift=0.5pt] p4.south east)
        ;
    \end{tikzpicture}
    \caption{Схема одного шага обхода в ширину}
    \label{fig:bfs_schema}
\end{marginfigure}

Алгоритм обхода в ширину может быть переформулирован в терминах матрично-векторных операций следующим образом%
\sidenote{
    Стоит отметить, что ситуация с не менее известным обходом в глубину (Depth-First Search, DFS) более сложная: на момент написания текста не известно <<естественного>> выражения данного обхода в терминах линейной алгебры.
    Доказательство невозможности такого построения также не предъявлены.
    При этом, решения для частных случаев (деревья, ориентированные графы без циклов) предложены, например, в работе~\cite{10.1145/3315454.3329962}.}.
Пусть фронт~--- вектор размера $n$, а сам граф представлен матрицей смежности.
Тогда один шаг~--- просмотр всех смежных вершин для формирования нового нового фронта~--- это умножение текущего фронта на матрицу смежности.
Для того, чтобы отслеживать уже посещённые вершины, поддерживается булев вектор \emph{visited} размера $|V|$, такой, что $\emph{visited}[i] = 1$ тогда и только тогда, когда  \circled{$v_i$} уже посещалась в процессе обхода\sidenote{
    Делать вектор \emph{visited} булевым удобно только в самых простых случаях.
    В общем случае он будет хранить некоторую информацию о вершине.
    Например, номер шага, на котором её посетили, её предка, или даже расстояние до неё от стартовой вершины.
}.
Данный вектор используется как маска для фильтрации кандидатов в новый фронт.

Такие шаги повторяются до тех пор, пока фронт не окажется пустым ($\overline{0}$, нет новых вершин для посещения).
А результатом работы является информация, накопленная в \emph{visited}.

Псевдокод самой простой версии алгоритма\sidenote{
    Возможны вариации. Точно не самый оптимальный. Ссылка на AGraph и на статью какую-нибудь!!!!
} представлен на листинге~\ref{algo:BFS_linal}.
Нам понадобятся несколько алгебраических структур.
Во-первых, $\BbbB = \langle \{0,1\},\vee, \wedge \rangle$ --- стандартное булево полукольцо.
Во-вторых, $\BbbM = \langle \{0,1\},\oplus \rangle$, где $\oplus$ определена следующим образом\sidenote{
    Инвертированная маска: в результат попадают только те значения из первого вектора, которым соответствуют нулевые значения во втором.
}:
\begin{minipage}{0.25\textwidth}
    \begin{itemize}
        \item $0 \oplus 0 = 0$;
        \item $1 \oplus 1 = 0$;
    \end{itemize}
\end{minipage}
\begin{minipage}{0.25\textwidth}
    \begin{itemize}
        \item $0 \oplus 1 = 0$;
        \item $1 \oplus 0 = 1$.
    \end{itemize}
\end{minipage}


\begin{algorithm}
    %\SetAlgoLined
    \KwData{$M$ --- булева матрица смежности графа\;
        $k$ --- номер стартовой вершины}
    \KwResult{Вектор, указывающий, какие вершины достижимы из стартовой}
    $\emph{current\_front} \leftarrow \overline{0}$\;
    $\emph{visited} \leftarrow \overline{0}$\;
    $\emph{current\_front}[k] \leftarrow 1$\;
    \While{$\emph{current\_front} \neq \ \overline{0}$}{
        $\emph{visited} \leftarrow \emph{visited} \oplus^\BbbB \emph{current\_front}$ \tcp*{Записываем вершины из фронта в посещённые}
        $\emph{new\_front} \leftarrow \emph{current\_front} \mmult{\BbbB} M$ \tcp*{Вычисляем вершины, достижимые за один шаг из текущего фронта}
        $\emph{current\_front} \leftarrow \emph{new\_front} \oplus^\BbbM \emph{visited}$ \tcp*{Формируем новый фронт с учётом уже посещённых вершин}
    }
    \KwRet{\emph{visited}}\;
    \caption{Алгоритм обхода в ширину в терминах линейной алгебры}
    \label{algo:BFS_linal}
\end{algorithm}

Заметим, что данный алгоритм решает очень простую задачу: выясняет, какие вершины достижимы из стартовой.
Решение более содержательных задач потребует, прежде всего, создания более сложных алгебраических структур.
Однако, общий принцип, шаги алгоритма, останется неизменным.

%$$\boxed{\oplus}^{\BbbB}$$
%
%{
%        \setlength{\fboxsep}{0.5\fboxsep}
%        $$\boxed{\oplus}^{\BbbB}$$
%    }
%
%    {
%        \setlength{\fboxsep}{0.4\fboxsep}
%        $$\boxed{\oplus}^{\BbbB}$$
%    }
%
%    {
%        \setlength{\fboxsep}{0.3\fboxsep}
%        $$\boxed{\oplus}^{\BbbB}$$
%    }
%
%    {
%        $$ X \Krond Y $$
%    }
%
%    {
%        \setlength{\fboxsep}{0.2\fboxsep}
%        $$X \boxed{\oplus}^{\BbbB} Y$$
%    }
%
%    {
%
%        $$X \Kronf Y$$
%    }
%
%    {
%
%        $$X \Kronw Y$$
%    }
%    {
%
%        $$X \Kronq Y$$
%    }
%
%    {
%        \setlength{\fboxsep}{0.25\fboxsep}
%        $$X \boxed{\circ}^{\BbbB} Y$$
%    }
%
%    {
%        \setlength{\fboxsep}{0.2\fboxsep}
%        $$X \boxed{\circ}^{\BbbB} Y$$
%    }
%
%$$\boxplus^{\BbbB}$$
%$$\square \oplus {\BbbB}$$
%$$\box \oplus {\BbbB}$$

\begin{example}

    Рассмотрим обход в ширину графа из примера~\ref{example:diGraph} начиная с вершины \circled{2}.
    Для обозначения текущего фронта будем использовать зелёный цвет, а для достижимых из него за один шаг~--- жёлтый, обведём вершину красным, если она посещается повторно.

    В начальном состоянии посещённых вершин нет и во фронте отмечена только вторая вершина (так как она является стартовой):
    \begin{align*}
        \emph{current\_front} & =
        \begin{pmatrix}
            0 & 0 & 1 & 0
        \end{pmatrix}
        \\
        \emph{visited}        & =
        \begin{pmatrix}
            0 & 0 & 0 & 0
        \end{pmatrix}.
    \end{align*}

    \begin{marginfigure}
        \begin{center}
            \resizebox{\marginparwidth}{!}{\input{figures/graph/graph_BFS_1.tex}}
        \end{center}
        \caption{Обход в ширину, шаг первый}
        \label{fig:bfs_step_1}
    \end{marginfigure}

    В посещённые вершины добавим вершины текущего фронта.
    \begin{align*}
        \emph{visited} & = \emph{visited} \oplus^\BbbB \emph{current\_front} \\
                       & =
        \begin{pmatrix}
            0 & 0 & 0 & 0
        \end{pmatrix}\oplus^\BbbB
        \begin{pmatrix}
            0 & 0 & 1 & 0
        \end{pmatrix}
    \end{align*}

    Умножим фронт на матрицу смежности для того, чтобы выяснить, в какие вершины мы можем перейти из стартовой, и получить новый фронт:
    \begin{align*}
        \emph{new\_front} & = \emph{current\_front} \mmult{\BbbB} M \\
                          & =
        \begin{pmatrix}
            0 & 0 & 1 & 0
        \end{pmatrix} \mmult{\BbbB}
        \begin{pmatrix}
            0 & 1 & 0 & 0 \\
            0 & 0 & 1 & 0 \\
            1 & 0 & 0 & 1 \\
            0 & 0 & 1 & 0
        \end{pmatrix}                                              \\
                          & =
        \begin{pmatrix}
            1 & 0 & 0 & 1
        \end{pmatrix}.
    \end{align*}

    Теперь можно создать фронт для следующей итерации с учётом нового фронта и посещённых вершин:
    \begin{align*}
        \emph{current\_front} & = \emph{new\_front} \oplus^\BbbM \emph{visited}
        \\
                              & =
        \begin{pmatrix}
            1 & 0 & 0 & 1
        \end{pmatrix}\oplus^\BbbM
        \begin{pmatrix}
            0 & 0 & 1 & 0
        \end{pmatrix}                                                          \\
                              & =
        \begin{pmatrix}
            1 & 0 & 0 & 1
        \end{pmatrix}.
    \end{align*}

    Состояние графа после первой итерации показано на рисунке~\ref{fig:bfs_step_1}: вершина \circled{2} --- изначальное состояние фронта, а вершины \circled{1} и \circled{3} достижимы из него за один шаг.

    На втором шаге из текущего фронта мы можем попасть в вершины \circled{1} и \circled{2}.
    Сначала обновим информацию о посещённых вершинах:
    \begin{align*}
        \emph{visited} & =
        \begin{pmatrix}
            0 & 0 & 1 & 0
        \end{pmatrix}\oplus^\BbbB
        \begin{pmatrix}
            1 & 0 & 0 & 1
        \end{pmatrix} =
        \begin{pmatrix}
            1 & 0 & 1 & 1
        \end{pmatrix}.
    \end{align*}

    Затем вычислим новый фронт:
    \begin{align*}
        \emph{new\_front} & =
        \begin{pmatrix}
            1 & 0 & 0 & 1
        \end{pmatrix} \mmult{\BbbB}
        \begin{pmatrix}
            0 & 1 & 0 & 0 \\
            0 & 0 & 1 & 0 \\
            1 & 0 & 0 & 1 \\
            0 & 0 & 1 & 0
        \end{pmatrix}        \\ &=
        \begin{pmatrix}
            0 & 1 & 1 & 0
        \end{pmatrix}.
    \end{align*}

    При этом вершина \circled{2} есть в \emph{visited}, потому фронт для следующей итерации будет выглядеть следующим образом:
    \begin{align*}
        \emph{current\_front} & =
        \begin{pmatrix}
            0 & 1 & 1 & 0
        \end{pmatrix} \oplus^\BbbM
        \begin{pmatrix}
            1 & 0 & 1 & 1
        \end{pmatrix}            \\ &=
        \begin{pmatrix}
            0 & 1 & 0 & 0
        \end{pmatrix}
    \end{align*}

    \begin{marginfigure}
        \begin{center}
            \resizebox{\marginparwidth}{!}{\input{figures/graph/graph_BFS_2.tex}}
        \end{center}
        \caption{Обход в ширину, шаг второй}
        \label{fig:bfs_step_2}
    \end{marginfigure}

    Соответствующее состояние графа представлено на рисунке~\ref{fig:bfs_step_2}.

    Следующий, третий, шаг будет завершающим.

    \begin{align*}
        \emph{current\_front} & =
        \begin{pmatrix}
            0 & 1 & 0 & 0
        \end{pmatrix}\mmult{\BbbB}
        \begin{pmatrix}
            0 & 1 & 0 & 0 \\
            0 & 0 & 1 & 0 \\
            1 & 0 & 0 & 1 \\
            0 & 0 & 1 & 0
        \end{pmatrix}            \\ &=
        \begin{pmatrix}
            0 & 0 & 1 & 0
        \end{pmatrix}
    \end{align*}

    Из текущего фронта мы можем попасть лишь в вершину \circled{2}, а она уже была посещена.
    Соответственно, фронт для следующей итерации будет пустой и мы выйдем из цикла.

    \begin{marginfigure}
        \begin{center}
            \resizebox{\marginparwidth}{!}{\input{figures/graph/graph_BFS_3.tex}}
        \end{center}
        \caption{Обход в ширину, шаг третий}
        \label{fig:bfs_step_3}
    \end{marginfigure}

    Финальное состояние графа можно увидеть на рисунке~\ref{fig:bfs_step_3}.
    В итоге, результирующий вектор \emph{visited} содержит единицы на всех позициях, то есть все вершины графа достижимы из вершины \circled{2}.

\end{example}

Мы рассмотрели обход графа из одной фиксированной вершины.
Однако часто возникает необходимость совершить обход графа независимо из нескольких вершин.
При этом для каждой посещённой вершины необходимо знать, из какой именно стартовой вершины она достижима\sidenote{
    Именно поэтому мы не можем пойти наивным путём: сложить все стартовые вершины в один фронт.
}.
Данную вариацию обхода будем называть обходом в ширину с несколькими стартовыми вершинами (multiple-source BFS, MS-BFS).
Для такой постановки задачи также предложен алгоритм, основанный на линейной алгебре~\sidecite{9286186}.
Идея его такая же, как у рассмотренного выше, однако фронт~--- это уже не вектор, а матрица размера $k \times |V|$, где $k$~--- количество стартовых вершин, каждая строка которой является фронтом для одной из стартовых вершин\sidenote{
    Такакя конструкция действительно является лишь естественным для алгоритмов, выреженных в терминах операций линейной алгебры, способом запустить несколько независимых обходов параллельно.
}.
Псевдокод такой вариации представлен на листинге~\ref{algo:MS-BFS_linal}.
Можно заметить, что алгоритм отличается от обхода с одной стартовой вершиной только инициализацией данных.

\begin{algorithm}
    \SetAlgoLined
    \KwData{$M$ --- булева матрица смежности графа\;
        $K$ --- вектор номеров стартовой вершины}
    \KwResult{Матрица, $i$-я строка которой указывает, какие вершины достижимы из $K[i]$}
    $\emph{current\_front} \leftarrow \Bbbzero^{k \times n}$\;
    $\emph{visited} \leftarrow \Bbbzero^{k \times n}$\;
    \For{$i \in 0\ldots |K|-1$}{$\emph{current\_front}[i,K[i]] \leftarrow 1$\;}
    \While{\emph{current\_front} $\neq \ \overline{0}$}{
        $\emph{visited} \leftarrow \emph{visited} \oplus^\BbbB \emph{current\_front}$ \tcp*{Записываем вершины из фронта в посещённые}
        $\emph{new\_front} \leftarrow \emph{current\_front} \mmult{\BbbB} M$ \tcp*{Вычисляем вершины, достижимые за один шаг из текущего фронта}
        $\emph{current\_front} \leftarrow \emph{new\_front} \oplus^\BbbM \emph{visited}$ \tcp*{Формируем новый фронт с учётом уже посещённых вершин}
    }
    \KwRet{\emph{visited}}\;
    \caption{Алгоритм поиска в ширину от нескольких стартовых вершин в терминах линейной алгебры}
    \label{algo:MS-BFS_linal}
\end{algorithm}

\begin{example}
    Рассмотрим обход в ширину графа из примера~\ref{example:diGraph} начиная с вершин \circled{1} и \circled{3}.
    Будем использовать ту же цветовую схему, что и в предыдущем примере.

    В данном случае вспомогательные структуры инициализируются следующими матрицами.
    \begin{align*}
        \emph{current\_front} & =
        \begin{pmatrix}
            0 & 1 & 0 & 0 \\
            0 & 0 & 0 & 1
        \end{pmatrix}
        \\
        \emph{visited}        & =
        \begin{pmatrix}
            0 & 0 & 0 & 0 \\
            0 & 0 & 0 & 0
        \end{pmatrix}.
    \end{align*}

    Далее будут выполняться известные уже шаги.
    Проследим изменения фронта.

    \begin{align*}
        \emph{new\_front} & = \emph{current\_front} \mmult{\BbbB} M \\
                          &=
        \begin{pmatrix}
            0 & 1 & 0 & 0 \\
            0 & 0 & 0 & 1
        \end{pmatrix} \mmult{\BbbB}
        \begin{pmatrix}
            0 & 1 & 0 & 0 \\
            0 & 0 & 1 & 0 \\
            1 & 0 & 0 & 1 \\
            0 & 0 & 1 & 0
        \end{pmatrix}        \\ &=
        \begin{pmatrix}
            0 & 0 & 1 & 0 \\
            0 & 0 & 1 & 0
        \end{pmatrix}.
    \end{align*}

    \begin{marginfigure}
        \begin{center}
            \resizebox{\marginparwidth}{!}{\input{figures/graph/graph_MS-BFS_1.tex}}
        \end{center}
        \caption{Обход в ширину с несколькими стартовыми вершинами, шаг первый}
        \label{fig:ms_bfs_step_1}
    \end{marginfigure}

    Первый шаг представлен на изображении~\ref{fig:ms_bfs_step_1}: из двух стартовых вершин мы можем попасть в вершину \circled{2}.
    Можно заметить, что фронт хранит информацию о том, что \circled{2} достижима и из вершины \circled{1}, и из вершины \circled{1}.

    \begin{marginfigure}
        \begin{center}
            \resizebox{\marginparwidth}{!}{\input{figures/graph/graph_MS-BFS_2.tex}}
        \end{center}
        \caption{Обход в ширину с несколькими стартовыми вершинами, шаг второй}
        \label{fig:ms_bfs_step_2}
    \end{marginfigure}

    Проделаем ещё один шаг.
    Он будет последим содержательным шагом: на следующем шаге мы всего лишь узнаем, что все вершины посещены.
    \begin{align*}
        \emph{new\_front} & = \emph{current\_front} \mmult{\BbbB} M \\
                          & =
        \begin{pmatrix}
            0 & 0 & 1 & 0 \\
            0 & 0 & 1 & 0
        \end{pmatrix} \mmult{\BbbB}
        \begin{pmatrix}
            0 & 1 & 0 & 0 \\
            0 & 0 & 1 & 0 \\
            1 & 0 & 0 & 1 \\
            0 & 0 & 1 & 0
        \end{pmatrix}        \\ &=
        \begin{pmatrix}
            1 & 0 & 0 & 1 \\
            1 & 0 & 0 & 1
        \end{pmatrix}.
    \end{align*}



    Результат шага представлен на рисунке~\ref{fig:ms_bfs_step_2}.
    Здесь важно обратить внимание на вершину \circled{3}: она буде повторно посещённой для стартовой вершины \circled{3}, но для вершины \circled{1} мы пришли в неё впервые.
    Потому фронт для следующей итерации будет выглядеть следующим образом.

    \begin{align*}
        \emph{current\_front} & = \emph{new\_front} \oplus^\BbbM \emph{visited} \\
                              &=
        \begin{pmatrix}
            1 & 0 & 0 & 1 \\
            1 & 0 & 0 & 1
        \end{pmatrix} \oplus^\BbbM
        \begin{pmatrix}
            0 & 1 & 1 & 0 \\
            0 & 0 & 1 & 1
        \end{pmatrix}        \\ &=
        \begin{pmatrix}
            1 & 0 & 0 & 1 \\
            1 & 0 & 0 & 0
        \end{pmatrix}.
    \end{align*}

\end{example}

Идеи, заложенные в описанных выше алгоритмах, будут использоваться нами далее, при решении других задач.

\section{Задачи поиска путей}

Одна из классических задач анализа графов~--- это задача поиска путей между вершинами с различными ограничениями.

При этом возможны различные постановки задачи.
С одной стороны, постановки различаются тем, что именно мы хотим получить в качестве результата.
Здесь наиболее частыми являются следующие варианты.

\begin{itemize}
    \item Наличие хотя бы одного пути, удовлетворяющего ограничениям, в графе.
          В данном случае не важно, между какими вершинами существует путь, важно лишь наличие его в графе.
    \item Наличие пути, удовлетворяющего ограничениям, между некоторыми вершинами: задача достижимости.
          При данной постановке задачи, нас интересует ответ на вопрос о достижимости вершины \circled{$v_i$} из вершины \circled{$v_j$} по пути, удовлетворяющему ограничениям.
          Такая постановка требует лишь проверить существование пути, но не его предоставления в явном виде.
    \item Поиск одного пути, удовлетворяющего ограничениям: необходимо не только установить факт наличия пути, но и  предъявить его.
          При этом часто подразумевается, что возвращается любой путь, являющийся решением, без каких-либо дополнительных ограничений.
          Хотя, например, в некоторых задачах дополнительное требование простоты или наименьшей длины выглядит достаточно естественным.
    \item Поиск всех путей: необходимо предоставить все пути, удовлетворяющие заданным ограничениям.
\end{itemize}

С другой стороны, задачи могут различаться ещё и тем, как фиксируются множества стартовых и конечных вершин.
Здесь возможны следующие варианты:
\begin{itemize}
    \item от одной вершины до всех,
    \item между всеми парами вершин,
    \item между фиксированной парой вершин,
    \item между двумя множествами вершин $V_1$ и $V_2$, что подразумевает решение задачи для всех $(v_i,v_j) \in V_1 \times V_2$.
\end{itemize}

Стоит отметить, что последний вариант является самым общим и остальные~--- лишь его частные случаи.
Однако этот вариант часто выделяют отдельно, подразумевая, что остальные варианты в него не включаются\sidenote{
    Часто это связано с тем, что для некоторых частных случаев можно построить специализированный алгоритм, который будет по каким-то показателям лучше, чем алгоритм для задачи общего вида.
}.

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

Часто поиск путей сопровождается изучением их свойств, что далее приводит к формулированию дополнительных ограничений на пути в терминах этих свойств.
Например, можно потребовать, чтобы пути были простыми или не проходили через определённые вершины.
Один из естественных способов описывать свойства и, как следствие, задавать ограничения~--- это использовать ту алгебраическую структуру, из которой берутся веса рёбер графа%
\sidenote{На самом деле здесь наблюдается некоторая двойственность.
    С одной стороны, действительно, удобно считать, что свойства описываются в терминах некоторой заданной алгебраической структуры.
    Но, вместе с этим, структура подбирается исходя из решаемой задачи.}.

Предположим, что дан граф $\mbfscrG = \langle V, E, L\rangle $, где $L = (S, \oplus, \otimes)$~--- это полукольцо.
Тогда изучение свойств путей можно описать следующим образом:
\begin{equation}
    \label{eq:algPathProblem}
    \left\{\ (v_i, v_j, c) \mid c = \bigoplus_{v_i \pi_k v_j} \bigotimes_{(u, l, v) \in \pi } l \ \right\}.
\end{equation}

Иными словами, для каждой пары вершин, для которой существует хотя бы один путь, их соединяющий, мы агрегируем (с помощью операции $\oplus$ из полукольца) информацию обо всех путях между этими вершинами.
При этом информация о пути получается как свёртка меток рёбер пути с использованием операции $\otimes$\sidenote{Заметим, что детали свёртки вдоль пути зависят от свойств полукольца (и от решаемой задачи).
    Так, если полукольцо коммутативно, то нам не обязательно соблюдать порядок рёбер.
    В дальнейшем мы увидим, что данные особенности полукольца существенно влияют на особенности алгоритмов решения соответствующих задач.}.

Естественным требованием (хотя бы для прикладных задач, решаемых таким способом) является существование и конечность указанной суммы.
На данном этапе мы не будем касаться того, какие именно свойства полукольца могут нам обеспечить данное свойство, однако в дальнейшем будем считать, что оно выполняется.
Более того, будем стараться приводить частные для конкретной задачи рассуждения, показывающие, почему это свойство выполняется в рассматриваемых в задаче ограничениях.

Описанная выше задача общего вида называется анализом свойств путей алгебраическими методами (Algebraic Path Problem)~\sidecite{Baras2010PathPI} и предоставляет общий способ для решения широкого класса прикладных задач%
\sidenote{В работе \enquote{Path Problems in Networks}~\cite{Baras2010PathPI} собран действительно большой список прикладных задач с описанием соответствующих полуколец.
    Сводная таблица на страницах 58--59 содержит 29 различных прикладных задач и соответствующих полуколец.}.
Наиболее известными являются такие задачи, как построение транзитивного замыкания графа и поиск кратчайших путей (All Pairs Shortest Path или APSP).
Далее мы подробнее обсудим эти две задачи и предложим алгоритмы их решения.

\section{Алгоритм Флойда-Уоршелла}

Наиболее естественным образом решение обсуждаемых выражается в терминах операций над матрицей смежности исходного графа.
Поэтому предположим, что исходный граф задан матрицей над моноидом $\BbbG = (S,\oplus)$.

Как мы видели ранее, операция $\oplus$ позволяет нам агрегировать информацию по всем параллельным рёбрам.
Ровно она же и будет агрегировать информацию по всем путям между двумя вершинами%
\sidenote{Вообще говоря, работая с матрицей смежности мы не видим разницу между путём и ребром, так как любая запись в матрице смежности в ячейке $[i, j]$ говорит нам только о том, что вершины $i$ и $j$ связаны и эта связь обладает некоторым свойством (значение в ячейке), и ничего не говорит о том, как эта связь устроена.}.
Таким образом, осталось сконструировать операцию, отвечающую за агрегацию информации вдоль пути.
Здесь мы будем исходить из того, что новый путь может быть получен из двух подпутей, а свойство нового пути зависит только от свойств исходных подпутей.

Таким образом, дополнительная операция, обозначим её $\otimes: S \times S \to S$%
\sidenote{При первом рассмотрении такой выбор кажется контринтуитивным.
    Действительно, ведь при соединении путей мы как бы \enquote{складываем} их веса.
    Но при более детальном анализе поведения этой операции, в частности, относительно нейтрального элемента, становится понятно, что она ведёт себя очень похоже на умножение.
    Вероятно, стоит обратить внимание на операцию конкатенации, которая, с одной стороны, \enquote{делает то, что нам нужно}, а с другой, (и неспроста) часто обозначается $\cdot$.}%
, должна вести себя следующим образом. Пусть $S$~--- носитель моноида, $\Bbbzero \in S$~--- нейтральный элемент относительно $\oplus$.
\begin{itemize}
    \label{itm:otimesIntro}
    \item $s_1 \otimes s_2 = s_3$, $s_i \in S$, $s_i \neq \Bbbzero$: если существует путь $i \pi j$ со свойством $s_1$ и путь $j \pi k$ со свойством $s_2$, то существует путь $i \pi k$ со свойством $s_3$.
    \item $s \otimes \Bbbzero = \Bbbzero$: если существует путь $i \pi j$ со свойством $s$ и не существует пути $j \pi k$, то не существует и пути $i \pi k$.
    \item $\Bbbzero \otimes s = \Bbbzero$: если не существует пути $i \pi j$ и существует путь $j \pi k$ со свойством $s$, то не существует и пути $i \pi k$.
    \item $\Bbbzero \otimes \Bbbzero = \Bbbzero$: если не существует пути $i \pi j$ и не существует пути $j \pi k$, то не существует и пути $i \pi k$.
\end{itemize}

Новую операцию добавим к моноиду и получим новую алгебраическую структуру $\BbbG' = (S, \oplus,\otimes)$.
Данная структура является коммутативным моноидом по сложению (по построению) с нейтральным элементом $\Bbbzero$.
Из построения $\otimes$ видно, что $\Bbbzero$ является аннигилятором.
Ничего более про операцию $\otimes$, а значит и про $\BbbG'$ мы сказать, исходя из построения, не можем.
Классический фреймворк для решения algebraic path problem подразумевает, что $\BbbG'$ является полукольцом, однако далее мы увидим, что существуют задачи, в которых $\otimes$, например, не является ассоциативной%
\sidenote{Такой будет рассматриваемая в данной работе задача достижимости с ограничениями в терминах формальных языков.
    Другие примеры можно найти в уже упоминавшейся работе~\cite{Baras2010PathPI}.}.
А значит, согласно нашему определению, $\BbbG'$ полукольцом не является.

Теперь, когда построена алгебраическая структура, обеспечивающая вычисление формулы~
\ref{eq:algPathProblem}, мы можем предложить алгоритм вычисления этой формулы и данным алгоритмом в интересующих нас частных случаях будет являться алгоритм Флойда-Уоршелла~\sidecite{Floyd1962, Bernard1959, Warshall1962}.
Псевдокод алгоритма представлен на листинге~\ref{lst:algoFloydWarshall}, а его сложность $O(n^3)$.
Он практически дословно основан на описанной выше идее сборки путей из двух подпутей: тройной вложенный цикл перебирает все возможные разбиения пути на две части, а в строке 7 как раз и происходит вычисление формулы~\ref{eq:algPathProblem}.

Необходимо обратить внимание на несколько вещей.
Первая~--- порядок обхода.
Внешний цикл перебирает возможные точки разбиения (хотя мог бы, например, перебирать начальные вершины) для того, чтобы гарантировать правильный порядок вычисления подпутей (информация ни о каких подпутях не будет получена после того, как они поучаствовали в построении более длинного пути).
Вторая~--- количество итераций.
В данном случае мы ограничились тройным вложенным циклом от 0 до $n$ и для наших задач этого будет достаточно, однако, как доказательство этого факта, так и построение аналогичного алгоритма для других задач требует аккуратного анализа решаемой задачи и последующего доказательства корректности построенного алгоритма.

\begin{algorithm}
    \SetAlgoLined
    \KwData{$\mbfscrG$ --- граф, транзитивное замыканеи которого необходимо построить\;}
    \KwResult{Матрица, задающая транзитивное замыкание входного графа}
    %     \Comment{Матрица над $\BbbG=(S,\oplus,\otimes)$}
    $M \leftarrow$ матрица смежности $\mbfscrG$\;
    $n \leftarrow |V(\mbfscrG)|$\;
    \For{k = 0; k < n; k++}{
      \For{i = 0; i < n; i++}{
        \For{j = 0; j < n; j++}{
          $M[i,j] \leftarrow M[i,j] \oplus (M[i,k] \otimes M[k,j])$ \;
        }
      }
    }
    \KwRet{$M$}\;
    \caption{Алгоритм Флойда-Уоршелла}
    \label{lst:algoFloydWarshall}
\end{algorithm}

Хотя изначально данный алгоритм был предложен для решения задачи о кратчайших путях, при абстрагировании алгебраической структуры он превращается в алгоритм решения целого ряда задач.
В частности~--- нахождения транзитивного замыкания.
Так, если возьмём тропическое полукольцо $(\BbbR_{+\infty}, \min, +)$, то получим алгоритм для поиска кратчайших путей.
Если же возьмём булево полукольцо, то получим алгоритм для построения транзитивного замыкания графа.

\begin{marginfigure}
    \begin{center}
        \resizebox{\marginparwidth}{!}{\input{figures/graph/graph2.tex}}
    \end{center}
    \caption{Не полный граф}
    \label{gr:graph2nottc}
\end{marginfigure}
\begin{marginfigure}
    \begin{center}
        \resizebox{\marginparwidth}{!}{\input{figures/graph/graph5.tex}}
    \end{center}
    \caption{Полный граф}
    \label{gr:graph5}
\end{marginfigure}
\begin{example}[Транзитивное замыкание графа]
    \label{exmpl:transitiveClosure}
    Пусть дан граф (см. рисунок~\ref{gr:graph2nottc}).
    Его матрица смежности:
    \[
        M =
        \begin{pmatrix}
            0 & 1 & 0 & 0 \\
            0 & 0 & 1 & 0 \\
            1 & 0 & 0 & 1 \\
            0 & 0 & 1 & 0
        \end{pmatrix}.
    \]

    Здесь мы считаем, что отношение достижимости не рефлексивно: все диагональные элементы матрицы $M$ равны 0.

    Воспользовавшись алгоритмом из листинга~\ref{lst:algoFloydWarshall}, специализированного на случай булева полукольца, можно получить следующую матрицу смежности.
    \[
        M' =
        \begin{pmatrix}
            1 & 1 & 1 & 1 \\
            1 & 1 & 1 & 1 \\
            1 & 1 & 1 & 1 \\
            1 & 1 & 1 & 1
        \end{pmatrix}.
    \]

    А значит, транзитивным замыканием исходного графа является полный граф, изображенный на рисунке~\ref{gr:graph5}.
\end{example}

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

Аналогичным образом, используя данный алгоритм, но уже для тропического полукольца, можно решить задачу о поиске кратчайших путей для графа из примера~\ref{example:apspGraph}.

Идеи, заложенные в алгоритме Флойда-Уоршелла, а также возможность абстрагировать его, помогут нам в дальнейшем предложить алгоритм для задачи достижимости с ограничениями в терминах формальных языков.


\section{Анализ путей в графе и линейная алгебра}

 В данной главе мы рассмотрим некоторые связи%
 \sidenote{Связь между графами и линейной алгеброй~--- обширная область, в которой можно даже выделить отдельные направления, такие как спектральная теория графов.
     С точки зрения практики данная связь также подмечена давно и более полно с ней можно ознакомиться, например, в работах~\cite{doi:10.1137/1.9780898719918, Davis2018Algorithm9S}.
     Кроме этого, много полезной информации можно найти на сайте \url{https://graphblas.github.io/GraphBLAS-Pointers/}.}
 между графами и операциями над ними и матрицами и операциями над матрицами.

 Как мы видели, достаточно естественное представление графа~--- это его матрица смежности.
 Далее можно заметить некоторое сходство между определением матричного умножения~\ref{def:MxM} и мыслями, которыми мы руководствовались, вводя операцию $\otimes$ (\ref{itm:otimesIntro}).
 Действительно, пусть есть матрица $M$ размера $n \times n$ над $\BbbG = (S, \oplus, \otimes)$%
 \sidenote{Здесь мы уже сталкиваемся с тем, что могут иметь смысл относительно экзотические алгебраические структуры.
     Действительно, как мы выяснили, матрица смежности может быть определена на чем-то более бедным, чем полукольцо, а матричное умножение мы определяли над полукольцом.
     Но если задуматься, то и для определения произведения матриц полукольцо вовсе необязательно, достаточно более бедной структуры.}~--- матрица смежности графа.
 Умножим её саму на себя: вычислим $M'= M \cdot M$.
 Тогда, по~\ref{def:MxM}, $M'[i, j] = \bigoplus_{l \in [0 \rng n-1]} M[i, l] \otimes M[l, j]$.
 Размер $M'$ также $n \times n$.
 То есть $M'$ задаёт такой граф, что в нём будет путь со свойством, являющимся агрегацией свойств всех путей, составленных из двух подпутей в исходном графе.
 А именно, если в исходном графе есть путь из $i$ в $l$ с некоторым свойством (его значение хранится в $M[i, l]$), и был путь из $l$ в $j$ (его значение хранится в $M[l,j]$), то в новом графе свойство $M[i, l] \otimes M[l, j]$ аддитивно (используя $\oplus$) учтётся в свойстве пути из $i$ в $j$.

 Таким образом, произведение матриц смежности соответствует обработке информации о путях интересующим нас образом.
 Это наблюдение позволяет предложить решение задач анализа свойств путей, основанное на операциях над матрицами.
 Рассмотрим такое решение для задачи о кратчайших путях.

 Пусть $D_k$~--- матрица кратчайших путей, состоящих не более чем из $k$ рёбер.
 То есть $D_k[i, j]$~--- это длина кратчайшего пути из вершины $i$ в вершину $j$, такого, что он состоит не более чем из $k$ ребер.
 Если такого пути нет, то $D_k[i, j] = +\infty$.

 Таким образом, $D_1 = M$, где $M$~--- это матрица смежности исходного графа, а решением APSP является $D_{n-1}$, вычисляемая с помощью следующего рекуррентного соотношения:
 \begin{gather*}
     D(1) = M \\
     D(2) = D(1) \cdot M = M^2 \\
     D(3) = D(2) \cdot M = M^3 \\
     \vdots \\
     D(n - 1) = D(n - 2) \cdot M = M^{(n - 1)}
 \end{gather*}

 Здесь мы пользуемся той особенностью задачи, что кратчайший путь в ориентированном графе (без отрицательных циклов) не может быть длиннее $n$%
 \sidenote{Раз отрицательных циклов нету, то проходить через одну вершину, коих $n$, больше одного раза бессмысленно.}.
 Более того, мы пользуемся тем, что используемая структура именно полукольцо, а исходное отношение рефлексивно%
 \sidenote{
     Тот факт, что в любой вершине есть петля с весом 0, а 0~--- нейтральный для $\otimes$, позволяет не суммировать матрицы.
     Итоговая матрица содержит данные о путях длины \emph{не больше чем} вычисляемая степень, хотя должна бы содержать данные о путях ровно и только такой длины.
     Предлагается самостоятельно исследовать данный феномен.}.

 Таким образом, решение APSP сведено к произведению матриц над тропическим полукольцом, однако вычислительная сложность решения слишком большая: $O(n K(n))$, где $K(n)$~--- сложность алгоритма умножения матриц.

 Чтобы улучшить сложность, заметим, что, например, $D_3$ вычислять не обязательно, так как можно сразу вычислить $D_4$ как $D_2 \cdot D_2$.

 В итоге получим следующую последовательность вычислений:
 \begin{gather*}
     D_1 = M \\
     D_2 = M^2 = M \cdot M \\
     D_4 = M^4 = M^2 \cdot M^2 \\
     D_8 = M^8 = M^4 \cdot M^4 \\
     \vdots \\
     D_{2^{\log(n-1)}} = M^{2^{\log(n-1)}} = M^{2^{\log(n-1)} - 1} \cdot M^{2^{\log(n-1)} - 1} \\
     D_{n-1} = D_{2^{\log(n-1)}}
 \end{gather*}

 Теперь вместо $n$ итераций нам нужно $\log{n}$, а итоговая сложность решения~--- $O(\log{n} K(n))$%
 \sidenote{
     Заметим, что это оценка для худшего случая.
     На практике при использовании данного подхода можно прекращать вычисления как только при двух последовательных шагах получились одинаковые матрицы ($D_i = D_{i-1}$).
     Это приводит нас к понятию \emph{неподвижной точки}, обсуждение которого лежит за рамками повествования.}.
 Данный алгоритм называется \emph{repeated squaring}%
 \sidenote{Пример решения APSP с помощью repeated squaring: \url{http://users.cecs.anu.edu.au/~Alistair.Rendell/Teaching/apac_comp3600/module4/all_pairs_shortest_paths.xhtml}}.
 Здесь мы предполагаем, что $n-1 = 2^k$ для какого-то $k$.
 На практике такое верно далеко не всегда.
 Если это условие не выполняется, то необходимо взять ближайшую сверху степень двойки%
 \sidenote{
     Кажется, что это приведёт к избыточным вычислениям.
     Попробуйте оценить, на сколько много лишних вычислений будет сделано в худшем случае.}.

 Таким образом, APSP сводится к умножению матриц над полукольцом, что, к сожалению, не позволяет этим путём получить истинно субкубический алгоритм для задачи.
 Тем не менее, позволяет получить слегка субкубический.
 Приведем некоторые работы по APSP для ориентированных графов с вещественными весами (здесь $n$~--- количество вершин в графе), по которым можно более детально ознакомиться как с историей вопроса, так и с текущими результатами:
 \begin{itemize}
     \item M.L. Fredman (1976)~--- $O(n^3(\log \log n / \log n)^\frac{1}{3})$~--- использование дерева решений~\sidecite{FredmanAPSP1976}
     \item W. Dobosiewicz (1990)~--- $O(n^3 / \sqrt{\log n})$~--- использование операций на Word Random Access Machine~\sidecite{Dobosiewicz1990}
     \item T. Takaoka (1992)~--- $O(n^3 \sqrt{\log \log n / \log n})$~--- использование таблицы поиска~\sidecite{Takaoka1992}
     \item Y. Han (2004)~--- $O(n^3 (\log \log n / \log n)^\frac{5}{7})$~\sidecite{Han2004}
     \item T. Takoaka (2004)~--- $O(n^3 (\log \log n)^2 / \log n)$~\sidecite{Takaoka2004}
     \item T. Takoaka (2005)~--- $O(n^3 \log \log n / \log n)$~\sidecite{Takaoka2005}
     \item U. Zwick (2004)~--- $O(n^3 \sqrt{\log \log n} / \log n)$~\sidecite{Zwick2004}
     \item T.M. Chan (2006)~--- $O(n^3 / \log n)$~--- многомерный принцип \enquote{разделяй и властвуй}~\sidecite{Chan2008}
 \end{itemize}

 Вопрос же о истинно субкубических алгоритмах решения APSP всё ещё открыт~\sidecite{Chan2010} и активно обсуждается в научном сообществе.

 Аналогичным образом можно свести транзитивное замыкание к матричным операциям.
 Предлагаем проделать это самостоятельно, заодно обратив внимание на важность рефлексивности (в примере~\ref{exmpl:transitiveClosure} её нет).

 Заметим, что оптимизация, связанная с возведением в квадрат возможна только при ассоциативности произведения матриц, что зависит от свойств алгебраической структуры, над которой построены матрицы.
 Для полукольца такая оптимизация законна, однако в некоторых случаях её применить нельзя.
 Таким случаем как раз и будет рассматриваемая в нашей работе задача.
 Поэтому построение алгоритма её решения через операции над матрицами, хотя и будет основано на указанных выше соображениях, но будет сопряжено с некоторыми трудностями.

% %\section{Вопросы и задачи}
% %\begin{enumerate}
% %  \item Реализуйте абстракцию полукольца, позволяющую конструировать полукольца с произвольными операциями.
% %  \item Реализуйте алгоритм произведения матриц над произвольным полукольцом. Используйте результат решения предыдущей задачи.
% %  \item Используя результаты предыдущих задач, реализуйте алгоритм построения транзитивного замыкания через произведение матриц.
% %  \item Используя результаты предыдущих задач, реализуйте алгоритм решения задачи APSP для ориентированного через произведение матриц.
% %  \item Используя существующую библиотеку линейной алгебры для CPU, решите задачу построения транзитивного замыкания графа.
% %  \item Используя существующую библиотеку линейной алгебры для CPU, решите задачу APSP для ориентированного графа.
% %  \item Используя существующую библиотеку линейной алгебры для GPGPU, решите задачу построения транзитивного замыкания графа.
% %  \item Используя существующую библиотеку линейной алгебры для GPGPU, решите задачу APSP для ориентированного графа.
% %  \item Сравните произволительность решений предыдущих задач
% %\end{enumerate}