\documentclass[12pt, a4paper] {ncc}
\usepackage[utf8] {inputenc}
\usepackage[T2A]{fontenc}
\usepackage[english, russian] {babel}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{listings,a4wide,longtable,amsmath,amsfonts,graphicx,tikz}
\usepackage{indentfirst,fancyvrb,pdfpages,tabularx}
\usepackage[rounded]{syntax}
\usepackage{calc}

\newcommand{\sel}[1]{$\fbox{#1}$}

\begin{document}
\setcounter{figure}{0}
\frenchspacing
\pagestyle{empty}
% ============================ ТИТУЛЬНЫЙ ЛИСТ ================================
\begin{center}
     Национальный исследовательский университет информационных технологий,
                              механики и оптики.\\
                       Кафедра вычислительной техники.\\
            Конструкторско-техническое обеспечение производства ЭВМ.
\end{center}
\vspace{\stretch{2}}
\begin{center}
                         {\bf Домашняя работа №3}\\
                Графо-теоретический подход к синтезу топологии\\
                              {\sl Вариант 31}
\end{center}
\vspace{\stretch{3}}
\begin{flushright}
                                          Работу выполнил студент группы P3415\\
                                                         {\it Халанский Дмитрий}
\end{flushright}
\vspace{\stretch{4}}
\begin{center}
                                      2017
\end{center}
% ======================== КОНЕЦ ТИТУЛЬНОГО ЛИСТА ============================
\newpage
\pagestyle{plain}
% ================================ ОТЧЁТ =====================================

\section{Исходные данные}

Имеем 32 цепи, связывающие 17 модулей таким образом:

\begin{tabular}{c|l l l}
Цепь & \multicolumn{3}{l}{Модуль/контакт} \\ \hline
1    & 13/5  & 7/2   & 8/2   \\
2    & 1/9   & 3/14  & 10/9  \\
3    & 12/12 & 13/10 & 11/9  \\
4    & 9/9   & 5/12  &       \\
5    & 12/5  & 8/5   &       \\
6    & 13/8  & 6/14  & 12/10 \\
7    & 5/10  & 13/6  & 12/7  \\
8    & 13/7  & 1/2   & 7/13  \\
9    & 12/1  & 9/2   & 4/8   \\
10   & 13/12 & 8/7   & 5/4   \\
11   & 7/5   & 4/3   &       \\
12   & 13/13 & 10/6  & 12/3  \\
13   & 13/11 & 11/12 & 8/3   \\
14   & 13/1  & 12/11 & 11/7  \\
15   & 12/6  & 6/5   &       \\
16   & 11/13 & 11/4  &       \\
17   & 8/8   & 7/8   & 11/8  \\
18   & 13/3  & 12/9  &       \\
19   & 11/5  & 9/3   & 4/11  \\
20   & 10/11 & 2/5   &       \\
21   & 13/4  & 5/2   & 2/12  \\
\end{tabular}

\section{Ход работы}

\subsection{Представление исходных данных}

\subsubsection{Матрица комплексов}

\begin{longtable}{c|c c c c c c c c c c c c c}
\hline
      & $e_{1}$ & $e_{2}$ & $e_{3}$ & $e_{4}$ & $e_{5}$ & $e_{6}$ & $e_{7}$ & $e_{8}$ & $e_{9}$ & $e_{10}$ & $e_{11}$ & $e_{12}$ & $e_{13}$\\
\hline
$u_{1} $ & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\
$u_{2} $ & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
$u_{3} $ & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\
$u_{4} $ & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\
$u_{5} $ & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\
$u_{6} $ & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\
$u_{7} $ & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\
$u_{8} $ & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\
$u_{9} $ & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\
$u_{10}$ & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\
$u_{11}$ & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
$u_{12}$ & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 \\
$u_{13}$ & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\
$u_{14}$ & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\
$u_{15}$ & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\
$u_{16}$ & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\
$u_{17}$ & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 \\
$u_{18}$ & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\
$u_{19}$ & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\
$u_{20}$ & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
$u_{21}$ & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
\end{longtable}

\subsubsection{Матрица соединений}

\begin{longtable}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
      & $e_{1}$ & $e_{2}$ & $e_{3}$ & $e_{4}$ & $e_{5}$ & $e_{6}$ & $e_{7}$ & $e_{8}$ & $e_{9}$ & $e_{10}$ & $e_{11}$ & $e_{12}$ & $e_{13}$\\
\hline
$e_{1}$  & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ \hline
$e_{2}$  & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ \hline
$e_{3}$  & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ \hline
$e_{4}$  & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 2 & 0 & 1 & 1 & 0 \\ \hline
$e_{5}$  & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 3 \\ \hline
$e_{6}$  & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 1 \\ \hline
$e_{7}$  & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 2 & 0 & 0 & 1 & 0 & 2 \\ \hline
$e_{8}$  & 0 & 0 & 0 & 0 & 1 & 0 & 2 & 0 & 0 & 0 & 2 & 1 & 3 \\ \hline
$e_{9}$  & 0 & 0 & 0 & 2 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ \hline
$e_{10}$ & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ \hline
$e_{11}$ & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 2 & 1 & 0 & 0 & 2 & 3 \\ \hline
$e_{12}$ & 0 & 0 & 0 & 1 & 1 & 2 & 0 & 1 & 1 & 1 & 2 & 0 & 6 \\ \hline
$e_{13}$ & 1 & 1 & 0 & 0 & 3 & 1 & 2 & 3 & 0 & 1 & 3 & 6 & 0 \\ \hline
\end{longtable}

\subsection{Нахождение гамильтонова цикла}

\subsubsection{Поиск цикла}

Для начала строим путь по матрице соединений таким образом:

\begin{enumerate}
\item Задаём $n = 1$;
\item Вычёркиваем из матрицы строку $e_n$;
\item Находим верхнюю ячейку в столбце $e_n$ из имеющих положительное
значение;
\item Если такой нет, выполнение завершается. Если такая есть, то определяем,
какой вершине $e_m$ соответствует эта ячейка; устанавливаем $n = m$; повторяем с
п. 2.
\end{enumerate} 

Пример начальных этапов выполнения:

\begin{itemize}
\item $n = 1$;
\item Вычёркиваем строку $e_1$;
\item Обнаруживаем, что есть вершина с $e_3$;
\item $n = 3$;
\item Вычёркиваем строку $e_3$;
\item Обнаруживаем, что есть вершина у $e_3$ и $e_{10}$;
\item $n = 10$...
\end{itemize}

В результате имеем путь $\{e_1, e_3, e_{10}, e_2, e_5, e_8, e_7,
e_4, e_9, e_{11}, e_{12}, e_6, e_{13}\}$. Обнаруживаем, что есть вершина между
$e_1$ и $e_{13}$~--- очень удачно вышло, что с первой попытки вышло обнаружить
гамильтонов цикл. Если бы это было не так, то мы бы пошли назад до первого
случая, когда в столбце есть более одного положительного числа, и выбрали не то,
которое взяли в первый раз. Мы бы повторяли перебор путей до тех пор, пока бы не
обнаружился гамильтонов цикл.

\subsubsection{Перенумерация вершин}

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

\begin{tabular}{c|c c c c c c c c c c c c c}
Новая  & $e_{1}$ & $e_{2}$ & $e_{3}$  & $e_{4}$ & $e_{5}$ & $e_{6}$ & $e_{7}$ & $e_{8}$ & $e_{9}$ & $e_{10}$ & $e_{11}$ & $e_{12}$ & $e_{13}$ \\
Старая & $e_{1}$ & $e_{3}$ & $e_{10}$ & $e_{2}$ & $e_{5}$ & $e_{8}$ & $e_{7}$ & $e_{4}$ & $e_{9}$ & $e_{11}$ & $e_{12}$ & $e_{6}$  & $e_{13}$ \\
\end{tabular}

Тогда входные данные становятся такими:

\begin{longtable}{c|l l l}
Цепь & \multicolumn{3}{l}{Модуль/контакт} \\ \hline
1    & 13/5  & 7/2   & 6/2   \\
2    & 1/9   & 2/14  & 3/9   \\
3    & 11/12 & 13/10 & 10/9  \\
4    & 9/9   & 5/12  &       \\
5    & 11/5  & 6/5   &       \\
6    & 13/8  & 12/14 & 11/10 \\
7    & 5/10  & 13/6  & 11/7  \\
8    & 13/7  & 1/2   & 7/13  \\
9    & 11/1  & 9/2   & 8/8   \\
10   & 13/12 & 6/7   & 5/4   \\
11   & 7/5   & 8/3   &       \\
12   & 13/13 & 3/6   & 11/3  \\
13   & 13/11 & 10/12 & 6/3   \\
14   & 13/1  & 11/11 & 10/7  \\
15   & 11/6  & 12/5  &       \\
16   & 10/13 & 10/4  &       \\
17   & 6/8   & 7/8   & 10/8  \\
18   & 13/3  & 11/9  &       \\
19   & 10/5  & 9/3   & 8/11  \\
20   & 3/11  & 4/5   &       \\
21   & 13/4  & 5/2   & 4/12  \\
\end{longtable}

Новая матрица комплексов:

\begin{longtable}{c|c c c c c c c c c c c c c}
\hline
 & $e_{1}$ & $e_{2}$ & $e_{3}$ & $e_{4}$ & $e_{5}$ & $e_{6}$ & $e_{7}$ & $e_{8}$ & $e_{9}$ & $e_{10}$ & $e_{11}$ & $e_{12}$ & $e_{13}$\\
\hline
$u_{1} $ & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\
$u_{2} $ & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
$u_{3} $ & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 \\
$u_{4} $ & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\
$u_{5} $ & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\
$u_{6} $ & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\
$u_{7} $ & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\
$u_{8} $ & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\
$u_{9} $ & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 \\
$u_{10}$ & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
$u_{11}$ & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\
$u_{12}$ & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\
$u_{13}$ & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\
$u_{14}$ & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 \\
$u_{15}$ & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\
$u_{16}$ & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
$u_{17}$ & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\
$u_{18}$ & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\
$u_{19}$ & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\
$u_{20}$ & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
$u_{21}$ & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
\end{longtable}

Новая матрица соединений:

\begin{longtable}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
      & $e_{1}$ & $e_{2}$ & $e_{3}$ & $e_{4}$ & $e_{5}$ & $e_{6}$ & $e_{7}$ & $e_{8}$ & $e_{9}$ & $e_{10}$ & $e_{11}$ & $e_{12}$ & $e_{13}$\\
\hline
$e_{1}$  & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ \hline
$e_{2}$  & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline
$e_{3}$  & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ \hline
$e_{4}$  & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \hline
$e_{5}$  & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 3 \\ \hline
$e_{6}$  & 0 & 0 & 0 & 0 & 1 & 0 & 2 & 0 & 0 & 2 & 1 & 0 & 3 \\ \hline
$e_{7}$  & 1 & 0 & 0 & 0 & 0 & 2 & 0 & 1 & 0 & 1 & 0 & 0 & 2 \\ \hline
$e_{8}$  & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 2 & 1 & 1 & 0 & 0 \\ \hline
$e_{9}$  & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 2 & 0 & 1 & 1 & 0 & 0 \\ \hline
$e_{10}$ & 0 & 0 & 0 & 0 & 0 & 2 & 1 & 1 & 1 & 0 & 2 & 0 & 3 \\ \hline
$e_{11}$ & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 2 & 0 & 2 & 6 \\ \hline
$e_{12}$ & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 0 & 1 \\ \hline
$e_{13}$ & 1 & 0 & 1 & 1 & 3 & 3 & 2 & 0 & 0 & 3 & 6 & 1 & 0 \\ \hline
\end{longtable}

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

\begin{tikzpicture}
\foreach \a in {1,2,...,13}{
\draw (\a*360/13: 4cm) node[circle,draw,minimum width=2em] (p\a) {p\a};
}
\draw(p1) -- (p2) -- (p3) -- (p4) -- (p5) -- (p6) -- (p7) -- (p8) -- (p9)
  -- (p10) -- (p11) -- (p12) -- (p13) -- (p1);
\draw(p1) -- (p3);
\draw(p1) -- (p7);
\draw(p3) -- (p11);
\draw(p3) -- (p13);
\draw(p4) -- (p13);
\draw(p5) -- (p9);
\draw(p5) -- (p11);
\draw(p5) -- (p13);
\draw(p6) -- (p10);
\draw(p6) -- (p11);
\draw(p6) -- (p13);
\draw(p7) -- (p10);
\draw(p7) -- (p13);
\draw(p8) -- (p10);
\draw(p8) -- (p11);
\draw(p9) -- (p11);
\draw(p10) -- (p13);
\draw(p11) -- (p13);
\end{tikzpicture}

\subsection{Построение графа пересечений}

Рассмотрим рёбро, которое связывает вершины $n$ и $m$; тогда оно пересекает все
рёбра, которые связывают вершину в промежутке $(n, m)$ и вершину за
промежутком $[n; m]$.

Очевидно, что ни одно из рёбер, входящих в гамильтонов цикл, не пересекает
никакое другое: промежуток $(n, n+1)$ пустой.

На основании этого строим граф смежности рёбер:

\begin{tikzpicture}
\draw (1*360/18: 6cm)  node[circle,draw,minimum width=3em] (1x3) {1,3};
\draw (2*360/18: 6cm)  node[circle,draw,minimum width=3em] (1x7) {1,7};
\draw (3*360/18: 6cm)  node[circle,draw,minimum width=3em] (3x11) {3,11};
\draw (4*360/18: 6cm)  node[circle,draw,minimum width=3em] (3x13) {3,13};
\draw (5*360/18: 6cm)  node[circle,draw,minimum width=3em] (4x13) {4,13};
\draw (6*360/18: 6cm)  node[circle,draw,minimum width=3em] (5x9) {5,9};
\draw (7*360/18: 6cm)  node[circle,draw,minimum width=3em] (5x11) {5,11};
\draw (8*360/18: 6cm)  node[circle,draw,minimum width=3em] (5x13) {5,13};
\draw (9*360/18: 6cm)  node[circle,draw,minimum width=3em] (6x10) {6,10};
\draw (10*360/18: 6cm) node[circle,draw,minimum width=3em] (6x11) {6,11};
\draw (11*360/18: 6cm) node[circle,draw,minimum width=3em] (6x13) {6,13};
\draw (12*360/18: 6cm) node[circle,draw,minimum width=3em] (7x10) {7,10};
\draw (13*360/18: 6cm) node[circle,draw,minimum width=3em] (7x13) {7,13};
\draw (14*360/18: 6cm) node[circle,draw,minimum width=3em] (8x10) {8,10};
\draw (15*360/18: 6cm) node[circle,draw,minimum width=3em] (8x11) {8,11};
\draw (16*360/18: 6cm) node[circle,draw,minimum width=3em] (9x11) {9,11};
\draw (17*360/18: 6cm) node[circle,draw,minimum width=3em] (10x13) {10,13};
\draw (18*360/18: 6cm) node[circle,draw,minimum width=3em] (11x13) {11,13};

\draw (3x11) -- (1x7);
\draw (3x13) -- (1x7);
\draw (4x13) -- (1x7);
\draw (4x13) -- (3x11);
\draw (5x9)  -- (1x7);
\draw (5x11) -- (1x7);
\draw (5x13) -- (1x7);
\draw (5x13) -- (3x11);
\draw (6x10) -- (1x7);
\draw (6x10) -- (5x9);
\draw (6x11) -- (1x7);
\draw (6x11) -- (5x9);
\draw (6x13) -- (1x7);
\draw (6x13) -- (3x11);
\draw (6x13) -- (5x9);
\draw (6x13) -- (5x11);
\draw (7x10) -- (5x9);
\draw (7x13) -- (3x11);
\draw (7x13) -- (5x9);
\draw (7x13) -- (5x11);
\draw (7x13) -- (6x10);
\draw (7x13) -- (6x11);
\draw (8x10) -- (5x9);
\draw (8x11) -- (5x9);
\draw (8x11) -- (6x10);
\draw (8x11) -- (7x10);
\draw (9x11) -- (6x10);
\draw (9x11) -- (7x10);
\draw (10x13) -- (3x11);
\draw (10x13) -- (5x11);
\draw (10x13) -- (6x11);
\draw (10x13) -- (8x11);
\draw (10x13) -- (9x11);
\end{tikzpicture}

Матрица соединений этого графа:

{\scriptsize\begin{tabularx}{\textwidth}{c c|X X X X X X X X X X X X X X X X X X}
& & $u_{1,7}$ & $u_{1,3}$ & $u_{3,11}$ & $u_{3,13}$ & $u_{4,13}$ & $u_{5,9}$ & $u_{5,11}$ & $u_{5,13}$ & $u_{6,10}$ & $u_{6,11}$ & $u_{6,13}$ & $u_{7,10}$ & $u_{7,13}$ & $u_{8,10}$ & $u_{8,11}$ & $u_{9,11}$ & $u_{10,13}$ & $u_{11,13}$ \\ \hline
$u_{1,7}$   & 1  & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline
$u_{1,3}$   & 2  & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline
$u_{3,11}$  & 3  & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ \hline
$u_{3,13}$  & 4  & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline
$u_{4,13}$  & 5  & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline
$u_{5,9}$   & 6  & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ \hline
$u_{5,11}$  & 7  & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ \hline
$u_{5,13}$  & 8  & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline
$u_{6,10}$  & 9  & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 \\ \hline
$u_{6,11}$  & 10 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ \hline
$u_{6,13}$  & 11 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline
$u_{7,10}$  & 12 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ \hline
$u_{7,13}$  & 13 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline
$u_{8,10}$  & 14 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ \hline
$u_{8,11}$  & 15 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ \hline
$u_{9,11}$  & 16 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ \hline
$u_{10,13}$ & 17 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ \hline
$u_{11,13}$ & 18 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline
\end{tabularx}}

\subsection{Нахождение максимальных внутренне устойчивых подмножеств}

Найдём семейство $\Psi$.

\begin{enumerate}
\item Нули в первой строке соответствуют элементам

$$\{2, 12, 13, 14, 15, 16, 17, 18\}$$

\item Выбираем первый элемент из них~--- $2$.
\item Строим дизъюнкцию из первой строки и текущего элемента. Далее, пока в ней
есть нули, добавляем в дизъюнкцию новые строки, соответствующие позициям с
нулями.

Пример:
\begin{enumerate}
\item $M_{1,2} = \{111111111110000000\}$
\item $M_{1,2,12} = \{111111111111001100\}$
\item $M_{1,2,12,13} = \{111111111111101100\}$
\item $M_{1,2,12,13,14} = \{111111111111111100\}$
\item $M_{1,2,12,13,14,17} = \{111111111111111110\}$
\item $M_{1,2,12,13,14,17,18} = \{111111111111111111\}$
\item Построено $\psi_1 = \{u_{1,7}, u_{1,3}, u_{7,13}, u_{8,10}, u_{8,11},
u_{10,13}, u_{11,13}\}$
\end{enumerate}

\item Повторяем прошлый пункт, но начинаем добавлять новые составляющие в
дизъюнкцию со второго нуля; находим множество $\psi_2$. Затем с третьего нуля, и
так далее.

\item Выбираем следующий элемент и повторяем для него последние два пункта.
\end{enumerate}

По такому принципу находим все семейства:

$$\begin{aligned}
\psi_1 &= \{9, 10, 11, 1, 4, 5, 8, 12, 14, 18\} \\
\psi_2 &= \{9, 10, 1, 3, 4, 7, 12, 14, 18\} \\
\psi_3 &= \{9, 10, 1, 4, 5, 8, 12, 14, 17, 18\} \\
\psi_4 &= \{11, 1, 4, 5, 8, 12, 13, 14, 17, 18\} \\
\psi_5 &= \{1, 2, 12, 13, 14, 17, 18\} \\
\psi_6 &= \{1, 2, 13, 14, 15, 18\} \\
\psi_7 &= \{1, 3, 4, 6, 7, 16, 18\} \\
\psi_8 &= \{1, 4, 5, 6, 7, 8, 16, 18\}
\end{aligned}$$

\subsection{Поиск максимального двудольного подграфа}

Высчитаем для каждой пары множеств из семейства $\Psi$ значение $|\psi_i| +
|\psi_j| - |\psi_i \cup \psi_j|$ и составим матрицу:

\begin{tabular}{|c|c c c c c c c c|}
\hline
& $\psi_1$ & $\psi_2$ & $\psi_3$ & $\psi_4$ & $\psi_5$ & $\psi_6$ & $\psi_7$ & $\psi_8$ \\
\hline
$\psi_1$ & 0  & 12 & 11 & 12 & 13 & 13 & 14 & 13 \\
$\psi_2$ & -1 & 0  & 13 & 14 & 12 & 12 & 11 & 13 \\
$\psi_3$ & -1 & -1 & 0  & 11 & 12 & 13 & 14 & 13 \\
$\psi_4$ & -1 & -1 & -1 & 0  & 11 & 12 & 14 & 13 \\
$\psi_5$ & -1 & -1 & -1 & -1 & 0  & 8  & 12 & 13 \\
$\psi_6$ & -1 & -1 & -1 & -1 & -1 & 0  & 11 & 12 \\
$\psi_7$ & -1 & -1 & -1 & -1 & -1 & -1 & 0  & 9  \\
$\psi_8$ & -1 & -1 & -1 & -1 & -1 & -1 & -1 & 0  \\ \hline
\end{tabular}

Наибольшее значение функция принимает на паре $\psi_1, \psi_7$.

Общие рёбра для них~--- $1, 4, 18$. Они не пересекаются ни с чем.

Убираем рёбра, содержащиеся в $\psi_1$ или $\psi_7$. Остаётся:

$$\begin{aligned}
\psi_5' &= \{2, 13, 17\} \\
\psi_6' &= \{2, 13, 15\}
\end{aligned}$$

Найдём новую матрицу $A$:

\begin{tabular}{|c|c c|}
\hline
& $\psi_5'$ & $\psi_6'$ \\ \hline
$\psi_5'$ & 0  & 4 \\
$\psi_6'$ & -1 & 0 \\ \hline
\end{tabular}

Возьмём пару из $\psi_5'$ и $\psi_6'$. Новое семество пустое. Все рёбра
задействованы.

\subsection{Проверка изоморфизма графов}

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

\begin{tabular}{|c|c c|}
\hline
\bf Значение & $G_1$ & $G_2$ \\
\hline
Число вершин $m$ & 13 & 13 \\
Число рёбер $k$  & 48 & 48 \\
Компоненты связности $p$ & 1 & 1 \\
\hline
\end{tabular}

По основным инвариантам графы совпадают.

Список вершин и соответствующих рангов:

\begin{tabular}{|c|c c|}
\hline
\bf Ранг & $G_1$ & $G_2$ \\
\hline
21 & $e_{13}$ & $e_{13}$ \\
15 & $e_{12}$ & $e_{11}$ \\
10 & $e_{11}$ & $e_{10}$ \\
9  & $e_{8}$ & $e_6$ \\
7  & $e_5, e_7$ & $e_5, e_7$ \\
5  & $e_4, e_9, e_{10}$ & $e_3, e_8, e_9$ \\
4  & $e_{1}$ & $e_1$ \\
3  & $e_{2}, e_6$ & $e_4, e_{12}$ \\
2  & $e_{3}$ & $e_2$ \\
\hline
\end{tabular}

Понятно, что вершины с одинаковым рангом изоморфны. Тогда имеем известное
соответствие для большей части вершин.

Возьмём матрицу смежности оригинального графа и запишем уже известные номера
вершин второго графа.

\begin{longtable}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
      & $e_{1}$ & ?3 & $e_{2}$ & ?5 & ?7 & ?3 & ?7 & $e_{6}$ & ?5 & ?5 & $e_{10}$ & $e_{11}$ & $e_{13}$\\
\hline
$e_{1}$  & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ \hline
?3       & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ \hline
$e_{2}$  & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ \hline
?5       & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 2 & 0 & 1 & 1 & 0 \\ \hline
?7       & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 3 \\ \hline
?3       & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 1 \\ \hline
?7       & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 2 & 0 & 0 & 1 & 0 & 2 \\ \hline
$e_{6}$  & 0 & 0 & 0 & 0 & 1 & 0 & 2 & 0 & 0 & 0 & 2 & 1 & 3 \\ \hline
?5       & 0 & 0 & 0 & 2 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ \hline
?5       & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ \hline
$e_{10}$ & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 2 & 1 & 0 & 0 & 2 & 3 \\ \hline
$e_{11}$ & 0 & 0 & 0 & 1 & 1 & 2 & 0 & 1 & 1 & 1 & 2 & 0 & 6 \\ \hline
$e_{13}$ & 1 & 1 & 0 & 0 & 3 & 1 & 2 & 3 & 0 & 1 & 3 & 6 & 0 \\ \hline
\end{longtable}

Проверка уже идентифицировааных рёбер позволяет восстановить нумерацию.
Следовательно, графы изоморфны.

\subsection{Поиск эйлерова цикла}

У графа есть вершины с нечётным количеством смежных рёбер. Дополним граф так,
чтобы их не было.

\begin{longtable}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
      & $e_{1}$ & $e_{2}$ & $e_{3}$ & $e_{4}$ & $e_{5}$ & $e_{6}$ & $e_{7}$ & $e_{8}$ & $e_{9}$ & $e_{10}$ & $e_{11}$ & $e_{12}$ & $e_{13}$\\
\hline
$e_{1}$  & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ \hline
$e_{2}$  & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 \\ \hline
$e_{3}$  & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ \hline
$e_{4}$  & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 \\ \hline
$e_{5}$  & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 1 \\ \hline
$e_{6}$  & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ \hline
$e_{7}$  & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ \hline
$e_{8}$  & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ \hline
$e_{9}$  & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ \hline
$e_{10}$ & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ \hline
$e_{11}$ & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 1 \\ \hline
$e_{12}$ & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 0 & 1 \\ \hline
$e_{13}$ & 1 & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 \\ \hline
\end{longtable}

Эйлеров цикл: 

$$\begin{aligned}
e_1, e_3, e_{10}, e_1, e_7, e_4, e_9, \\
e_5, e_2, e_8, e_5, e_7, e_8, e_{11}, e_4, e_{12}, \\
e_5, e_{13}, e_2, e_{10}, e_9, e_{11}, e_7, e_{13}, \\
e_6, e_{12}, e_8, e_{13}, e_9, e_{12}, e_{10}, e_{13}, \\
e_{11}, e_{12}, e_{13}, e_1
\end{aligned}$$

\end{document}

