diff options
| author | Andrew Guschin <guschin@altlinux.org> | 2024-10-29 18:51:55 +0400 |
|---|---|---|
| committer | Andrew Guschin <guschin@altlinux.org> | 2024-10-29 18:51:55 +0400 |
| commit | dcfac8227b2628c7e2c1e06a551300a6403f2b79 (patch) | |
| tree | 859312ba2a3d093fabad1acda54975145ed0e425 /nir/nir.tex | |
| parent | 2ca7b9c081da1d0aac4d6b777d226255941c503e (diff) | |
wip(nir): report
Diffstat (limited to 'nir/nir.tex')
| -rw-r--r-- | nir/nir.tex | 1431 |
1 files changed, 1431 insertions, 0 deletions
diff --git a/nir/nir.tex b/nir/nir.tex new file mode 100644 index 0000000..2a5a009 --- /dev/null +++ b/nir/nir.tex @@ -0,0 +1,1431 @@ +\documentclass[spec, och, nir]{SCWorks}
+\usepackage{preamble}
+
+\title{Вычисление чисел независимого доминирования и принудительных геодезических чисел}
+\course{5}
+\group{531}
+\author{Гущина Андрея Юрьевича}
+\satitle{д.ф.-м.н., доцент}
+\saname{М. Б. Абросимов}
+\date{2024}
+
+\begin{document}
+
+\input{titlepage.tex}
+\tableofcontents
+
+\intro
+
+Теория графов является одной из ключевых областей дискретной математики,
+находящей широкое применение в информатике, биоинформатике, социальных науках и
+многих других дисциплинах. Одним из важных понятий в этой области является
+доминирование. Это свойство позволяет эффективно моделировать различные
+ситуации, где необходимо контролировать или влиять на определённые элементы
+системы.
+
+Понятие доминирования в графах возникло в середине 19 века, когда исследователи
+начали изучать минимальные наборы вершин, которые могли бы <<контролировать>>
+или <<покрывать>> весь граф. Число доминирования, например, определяет
+минимальное количество вершин, таких, что каждая вершина графа либо принадлежит
+этому набору, либо смежна с вершиной из этого набора.
+
+Важным аспектом исследования доминирования является его связь с понятием
+геодоминирования, которое рассматривает более сложные структуры взаимодействия
+между вершинами. Геодоминирование включает анализ расстояний и связности между
+вершинами, что позволяет глубже понять динамику графов и их применение в
+реальных задачах, таких как оптимизация сетей и анализ социальных
+взаимодействий.
+
+В данной работе будут изучены и проанализированы подходы для разработки и
+вычислении таких параметров графов, как числа независимого доминирования и
+принудительные геодезические числа.
+
+
+\section{Основные определения}
+
+Пусть $G = (V, E)$ "--- неориентированный граф с множеством вершин $V$ и
+множеством рёбер $E$.
+
+\subsection{Число независимого доминирования}
+
+\begin{definition}
+ Говорят, что вершина $v$ считается доминирующей вершиной над вершиной $u$,
+ если $E$ содержит ребро от $v$ к $u$ или $v = u$. Множество вершин $D
+ \subseteq V$ называется доминирующим множеством графа $G$, если каждая
+ вершина графа доминируется как минимум одним элементом из $D$ \cite{pds1}.
+\end{definition}
+
+\begin{definition}
+ Доминирующее множество $D$ является минимальным, если ни одно другое
+ подмножество $D^{'} \subset D$ не является доминирующим множеством.
+ Минимальная мощность доминирующего множества графа $G$ называется числом
+ доминирования $G$ и обозначается $\gamma(G)$ \cite{pds2}.
+\end{definition}
+
+\begin{definition}
+ Множество вершин графа $G = (V, E)$ является независимым, если $(\forall a, b
+ \in V) (a, b) \not\in E$.
+\end{definition}
+
+\begin{definition}
+ Независимым доминирующим множеством графа $G$ называется множество $D$,
+ которое одновременно является доминирующим и независимым. Числом независимого
+ доминирования $i(G)$ называют минимальную мощность независимого доминирующего
+ множества в графе $G$ \cite{GODDARD2013839}.
+\end{definition}
+
+\subsubsection{Алгоритм вычисления числа независимого доминирования}
+
+Для нахождения числа независимого доминирования можно перебрать все возможные
+подграфы $S$ графа $G$. В случае, если множество вершин подграфа $S$ является
+независимым доминирующим множеством графа $G$, его мощность необходимо
+сохранить. Среди всех таких значений необходимо выбрать минимальное.
+
+\textbf{Вход:}
+ $G = (V, E)$, $H$ --- множество всех подграфов $G$
+
+\textbf{Выход:}
+ $i(G) \geq 0$
+
+\underline{Шаг 1.}
+ Составить множество $I_H$ всех подграфов $S = (V_S, E_S) \in H$, для
+ которых справедливо, что множество $V_S$ "--- независимо.
+
+\underline{Шаг 2.}
+ Присвоить $ID = \varnothing$.
+
+\underline{Шаг 3.}
+ Для каждого подграфа $S_I = (V_{S_I}, E_{S_I})$ выполнить шаги 4 -- 5.
+
+\underline{Шаг 4.}
+ Присвоить $d = 0$. Для каждой вершины $v \in V_{S_I}$ проверить, что
+ $\exists u_v \in (E - E_{S_I})$. Если такая $u_v$ нашлась, то увеличить $d$
+ на 1.
+
+\underline{Шаг 5.}
+ Если $d = |V_{S_I}|$, то множество $S_I$ является доминирующим и
+ необходимо добавить значение $|V_{S_I}|$ в множество $ID$.
+
+\underline{Шаг 6.}
+ Если остались не перебранные графы в множестве $H$, перейти к шагу 3.
+
+\underline{Шаг 7.}
+ Минимальное значение из множества $ID$ является числом $i(G)$ независимого
+ доминирования графа $G$.
+
+Для вычисления множества $H$ всех подграфов $G = (V, E)$, необходимо перебрать
+все возможные наборы вершин. Так как в очередной набор вершина может быть либо
+включена, либо не включена "--- таких наборов $2^{|G|}$. Для каждого из этих
+подграфов $S = (V_S, E_S)$ необходимо проверить, что $V_S$ является независимым
+и доминирующим в графе $G$. В случае независимости, это подразумевает перебор
+всех пар вершин $u, v \in V_S$, число которых равно $\frac{|V_S|^2}{2}$. В
+случае доминирования, это подразумевает перебор всех пар вершин $u \in V_S, v
+\in V - V_S$, число которых равно $|V_S| \cdot |V - V_S|$.
+
+С учётом того, что все множества $V_S$ являются подмножествами $V$, где $0 <
+|V_S| \leq |V|$, можно сделать вывод, что асимптотической сложностью данного
+алгоритма является $O(2^n \cdot n^2)$, где $n = |V|$.
+
+\subsection{Принудительное геодезическое число}
+
+Назовём $d(u, v): u, v \in V$ длиной кратчайшего пути между вершинами $u$ и $v$
+в графе $G$.
+
+\begin{definition}
+ Любой путь длины $d(u, v)$ между вершинами $u, v \in V$ называется
+ геодезическим. Говорят, что вершины $u$ и $v$ геодоминируют вершины, лежащие
+ на одном из их геодезических путей.
+\end{definition}
+
+\begin{definition}
+ Геодезическим множеством графа $G$ называется подмножество $S$ его вершин такое,
+ что каждая вершина графа $G$ принадлежит какому"=либо геодезическому пути,
+ соединяющему вершины из $S$.
+\end{definition}
+
+\begin{definition}
+ Геодезическое множество называют минимальным, если никакое его собственное
+ подмножество не является геодезическим.
+\end{definition}
+
+\begin{definition}
+ Геодезическим числом $g(G)$ графа $G$ называется минимальная мощность его
+ геодезического множества, а сами такие множества называются наименьшими
+ геодезическими множествами.
+\end{definition}
+
+\begin{definition}
+ Для наименьшего геодезического множества $S$ графа $G$, его подмножество $T$
+ такое, что оно не является частью никакого другого наименьшего геодезического
+ множества, называется принудительным подмножеством \cite{TONG20091159}.
+\end{definition}
+
+\begin{definition}
+ Минимальная мощность принудительного подмножества среди всех принудительных
+ подмножеств наименьших геодезических множеств графа $G$ называется
+ принудительным геодезическим числом $fg(G)$ \cite{TONG20091159}.
+\end{definition}
+
+\subsubsection{Алгоритм вычисления принудительного геодезического числа}
+
+\textbf{Вход:}
+ $G = (V, E)$, $H$ --- множество всех подграфов $G$
+
+\textbf{Выход:}
+ $fg(G) \geq 0$
+
+\underline{Шаг 1.}
+ Присвоить $GS = \varnothing$.
+
+\underline{Шаг 2.}
+ Для каждого подграфа $S = (V_S, E_S) \in H$ выполнить шаги 3 -- 5. Когда
+ все подграфы $S$ будут перебраны, перейти к шагу 6.
+
+\underline{Шаг 3.}
+ Присвоить $visited = V_S$.
+
+\underline{Шаг 4.}
+ Для каждой пары вершин $u, v \in V_S$ вычислить $d(u, v)$ и найти все
+ геодезические пути между ними. Все найденные пути присвоить $P_{uv}$.
+
+\underline{Шаг 5.}
+ Для каждого пути $p \in P_{uv}$ добавить все вершины, принадлежащие этому
+ пути, добавить во множество $visited$. Если $|visited| = |V|$, добавить
+ $V_S$ в множество $GS$ и перейти к шагу 2. Иначе "--- перейти к шагу 3.
+
+\underline{Шаг 6.}
+ Составить множество $GS_m$, состоящее из всех таких множеств, мощность
+ которых минимальна среди всех множеств $V_{GS} \in GS$.
+
+\underline{Шаг 7.}
+ Если $|GS_m| = 1$, то $fg(G) = 0$ и закончить выполнение алгоритма.
+
+\underline{Шаг 8.}
+ Присвоить $FG = \varnothing$.
+
+\underline{Шаг 9.}
+ Для каждого множества $V_m \in GS_m$ выполнить шаги 10 -- 11. Присвоить
+ $verts = V_m$. Если все множества $V_m$ перебраны, перейти к шагу 12.
+
+\underline{Шаг 10.}
+ Для каждого множества $V_o \in (GS_M - \set{V_m})$ обновить $verts = verts
+ - V_o$.
+
+\underline{Шаг 11.}
+ Добавить множество $verts$ в множество $FG$ и перейти к шагу 9.
+
+\underline{Шаг 12.}
+ Минимальная мощность множества $V_{FG} \in FG$ является принудительным
+ геодезическим числом $fg(G)$ графа $G$.
+
+Для вычисления множества $H$ всех подграфов $G = (V, E)$, необходимо перебрать
+все возможные наборы вершин. Так как в очередной набор вершина может быть либо
+включена, либо не включена "--- таких наборов $2^{|G|}$. Для каждого из этих
+подграфов $S = (V_S, E_S)$ необходимо найти все геодезические пути между всеми
+парами вершин $u, v \in V_S, u \neq v$, число которых равно
+$\frac{|V_S|^2}{2}$. Поиск геодезических путей можно выполнить, например, с
+помощью алгоритма поиска в ширину, сложность которого равна $O(n + m)$, где $n$
+"--- количество вершин, $m$ "--- количество рёбер.
+
+Далее необходимо сравнить каждое найденное геодезическое множество со всеми
+остальными. Ассимптотическую сложность такого перебора можно оценить как
+квадратичную, что меньше перебора всех подграфов, поэтому при оценке сложности
+всего алгоритма, этим можно пренебречь.
+
+С учётом того, что все множества $V_S$ являются подмножествами $V$, где $0 <
+|V_S| \leq |V|$, можно сделать вывод, что асимптотической сложностью данного
+алгоритма является $O(2^n \cdot n^2 \cdot (n + m))$, где $n = |V|$, $m = |E|$.
+
+\section{Вычислительный эксперимент}
+
+Для произведения вычислительного эксперимента была использована программа
+\emph{geng} из пакета \emph{nauty} \cite{mckay2014practical} для генерации
+графов.
+
+Для выполнения непосредственных вычислений была написана программа на языке
+программирования Rust, исходный код которой указан в Приложениях
+\ref{app:rust1} -- \ref{app:rust5}.
+
+Помимо самой программы, была адаптирована программа \emph{geng} для выполнения
+перебора графов программно, а не с помощью чтения из стандартного ввода. С
+помощью библиотеки \emph{tokio} было выполнено распределение вычислений по всем
+ядрам процессора. Так как параметры \emph{res/mod} утилиты \emph{geng} не
+позволяют разделить перебор всех неизоморфных графов на равные части, такой
+подход позволил \emph{равномерно} распределить вычисления.
+
+Исходный код упомянутой адаптации утилиты \emph{geng} указан в Приложении
+\ref{app:geng_iter}.
+
+Визуализации графов подготовлены с помощью программы на языке программирования
+Python с использованием библиотеки NetworkX. Визуализации выводятся в формате
+PGF/TikZ (Приложение \ref{app:drawer}).
+
+Результаты вычислительного эксперимента были записаны в БД под управлением СУБД
+Sqlite. Каждый граф идентифицируется в БД с помощью своего представления в
+формате \emph{graph6} \cite{graph6}.
+
+Вычисления проводились на двух процессорах:
+\begin{itemize}
+ \item 16-ядерный AMD Ryzen 7 5825U;
+ \item ARM-процессор с 64 x Cortex-A72 ядрами.
+\end{itemize}
+
+\subsection{Результаты вычислительного эксперимента}
+
+В таблице \ref{tbl:timelen} указано время выполнения разработанной программы с
+разделением по количеству вершин $n$ анализируемых графов. В последнем столбце
+указан процессор с количеством ядер, использованный для выполнения анализа
+конкретной группы графов.
+
+\begin{table}[h]
+ \centering
+ \caption{Длительность вычислительного эксперимента}
+ \begin{tabular}{|c|c|c|c|}
+ \hline
+ $n$ & Кол-во графов & Время работы & Процессор \\ \hline
+ 2 & 2 & 0.00111 c. & 16 x AMD Ryzen 7 5825U \\ \hline
+ 3 & 4 & 0.00157 c. & 16 x AMD Ryzen 7 5825U \\ \hline
+ 4 & 11 & 0.00202 c. & 16 x AMD Ryzen 7 5825U \\ \hline
+ 5 & 34 & 0.00213 c. & 16 x AMD Ryzen 7 5825U \\ \hline
+ 6 & 156 & 0.0116 c. & 16 x AMD Ryzen 7 5825U \\ \hline
+ 7 & 1044 & 0.17 c. & 16 x AMD Ryzen 7 5825U \\ \hline
+ 8 & 12346 & 9.31 c. & 16 x AMD Ryzen 7 5825U \\ \hline
+ 9 & 274668 & 1446.86 $\approx$ 24 мин. & 16 x AMD Ryzen 7 5825U \\ \hline
+ 10 & 12005168 & 199430.86 $\approx$ 55 ч. & 64 x Cortex-A72 \\ \hline
+ \end{tabular}
+ \label{tbl:timelen}
+\end{table}
+
+
+В таблицах \ref{tbl:gr2} -- \ref{tbl:gr10} указаны результаты вычислений. В
+первом ряду указаны возможные значения принудительного геодезического числа
+$fg(G)$. В первой колонке указаны возможные значения числа независимого
+доминирования $i(G)$. На пересечениях рядов и колонок указано количество
+графов, значения $fg(G)$ и $i(G)$ соответствуют значениям, указанным в первом
+ряду и первой колонке.
+
+\begin{table}[H]
+ \centering
+ \caption{Результаты вычислений для графов с 2 вершинами}
+ \begin{tabular}{|c|c|c|c|}
+ \hline
+ $i(G)$ \textbackslash{} $fg(G)$ & 0 & 1 & 2 \\ \hline
+ 1 & 1 & 0 & 0 \\ \hline
+ 2 & 1 & 0 & 0 \\ \hline
+ \end{tabular}
+ \label{tbl:gr2}
+\end{table}
+
+\begin{table}[H]
+ \centering
+ \caption{Результаты вычислений для графов с 3 вершинами}
+ \begin{tabular}{|c|c|c|c|c|}
+ \hline
+ $i(G)$ \textbackslash{} $fg(G)$ & 0 & 1 & 2 & 3 \\ \hline
+ 1 & 2 & 0 & 0 & 0 \\ \hline
+ 2 & 1 & 0 & 0 & 0 \\ \hline
+ 3 & 1 & 0 & 0 & 0 \\ \hline
+ \end{tabular}
+ \label{tbl:gr3}
+\end{table}
+
+\begin{table}[H]
+ \centering
+ \caption{Результаты вычислений для графов с 4 вершинами}
+ \begin{tabular}{|c|c|c|c|c|c|}
+ \hline
+ $i(G)$ \textbackslash{} $fg(G)$ & 0 & 1 & 2 & 3 & 4 \\ \hline
+ 1 & 4 & 0 & 0 & 0 & 0 \\ \hline
+ 2 & 4 & 0 & 1 & 0 & 0 \\ \hline
+ 3 & 1 & 0 & 0 & 0 & 0 \\ \hline
+ 4 & 1 & 0 & 0 & 0 & 0 \\ \hline
+ \end{tabular}
+ \label{tbl:gr4}
+\end{table}
+
+\begin{table}[H]
+ \centering
+ \caption{Результаты вычислений для графов с 5 вершинами}
+ \begin{tabular}{|c|c|c|c|c|c|c|}
+ \hline
+ $i(G)$ \textbackslash{} $fg(G)$ & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline
+ 1 & 8 & 1 & 1 & 0 & 0 & 0 \\ \hline
+ 2 & 16 & 1 & 0 & 0 & 0 & 0 \\ \hline
+ 3 & 5 & 0 & 0 & 0 & 0 & 0 \\ \hline
+ 4 & 1 & 0 & 0 & 0 & 0 & 0 \\ \hline
+ 5 & 1 & 0 & 0 & 0 & 0 & 0 \\ \hline
+ \end{tabular}
+ \label{tbl:gr5}
+\end{table}
+
+\begin{table}[H]
+ \centering
+ \caption{Результаты вычислений для графов с 6 вершинами}
+ \begin{tabular}{|c|c|c|c|c|c|c|c|}
+ \hline
+ $i(G)$ \textbackslash{} $fg(G)$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline
+ 1 & 25 & 5 & 3 & 0 & 0 & 0 & 0 \\ \hline
+ 2 & 66 & 11 & 7 & 2 & 0 & 0 & 0 \\ \hline
+ 3 & 25 & 2 & 2 & 1 & 0 & 0 & 0 \\ \hline
+ 4 & 5 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline
+ 5 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline
+ 6 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline
+ \end{tabular}
+ \label{tbl:gr6}
+\end{table}
+
+\begin{table}[H]
+ \centering
+ \caption{Результаты вычислений для графов с 7 вершинами}
+ \begin{tabular}{|c|c|c|c|c|c|c|c|c|}
+ \hline
+ $i(G)$ \textbackslash{} $fg(G)$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline
+ 1 & 59 & 20 & 8 & 2 & 0 & 0 & 0 & 0 \\ \hline
+ 2 & 373 & 129 & 62 & 10 & 0 & 0 & 0 & 0 \\ \hline
+ 3 & 210 & 48 & 26 & 1 & 0 & 0 & 0 & 0 \\ \hline
+ 4 & 73 & 3 & 7 & 0 & 0 & 0 & 0 & 0 \\ \hline
+ 5 & 11 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline
+ 6 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline
+ 7 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline
+ \end{tabular}
+ \label{tbl:gr7}
+\end{table}
+
+\begin{table}[H]
+ \centering
+ \caption{Результаты вычислений для графов с 8 вершинами}
+ \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
+ \hline
+ $i(G)$ \textbackslash{} $fg(G)$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline
+ 1 & 485 & 254 & 93 & 27 & 0 & 0 & 0 & 0 & 0 \\ \hline
+ 2 & 4569 & 2059 & 897 & 133 & 1 & 0 & 0 & 0 & 0 \\ \hline
+ 3 & 1739 & 555 & 200 & 15 & 2 & 0 & 0 & 0 & 0 \\ \hline
+ 4 & 801 & 206 & 78 & 2 & 1 & 0 & 0 & 0 & 0 \\ \hline
+ 5 & 183 & 14 & 10 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline
+ 6 & 19 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline
+ 7 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline
+ 8 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline
+ \end{tabular}
+ \label{tbl:gr8}
+\end{table}
+
+\begin{table}[H]
+ \centering
+ \caption{Результаты вычислений для графов с 9 вершинами}
+ \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
+ \hline
+ $i(G)$ \textbackslash{} $fg(G)$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline
+ 1 & 6110 & 4128 & 1279 & 379 & 23 & 0 & 0 & 0 & 0 & 0 \\ \hline
+ 2 & 108690 & 63700 & 20121 & 3381 & 150 & 0 & 0 & 0 & 0 & 0 \\ \hline
+ 3 & 34947 & 18494 & 5062 & 490 & 17 & 0 & 0 & 0 & 0 & 0 \\ \hline
+ 4 & 4074 & 1087 & 293 & 22 & 3 & 0 & 0 & 0 & 0 & 0 \\ \hline
+ 5 & 1307 & 360 & 84 & 3 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline
+ 6 & 395 & 34 & 8 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline
+ 7 & 25 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline
+ 8 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline
+ 9 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline
+ \end{tabular}
+ \label{tbl:gr9}
+\end{table}
+
+\begin{table}[H]
+ \centering
+ \caption{Результаты вычислений для графов с 10 вершинами}
+ \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|}
+ \hline
+ $i(G)$ \textbackslash{} $fg(G)$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline
+ 1 & 126042 & 105165 & 25873 & 8402 & 973 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline
+ 2 & 4305543 & 3337594 & 787147 & 164044 & 19062 & 11 & 0 & 0 & 0 & 0 & 0 \\ \hline
+ 3 & 1434656 & 1137131 & 237609 & 39140 & 3038 & 3 & 0 & 0 & 0 & 0 & 0 \\ \hline
+ 4 & 141618 & 72118 & 15646 & 1907 & 289 & 1 & 0 & 0 & 0 & 0 & 0 \\ \hline
+ 5 & 23836 & 12234 & 3025 & 258 & 20 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline
+ 6 & 2065 & 479 & 130 & 4 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline
+ 7 & 91 & 5 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline
+ 8 & 7 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline
+ 9 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline
+ 10 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline
+ \end{tabular}
+ \label{tbl:gr10}
+\end{table}
+
+\section{Гипотезы на основе вычислительного эксперимента}
+
+По результатам эксперимента видно, что для всех рассмотренных графов, значение
+принудительного геодезического числа $fg(G) \leq \lfloor \frac{n}{2} \rfloor$.
+При этом, $fg(G) = \lfloor \frac{n}{2} \rfloor$ только при $(\lfloor \frac{n}{2}
+\rfloor - 1) \leq i(G) \leq \lfloor \frac{n}{2} \rfloor$ (для $n > 5$).
+
+Из этого можно сделать вывод, что мощность геодезического множества $\geq
+\lfloor \frac{n}{2} \rfloor$. При этом минимальных геодезических множеств
+больше одного, так как в ином случае $fg(G) = 0$.
+
+Допустим, что принудительное геодезическое число равно $(\lfloor \frac{n}{2}
+\rfloor + 1)$. Пусть минимальное геодезическое множество $G_0$ состоит из ровно
+такого же количества вершин, все из которых уникальны для этого множества.
+Другое минимальное геодезическое множество должно состоять из такого же
+количества вершин, которые также должны быть уникальными для него (иначе,
+$fg(G) \neq (\lfloor \frac{n}{2} \rfloor + 1)$, что противоречит предположению).
+Получаем, что в этих двух множествах количество вершин равно
+\begin{equation*}
+ \left(\left\lfloor \frac{n}{2} \right\rfloor + 1\right) \cdot 2 =
+ 2 \left\lfloor \frac{n}{2} \right\rfloor + 2
+\end{equation*}
+
+При чётном $n$ значение $2 \lfloor \frac{n}{2} \rfloor = n$. При нечётном "---
+$2 \lfloor \frac{n}{2} \rfloor = n - 1$. Получаем, что в $G_0 \cap G_1$ на 1
+вершину больше, чем в графе $G$, если $n$ "--- нечётное и на две, если $n$ "---
+чётное, что невозможно. Получаем, что
+\begin{equation*}
+ fg(G) < \left\lfloor \frac{n}{2} \right\rfloor + 1
+\end{equation*}
+
+Если $n$ --- чётное, то $fg(G) = \lfloor \frac{n}{2} \rfloor$ только в том случае,
+если существует два непересекающихся минимальных геодезических множества
+мощности $\lfloor \frac{n}{2} \rfloor$ (например, рис. \ref{fig:fg_even}, где
+$G_0 = \set{0, 1, 2}$, $G_1 = \set{3, 4, 5}$).
+
+\begin{figure}[h]
+ \centering
+ \begin{tikzpicture}[scale=4]
+ \draw
+ (1.0, 0.0) node[line width=1.5, draw=black, circle] (0){0}
+ (0.5, 0.866) node[line width=1.5, draw=black, circle] (1){1}
+ (-0.5, 0.866) node[line width=1.5, draw=black, circle] (2){2}
+ (-1.0, -0.0) node[line width=1.5, draw=black, circle] (3){3}
+ (-0.5, -0.866) node[line width=1.5, draw=black, circle] (4){4}
+ (0.5, -0.866) node[line width=1.5, draw=black, circle] (5){5};
+ \begin{scope}[-]
+ \draw[line width=1.5] (0) to (3);
+ \draw[line width=1.5] (0) to (4);
+ \draw[line width=1.5] (0) to (5);
+ \draw[line width=1.5] (1) to (3);
+ \draw[line width=1.5] (1) to (4);
+ \draw[line width=1.5] (1) to (5);
+ \draw[line width=1.5] (2) to (3);
+ \draw[line width=1.5] (2) to (4);
+ \draw[line width=1.5] (2) to (5);
+ \draw[line width=1.5] (3) to (5);
+ \end{scope}
+ \end{tikzpicture}
+ \caption{Визуализация графа <<EFzo>>}
+ \label{fig:fg_even}
+\end{figure}
+
+Если $n$ --- нечётное, то $fg(G) = \lfloor \frac{n}{2} \rfloor$ только в том
+случае, если существует два минимальных геодезических
+множества мощности $(\lfloor \frac{n}{2} \rfloor + 1)$, пересекающихся в одной
+вершине (например, рис.
+\ref{fig:fg_odd}, где $G_0 = \set{0, 1, 2, 3}$, $G_1 = \set{0, 4, 5, 6}$).
+
+\begin{figure}[h]
+ \centering
+ \begin{tikzpicture}[scale=4]
+ \draw
+ (1.0, 0.0) node[line width=1.5, draw=black, circle] (0){0}
+ (0.623, 0.782) node[line width=1.5, draw=black, circle] (1){1}
+ (-0.223, 0.975) node[line width=1.5, draw=black, circle] (2){2}
+ (-0.901, 0.434) node[line width=1.5, draw=black, circle] (3){3}
+ (-0.901, -0.434) node[line width=1.5, draw=black, circle] (4){4}
+ (-0.223, -0.975) node[line width=1.5, draw=black, circle] (5){5}
+ (0.623, -0.782) node[line width=1.5, draw=black, circle] (6){6};
+ \begin{scope}[-]
+ \draw[line width=1.5] (0) to (3);
+ \draw[line width=1.5] (0) to (4);
+ \draw[line width=1.5] (0) to (5);
+ \draw[line width=1.5] (0) to (6);
+ \draw[line width=1.5] (1) to (3);
+ \draw[line width=1.5] (1) to (5);
+ \draw[line width=1.5] (1) to (6);
+ \draw[line width=1.5] (2) to (4);
+ \draw[line width=1.5] (2) to (5);
+ \draw[line width=1.5] (2) to (6);
+ \draw[line width=1.5] (3) to (6);
+ \draw[line width=1.5] (4) to (6);
+ \draw[line width=1.5] (5) to (6);
+ \end{scope}
+ \end{tikzpicture}
+ \caption{Визуализация графа <<FEjfw>>}
+ \label{fig:fg_odd}
+\end{figure}
+
+Помимо этого, можно увидеть, что при $fg(G) = 0$ значения $i(G)$ варьируются от
+1 до $n$. Очевидно, что у всех несвязных графов $fg(G) = 0$, поэтому они
+находятся только в этих колонках.
+
+Но при $fg(G) > 0$ значение $i(G) < (n - 2)$ (при $n > 4$).
+Необходимо отметить, что $i(G) = n$ может быть только в случае, если граф
+пустой. Но в пустом графе не может быть $fg(G) > 0$. Поэтому $i(G) = n$ и
+$fg(G) > 0$ не может быть ни у одного графа. $i(G) = 1$ при этом может быть
+только у полного графа. Но у полного графа минимальными геодезическими
+множествами являются любые две пары вершин. То есть ни в одной из таких пар нет
+уникальной вершины, находящейся только в этой паре. Таким образом, $fg(G) = 0$.
+Для всех остальных графов не может быть справедливо одновременно $i(G) = 1$ и
+$fg(G) > 0$.
+
+Рассмотрим случай с $i(G) = n - 2$. Получаем, что существует $n - 2$ вершины
+(обозначим множеством $V_i$), не смежные между собой и каждая из них смежна
+хотя бы с одной из двух оставшихся вершин $u$ и $v$ (по определению
+доминирования).
+
+В случае, если граф не связный, $fg(G) = 0$, поэтому рассмотрим только случаи
+связных графов.
+
+Если $u$ и $v$ смежны, то существует как минимум один путь между двумя
+вершинами из $V_i$, проходящий через $u$ и $v$ одновременно. Таким образом,
+минимальное геодезическое множество равно $V_i$ и будет единственным. В таком
+случае $fg(G) = 0$.
+
+Если $u$ и $v$ не смежны, то существует два случая:
+\begin{itemize}
+ \item
+ Все вершины из $V_i$ смежны как с $u$, так и с $v$. Таким образом,
+ минимальное геодезическое множество будет равно $\set{u, v}$ и будет
+ единственным. В таком случае $fg(G) = 0$;
+ \item
+ Иначе, если хотя бы одна $v_i \in V_i$ смежна либо с $u$, либо с $v$,
+ можно провести два пути между вершинами из $V_i$, один из которых пройдёт
+ через $u$, а другой через $v$. При этом минимальное геодезическое множество
+ будет равно $V_i$ и будет единственным. То есть $fg(G) = 0$.
+\end{itemize}
+
+Получаем, что при $i(G) = n - 2$, значение $fg(G)$ обязано равняться 0.
+Аналогичный вывод можно получить для $i(G) = n - 1$.
+
+\section{Каталог графов}
+
+В этом разделе представлен каталог графов, для которых были вычислены значения
+чисел независимого доминирования $i(G)$ и принудительных геодезических чисел
+$fg(G)$.
+
+\begin{figure}[h]
+ \centering
+ \begin{tikzpicture}[scale=3]
+ \draw
+ (1.0, 0.0) node[line width=1.5, draw=black, circle] (0){0}
+ (-0.0, 1.0) node[line width=1.5, draw=black, circle] (1){1}
+ (-1.0, -0.0) node[line width=1.5, draw=black, circle] (2){2}
+ (0.0, -1.0) node[line width=1.5, draw=black, circle] (3){3};
+ \begin{scope}[-]
+ \draw[line width=1.5] (0) to (2);
+ \draw[line width=1.5] (0) to (3);
+ \draw[line width=1.5] (1) to (2);
+ \draw[line width=1.5] (1) to (3);
+ \end{scope}
+ \end{tikzpicture}
+ \caption{Визуализация графа <<C]>>, $i(G) = 2, fg(G) = 2$}
+\end{figure}
+
+\begin{figure}[h]
+ \centering
+ \begin{tikzpicture}[scale=4]
+ \draw
+ (1.0, 0.0) node[line width=1.5, draw=black, circle] (0){0}
+ (0.309, 0.951) node[line width=1.5, draw=black, circle] (1){1}
+ (-0.809, 0.588) node[line width=1.5, draw=black, circle] (2){2}
+ (-0.809, -0.588) node[line width=1.5, draw=black, circle] (3){3}
+ (0.309, -0.951) node[line width=1.5, draw=black, circle] (4){4};
+ \begin{scope}[-]
+ \draw[line width=1.5] (0) to (2);
+ \draw[line width=1.5] (0) to (3);
+ \draw[line width=1.5] (0) to (4);
+ \draw[line width=1.5] (1) to (2);
+ \draw[line width=1.5] (1) to (3);
+ \draw[line width=1.5] (1) to (4);
+ \draw[line width=1.5] (2) to (4);
+ \draw[line width=1.5] (3) to (4);
+ \end{scope}
+ \end{tikzpicture}
+ \caption{Визуализация графа <<D]\{>>, $i(G) = 2, fg(G) = 2$}
+\end{figure}
+
+\begin{figure}[h]
+ \centering
+ \begin{tikzpicture}[scale=4]
+ \draw
+ (1.0, 0.0) node[line width=1.5, draw=black, circle] (0){0}
+ (0.5, 0.866) node[line width=1.5, draw=black, circle] (1){1}
+ (-0.5, 0.866) node[line width=1.5, draw=black, circle] (2){2}
+ (-1.0, -0.0) node[line width=1.5, draw=black, circle] (3){3}
+ (-0.5, -0.866) node[line width=1.5, draw=black, circle] (4){4}
+ (0.5, -0.866) node[line width=1.5, draw=black, circle] (5){5};
+ \begin{scope}[-]
+ \draw[line width=1.5] (0) to (4);
+ \draw[line width=1.5] (0) to (5);
+ \draw[line width=1.5] (1) to (5);
+ \draw[line width=1.5] (2) to (5);
+ \draw[line width=1.5] (4) to (5);
+ \end{scope}
+ \end{tikzpicture}
+ \caption{Визуализация графа <<E?bg>>, $i(G) = 4, fg(G) = 0$}
+\end{figure}
+
+\begin{figure}[h]
+ \centering
+ \begin{tikzpicture}[scale=4]
+ \draw
+ (1.0, 0.0) node[line width=1.5, draw=black, circle] (0){0}
+ (0.5, 0.866) node[line width=1.5, draw=black, circle] (1){1}
+ (-0.5, 0.866) node[line width=1.5, draw=black, circle] (2){2}
+ (-1.0, -0.0) node[line width=1.5, draw=black, circle] (3){3}
+ (-0.5, -0.866) node[line width=1.5, draw=black, circle] (4){4}
+ (0.5, -0.866) node[line width=1.5, draw=black, circle] (5){5};
+ \begin{scope}[-]
+ \draw[line width=1.5] (0) to (3);
+ \draw[line width=1.5] (0) to (4);
+ \draw[line width=1.5] (1) to (4);
+ \draw[line width=1.5] (1) to (5);
+ \draw[line width=1.5] (2) to (5);
+ \draw[line width=1.5] (3) to (5);
+ \end{scope}
+ \end{tikzpicture}
+ \caption{Визуализация графа <<ECpo>>, $i(G) = 3, fg(G) = 1$}
+\end{figure}
+
+\begin{figure}[h]
+ \centering
+ \begin{tikzpicture}[scale=4]
+ \draw
+ (1.0, 0.0) node[line width=1.5, draw=black, circle] (0){0}
+ (0.623, 0.782) node[line width=1.5, draw=black, circle] (1){1}
+ (-0.223, 0.975) node[line width=1.5, draw=black, circle] (2){2}
+ (-0.901, 0.434) node[line width=1.5, draw=black, circle] (3){3}
+ (-0.901, -0.434) node[line width=1.5, draw=black, circle] (4){4}
+ (-0.223, -0.975) node[line width=1.5, draw=black, circle] (5){5}
+ (0.623, -0.782) node[line width=1.5, draw=black, circle] (6){6};
+ \begin{scope}[-]
+ \draw[line width=1.5] (0) to (4);
+ \draw[line width=1.5] (0) to (5);
+ \draw[line width=1.5] (0) to (6);
+ \draw[line width=1.5] (1) to (4);
+ \draw[line width=1.5] (1) to (5);
+ \draw[line width=1.5] (2) to (5);
+ \draw[line width=1.5] (2) to (6);
+ \draw[line width=1.5] (3) to (6);
+ \draw[line width=1.5] (4) to (6);
+ \draw[line width=1.5] (5) to (6);
+ \end{scope}
+ \end{tikzpicture}
+ \caption{Визуализация графа <<F?rdw>>, $i(G) = 4, fg(G) = 2$}
+\end{figure}
+
+\begin{figure}[h]
+ \centering
+ \begin{tikzpicture}[scale=4]
+ \draw
+ (1.0, 0.0) node[line width=1.5, draw=black, circle] (0){0}
+ (0.623, 0.782) node[line width=1.5, draw=black, circle] (1){1}
+ (-0.223, 0.975) node[line width=1.5, draw=black, circle] (2){2}
+ (-0.901, 0.434) node[line width=1.5, draw=black, circle] (3){3}
+ (-0.901, -0.434) node[line width=1.5, draw=black, circle] (4){4}
+ (-0.223, -0.975) node[line width=1.5, draw=black, circle] (5){5}
+ (0.623, -0.782) node[line width=1.5, draw=black, circle] (6){6};
+ \begin{scope}[-]
+ \draw[line width=1.5] (0) to (1);
+ \draw[line width=1.5] (0) to (2);
+ \draw[line width=1.5] (0) to (3);
+ \draw[line width=1.5] (0) to (4);
+ \draw[line width=1.5] (0) to (5);
+ \draw[line width=1.5] (0) to (6);
+ \draw[line width=1.5] (1) to (2);
+ \draw[line width=1.5] (1) to (3);
+ \draw[line width=1.5] (1) to (4);
+ \draw[line width=1.5] (1) to (5);
+ \draw[line width=1.5] (1) to (6);
+ \draw[line width=1.5] (2) to (3);
+ \draw[line width=1.5] (2) to (4);
+ \draw[line width=1.5] (2) to (5);
+ \draw[line width=1.5] (2) to (6);
+ \draw[line width=1.5] (3) to (4);
+ \draw[line width=1.5] (3) to (5);
+ \draw[line width=1.5] (3) to (6);
+ \draw[line width=1.5] (4) to (5);
+ \draw[line width=1.5] (4) to (6);
+ \draw[line width=1.5] (5) to (6);
+ \end{scope}
+ \end{tikzpicture}
+ \caption{Визуализация графа <<F~~~w>>, $i(G) = 1, fg(G) = 0$}
+\end{figure}
+
+\begin{figure}[h]
+ \centering
+ \begin{tikzpicture}[scale=4]
+ \draw
+ (1.0, 0.0) node[line width=1.5, draw=black, circle] (0){0}
+ (0.707, 0.707) node[line width=1.5, draw=black, circle] (1){1}
+ (-0.0, 1.0) node[line width=1.5, draw=black, circle] (2){2}
+ (-0.707, 0.707) node[line width=1.5, draw=black, circle] (3){3}
+ (-1.0, -0.0) node[line width=1.5, draw=black, circle] (4){4}
+ (-0.707, -0.707) node[line width=1.5, draw=black, circle] (5){5}
+ (0.0, -1.0) node[line width=1.5, draw=black, circle] (6){6}
+ (0.707, -0.707) node[line width=1.5, draw=black, circle] (7){7};
+ \begin{scope}[-]
+ \draw[line width=1.5] (0) to (4);
+ \draw[line width=1.5] (0) to (5);
+ \draw[line width=1.5] (1) to (4);
+ \draw[line width=1.5] (1) to (7);
+ \draw[line width=1.5] (2) to (5);
+ \draw[line width=1.5] (2) to (6);
+ \draw[line width=1.5] (3) to (6);
+ \draw[line width=1.5] (3) to (7);
+ \draw[line width=1.5] (4) to (6);
+ \draw[line width=1.5] (5) to (7);
+ \end{scope}
+ \end{tikzpicture}
+ \caption{Визуализация графа <<G?q`qg>>, $i(G) = 4, fg(G) = 4$}
+\end{figure}
+
+\begin{figure}[h]
+ \centering
+ \begin{tikzpicture}[scale=4]
+ \draw
+ (1.0, 0.0) node[line width=1.5, draw=black, circle] (0){0}
+ (0.707, 0.707) node[line width=1.5, draw=black, circle] (1){1}
+ (-0.0, 1.0) node[line width=1.5, draw=black, circle] (2){2}
+ (-0.707, 0.707) node[line width=1.5, draw=black, circle] (3){3}
+ (-1.0, -0.0) node[line width=1.5, draw=black, circle] (4){4}
+ (-0.707, -0.707) node[line width=1.5, draw=black, circle] (5){5}
+ (0.0, -1.0) node[line width=1.5, draw=black, circle] (6){6}
+ (0.707, -0.707) node[line width=1.5, draw=black, circle] (7){7};
+ \begin{scope}[-]
+ \draw[line width=1.5] (0) to (3);
+ \draw[line width=1.5] (0) to (5);
+ \draw[line width=1.5] (0) to (6);
+ \draw[line width=1.5] (1) to (4);
+ \draw[line width=1.5] (1) to (5);
+ \draw[line width=1.5] (1) to (6);
+ \draw[line width=1.5] (2) to (5);
+ \draw[line width=1.5] (2) to (6);
+ \draw[line width=1.5] (2) to (7);
+ \draw[line width=1.5] (3) to (5);
+ \draw[line width=1.5] (3) to (7);
+ \draw[line width=1.5] (4) to (6);
+ \draw[line width=1.5] (4) to (7);
+ \draw[line width=1.5] (5) to (7);
+ \draw[line width=1.5] (6) to (7);
+ \end{scope}
+ \end{tikzpicture}
+ \caption{Визуализация графа <<GCRvP\{>>, $i(G) = 3, fg(G) = 4$}
+\end{figure}
+
+\begin{figure}[h]
+ \centering
+ \begin{tikzpicture}[scale=4]
+ \draw
+ (1.0, 0.0) node[line width=1.5, draw=black, circle] (0){0}
+ (0.707, 0.707) node[line width=1.5, draw=black, circle] (1){1}
+ (-0.0, 1.0) node[line width=1.5, draw=black, circle] (2){2}
+ (-0.707, 0.707) node[line width=1.5, draw=black, circle] (3){3}
+ (-1.0, -0.0) node[line width=1.5, draw=black, circle] (4){4}
+ (-0.707, -0.707) node[line width=1.5, draw=black, circle] (5){5}
+ (0.0, -1.0) node[line width=1.5, draw=black, circle] (6){6}
+ (0.707, -0.707) node[line width=1.5, draw=black, circle] (7){7};
+ \begin{scope}[-]
+ \draw[line width=1.5] (0) to (3);
+ \draw[line width=1.5] (0) to (6);
+ \draw[line width=1.5] (0) to (7);
+ \draw[line width=1.5] (1) to (4);
+ \draw[line width=1.5] (1) to (6);
+ \draw[line width=1.5] (1) to (7);
+ \draw[line width=1.5] (2) to (5);
+ \draw[line width=1.5] (2) to (6);
+ \draw[line width=1.5] (2) to (7);
+ \draw[line width=1.5] (3) to (6);
+ \draw[line width=1.5] (3) to (7);
+ \draw[line width=1.5] (4) to (6);
+ \draw[line width=1.5] (5) to (7);
+ \end{scope}
+ \end{tikzpicture}
+ \caption{Визуализация графа <<GCOfvg>>, $i(G) = 3, fg(G) = 2$}
+\end{figure}
+
+\begin{figure}[h]
+ \centering
+ \begin{tikzpicture}[scale=4]
+ \draw
+ (1.0, 0.0) node[line width=1.5, draw=black, circle] (0){0}
+ (0.707, 0.707) node[line width=1.5, draw=black, circle] (1){1}
+ (-0.0, 1.0) node[line width=1.5, draw=black, circle] (2){2}
+ (-0.707, 0.707) node[line width=1.5, draw=black, circle] (3){3}
+ (-1.0, -0.0) node[line width=1.5, draw=black, circle] (4){4}
+ (-0.707, -0.707) node[line width=1.5, draw=black, circle] (5){5}
+ (0.0, -1.0) node[line width=1.5, draw=black, circle] (6){6}
+ (0.707, -0.707) node[line width=1.5, draw=black, circle] (7){7};
+ \begin{scope}[-]
+ \draw[line width=1.5] (0) to (7);
+ \draw[line width=1.5] (1) to (7);
+ \draw[line width=1.5] (2) to (7);
+ \end{scope}
+ \end{tikzpicture}
+ \caption{Визуализация графа <<G???F?>>, $i(G) = 7, fg(G) = 0$}
+\end{figure}
+
+\begin{figure}[h]
+ \centering
+ \begin{tikzpicture}[scale=4]
+ \draw
+ (1.0, 0.0) node[line width=1.5, draw=black, circle] (0){0}
+ (0.707, 0.707) node[line width=1.5, draw=black, circle] (1){1}
+ (-0.0, 1.0) node[line width=1.5, draw=black, circle] (2){2}
+ (-0.707, 0.707) node[line width=1.5, draw=black, circle] (3){3}
+ (-1.0, -0.0) node[line width=1.5, draw=black, circle] (4){4}
+ (-0.707, -0.707) node[line width=1.5, draw=black, circle] (5){5}
+ (0.0, -1.0) node[line width=1.5, draw=black, circle] (6){6}
+ (0.707, -0.707) node[line width=1.5, draw=black, circle] (7){7};
+ \begin{scope}[-]
+ \draw[line width=1.5] (0) to (5);
+ \draw[line width=1.5] (0) to (6);
+ \draw[line width=1.5] (1) to (6);
+ \draw[line width=1.5] (1) to (7);
+ \draw[line width=1.5] (2) to (6);
+ \draw[line width=1.5] (3) to (7);
+ \draw[line width=1.5] (4) to (7);
+ \draw[line width=1.5] (5) to (7);
+ \end{scope}
+ \end{tikzpicture}
+ \caption{Визуализация графа <<G?AFAw>>, $i(G) = 5, fg(G) = 1$}
+\end{figure}
+
+\begin{figure}[h]
+ \centering
+ \begin{tikzpicture}[scale=4]
+ \draw
+ (1.0, 0.0) node[line width=1.5, draw=black, circle] (0){0}
+ (0.766, 0.643) node[line width=1.5, draw=black, circle] (1){1}
+ (0.174, 0.985) node[line width=1.5, draw=black, circle] (2){2}
+ (-0.5, 0.866) node[line width=1.5, draw=black, circle] (3){3}
+ (-0.94, 0.342) node[line width=1.5, draw=black, circle] (4){4}
+ (-0.94, -0.342) node[line width=1.5, draw=black, circle] (5){5}
+ (-0.5, -0.866) node[line width=1.5, draw=black, circle] (6){6}
+ (0.174, -0.985) node[line width=1.5, draw=black, circle] (7){7}
+ (0.766, -0.643) node[line width=1.5, draw=black, circle] (8){8};
+ \begin{scope}[-]
+ \draw[line width=1.5] (0) to (2);
+ \draw[line width=1.5] (0) to (4);
+ \draw[line width=1.5] (0) to (5);
+ \draw[line width=1.5] (0) to (6);
+ \draw[line width=1.5] (0) to (7);
+ \draw[line width=1.5] (0) to (8);
+ \draw[line width=1.5] (1) to (3);
+ \draw[line width=1.5] (1) to (4);
+ \draw[line width=1.5] (1) to (6);
+ \draw[line width=1.5] (1) to (7);
+ \draw[line width=1.5] (1) to (8);
+ \draw[line width=1.5] (2) to (4);
+ \draw[line width=1.5] (2) to (5);
+ \draw[line width=1.5] (2) to (6);
+ \draw[line width=1.5] (2) to (7);
+ \draw[line width=1.5] (2) to (8);
+ \draw[line width=1.5] (3) to (5);
+ \draw[line width=1.5] (3) to (6);
+ \draw[line width=1.5] (3) to (7);
+ \draw[line width=1.5] (4) to (5);
+ \draw[line width=1.5] (4) to (6);
+ \draw[line width=1.5] (4) to (8);
+ \draw[line width=1.5] (5) to (7);
+ \draw[line width=1.5] (5) to (8);
+ \draw[line width=1.5] (6) to (7);
+ \draw[line width=1.5] (6) to (8);
+ \draw[line width=1.5] (7) to (8);
+ \end{scope}
+ \end{tikzpicture}
+ \caption{Визуализация графа <<HQy~vnn>>, $i(G) = 2, fg(G) = 3$}
+\end{figure}
+
+\begin{figure}[h]
+ \centering
+ \begin{tikzpicture}[scale=4]
+ \draw
+ (1.0, 0.0) node[line width=1.5, draw=black, circle] (0){0}
+ (0.766, 0.643) node[line width=1.5, draw=black, circle] (1){1}
+ (0.174, 0.985) node[line width=1.5, draw=black, circle] (2){2}
+ (-0.5, 0.866) node[line width=1.5, draw=black, circle] (3){3}
+ (-0.94, 0.342) node[line width=1.5, draw=black, circle] (4){4}
+ (-0.94, -0.342) node[line width=1.5, draw=black, circle] (5){5}
+ (-0.5, -0.866) node[line width=1.5, draw=black, circle] (6){6}
+ (0.174, -0.985) node[line width=1.5, draw=black, circle] (7){7}
+ (0.766, -0.643) node[line width=1.5, draw=black, circle] (8){8};
+ \begin{scope}[-]
+ \draw[line width=1.5] (0) to (2);
+ \draw[line width=1.5] (0) to (4);
+ \draw[line width=1.5] (0) to (6);
+ \draw[line width=1.5] (0) to (7);
+ \draw[line width=1.5] (0) to (8);
+ \draw[line width=1.5] (1) to (3);
+ \draw[line width=1.5] (1) to (5);
+ \draw[line width=1.5] (1) to (7);
+ \draw[line width=1.5] (1) to (8);
+ \draw[line width=1.5] (2) to (4);
+ \draw[line width=1.5] (2) to (6);
+ \draw[line width=1.5] (2) to (7);
+ \draw[line width=1.5] (2) to (8);
+ \draw[line width=1.5] (3) to (5);
+ \draw[line width=1.5] (3) to (7);
+ \draw[line width=1.5] (4) to (6);
+ \draw[line width=1.5] (5) to (8);
+ \draw[line width=1.5] (7) to (8);
+ \end{scope}
+ \end{tikzpicture}
+ \caption{Визуализация графа <<HQhTVbd>>, $i(G) = 2, fg(G) = 2$}
+\end{figure}
+
+\begin{figure}[h]
+ \centering
+ \begin{tikzpicture}[scale=4]
+ \draw
+ (1.0, 0.0) node[line width=1.5, draw=black, circle] (0){0}
+ (0.766, 0.643) node[line width=1.5, draw=black, circle] (1){1}
+ (0.174, 0.985) node[line width=1.5, draw=black, circle] (2){2}
+ (-0.5, 0.866) node[line width=1.5, draw=black, circle] (3){3}
+ (-0.94, 0.342) node[line width=1.5, draw=black, circle] (4){4}
+ (-0.94, -0.342) node[line width=1.5, draw=black, circle] (5){5}
+ (-0.5, -0.866) node[line width=1.5, draw=black, circle] (6){6}
+ (0.174, -0.985) node[line width=1.5, draw=black, circle] (7){7}
+ (0.766, -0.643) node[line width=1.5, draw=black, circle] (8){8};
+ \begin{scope}[-]
+ \draw[line width=1.5] (0) to (6);
+ \draw[line width=1.5] (0) to (7);
+ \draw[line width=1.5] (0) to (8);
+ \draw[line width=1.5] (1) to (7);
+ \draw[line width=1.5] (1) to (8);
+ \draw[line width=1.5] (2) to (7);
+ \draw[line width=1.5] (2) to (8);
+ \draw[line width=1.5] (3) to (7);
+ \draw[line width=1.5] (3) to (8);
+ \draw[line width=1.5] (4) to (7);
+ \draw[line width=1.5] (4) to (8);
+ \draw[line width=1.5] (5) to (7);
+ \draw[line width=1.5] (5) to (8);
+ \draw[line width=1.5] (6) to (8);
+ \draw[line width=1.5] (7) to (8);
+ \end{scope}
+ \end{tikzpicture}
+ \caption{Визуализация графа <<H??CFz~>>, $i(G) = 6, fg(G) = 1$}
+\end{figure}
+
+\begin{figure}[h]
+ \centering
+ \begin{tikzpicture}[scale=4]
+ \draw
+ (1.0, 0.0) node[line width=1.5, draw=black, circle] (0){0}
+ (0.809, 0.588) node[line width=1.5, draw=black, circle] (1){1}
+ (0.309, 0.951) node[line width=1.5, draw=black, circle] (2){2}
+ (-0.309, 0.951) node[line width=1.5, draw=black, circle] (3){3}
+ (-0.809, 0.588) node[line width=1.5, draw=black, circle] (4){4}
+ (-1.0, -0.0) node[line width=1.5, draw=black, circle] (5){5}
+ (-0.809, -0.588) node[line width=1.5, draw=black, circle] (6){6}
+ (-0.309, -0.951) node[line width=1.5, draw=black, circle] (7){7}
+ (0.309, -0.951) node[line width=1.5, draw=black, circle] (8){8}
+ (0.809, -0.588) node[line width=1.5, draw=black, circle] (9){9};
+ \begin{scope}[-]
+ \end{scope}
+ \end{tikzpicture}
+ \caption{Визуализация графа <<I????????>>, $i(G) = 10, fg(G) = 0$}
+\end{figure}
+
+\begin{figure}[h]
+ \centering
+ \begin{tikzpicture}[scale=4]
+ \draw
+ (1.0, 0.0) node[line width=1.5, draw=black, circle] (0){0}
+ (0.809, 0.588) node[line width=1.5, draw=black, circle] (1){1}
+ (0.309, 0.951) node[line width=1.5, draw=black, circle] (2){2}
+ (-0.309, 0.951) node[line width=1.5, draw=black, circle] (3){3}
+ (-0.809, 0.588) node[line width=1.5, draw=black, circle] (4){4}
+ (-1.0, -0.0) node[line width=1.5, draw=black, circle] (5){5}
+ (-0.809, -0.588) node[line width=1.5, draw=black, circle] (6){6}
+ (-0.309, -0.951) node[line width=1.5, draw=black, circle] (7){7}
+ (0.309, -0.951) node[line width=1.5, draw=black, circle] (8){8}
+ (0.809, -0.588) node[line width=1.5, draw=black, circle] (9){9};
+ \begin{scope}[-]
+ \draw[line width=1.5] (0) to (5);
+ \draw[line width=1.5] (0) to (6);
+ \draw[line width=1.5] (0) to (7);
+ \draw[line width=1.5] (1) to (5);
+ \draw[line width=1.5] (1) to (8);
+ \draw[line width=1.5] (2) to (6);
+ \draw[line width=1.5] (2) to (7);
+ \draw[line width=1.5] (2) to (8);
+ \draw[line width=1.5] (3) to (8);
+ \draw[line width=1.5] (5) to (7);
+ \draw[line width=1.5] (5) to (9);
+ \draw[line width=1.5] (6) to (9);
+ \draw[line width=1.5] (7) to (9);
+ \draw[line width=1.5] (8) to (9);
+ \end{scope}
+ \end{tikzpicture}
+ \caption{Визуализация графа <<I?BDDHo@w>>, $i(G) = 4, fg(G) = 0$}
+\end{figure}
+
+\begin{figure}[h]
+ \centering
+ \begin{tikzpicture}[scale=4]
+ \draw
+ (1.0, 0.0) node[line width=1.5, draw=black, circle] (0){0}
+ (0.809, 0.588) node[line width=1.5, draw=black, circle] (1){1}
+ (0.309, 0.951) node[line width=1.5, draw=black, circle] (2){2}
+ (-0.309, 0.951) node[line width=1.5, draw=black, circle] (3){3}
+ (-0.809, 0.588) node[line width=1.5, draw=black, circle] (4){4}
+ (-1.0, -0.0) node[line width=1.5, draw=black, circle] (5){5}
+ (-0.809, -0.588) node[line width=1.5, draw=black, circle] (6){6}
+ (-0.309, -0.951) node[line width=1.5, draw=black, circle] (7){7}
+ (0.309, -0.951) node[line width=1.5, draw=black, circle] (8){8}
+ (0.809, -0.588) node[line width=1.5, draw=black, circle] (9){9};
+ \begin{scope}[-]
+ \draw[line width=1.5] (0) to (5);
+ \draw[line width=1.5] (0) to (7);
+ \draw[line width=1.5] (0) to (8);
+ \draw[line width=1.5] (1) to (5);
+ \draw[line width=1.5] (1) to (8);
+ \draw[line width=1.5] (2) to (6);
+ \draw[line width=1.5] (3) to (6);
+ \draw[line width=1.5] (4) to (7);
+ \draw[line width=1.5] (4) to (8);
+ \draw[line width=1.5] (5) to (7);
+ \draw[line width=1.5] (5) to (9);
+ \draw[line width=1.5] (6) to (9);
+ \draw[line width=1.5] (7) to (9);
+ \draw[line width=1.5] (8) to (9);
+ \end{scope}
+ \end{tikzpicture}
+ \caption{Визуализация графа <<I?B@cZG@w>>, $i(G) = 4, fg(G) = 1$}
+\end{figure}
+
+\begin{figure}[h]
+ \centering
+ \begin{tikzpicture}[scale=4]
+ \draw
+ (1.0, 0.0) node[line width=1.5, draw=black, circle] (0){0}
+ (0.809, 0.588) node[line width=1.5, draw=black, circle] (1){1}
+ (0.309, 0.951) node[line width=1.5, draw=black, circle] (2){2}
+ (-0.309, 0.951) node[line width=1.5, draw=black, circle] (3){3}
+ (-0.809, 0.588) node[line width=1.5, draw=black, circle] (4){4}
+ (-1.0, -0.0) node[line width=1.5, draw=black, circle] (5){5}
+ (-0.809, -0.588) node[line width=1.5, draw=black, circle] (6){6}
+ (-0.309, -0.951) node[line width=1.5, draw=black, circle] (7){7}
+ (0.309, -0.951) node[line width=1.5, draw=black, circle] (8){8}
+ (0.809, -0.588) node[line width=1.5, draw=black, circle] (9){9};
+ \begin{scope}[-]
+ \draw[line width=1.5] (0) to (3);
+ \draw[line width=1.5] (0) to (6);
+ \draw[line width=1.5] (0) to (7);
+ \draw[line width=1.5] (0) to (8);
+ \draw[line width=1.5] (1) to (4);
+ \draw[line width=1.5] (1) to (5);
+ \draw[line width=1.5] (1) to (6);
+ \draw[line width=1.5] (1) to (7);
+ \draw[line width=1.5] (2) to (4);
+ \draw[line width=1.5] (2) to (5);
+ \draw[line width=1.5] (2) to (7);
+ \draw[line width=1.5] (2) to (8);
+ \draw[line width=1.5] (3) to (6);
+ \draw[line width=1.5] (3) to (8);
+ \draw[line width=1.5] (4) to (5);
+ \draw[line width=1.5] (4) to (7);
+ \draw[line width=1.5] (4) to (9);
+ \draw[line width=1.5] (5) to (9);
+ \draw[line width=1.5] (6) to (8);
+ \draw[line width=1.5] (6) to (9);
+ \draw[line width=1.5] (7) to (9);
+ \draw[line width=1.5] (8) to (9);
+ \end{scope}
+ \end{tikzpicture}
+ \caption{Визуализация графа <<ICXmfQqBw>>, $i(G) = 2, fg(G) = 1$}
+\end{figure}
+
+\begin{figure}[h]
+ \centering
+ \begin{tikzpicture}[scale=4]
+ \draw
+ (1.0, 0.0) node[line width=1.5, draw=black, circle] (0){0}
+ (0.809, 0.588) node[line width=1.5, draw=black, circle] (1){1}
+ (0.309, 0.951) node[line width=1.5, draw=black, circle] (2){2}
+ (-0.309, 0.951) node[line width=1.5, draw=black, circle] (3){3}
+ (-0.809, 0.588) node[line width=1.5, draw=black, circle] (4){4}
+ (-1.0, -0.0) node[line width=1.5, draw=black, circle] (5){5}
+ (-0.809, -0.588) node[line width=1.5, draw=black, circle] (6){6}
+ (-0.309, -0.951) node[line width=1.5, draw=black, circle] (7){7}
+ (0.309, -0.951) node[line width=1.5, draw=black, circle] (8){8}
+ (0.809, -0.588) node[line width=1.5, draw=black, circle] (9){9};
+ \begin{scope}[-]
+ \draw[line width=1.5] (0) to (5);
+ \draw[line width=1.5] (0) to (8);
+ \draw[line width=1.5] (1) to (6);
+ \draw[line width=1.5] (1) to (8);
+ \draw[line width=1.5] (1) to (9);
+ \draw[line width=1.5] (2) to (7);
+ \draw[line width=1.5] (2) to (9);
+ \draw[line width=1.5] (3) to (8);
+ \draw[line width=1.5] (4) to (9);
+ \draw[line width=1.5] (5) to (9);
+ \end{scope}
+ \end{tikzpicture}
+ \caption{Визуализация графа <<I?AA@BOZ?>>, $i(G) = 5, fg(G) = 1$}
+\end{figure}
+
+\begin{figure}[h]
+ \centering
+ \begin{tikzpicture}[scale=4]
+ \draw
+ (1.0, 0.0) node[line width=1.5, draw=black, circle] (0){0}
+ (0.809, 0.588) node[line width=1.5, draw=black, circle] (1){1}
+ (0.309, 0.951) node[line width=1.5, draw=black, circle] (2){2}
+ (-0.309, 0.951) node[line width=1.5, draw=black, circle] (3){3}
+ (-0.809, 0.588) node[line width=1.5, draw=black, circle] (4){4}
+ (-1.0, -0.0) node[line width=1.5, draw=black, circle] (5){5}
+ (-0.809, -0.588) node[line width=1.5, draw=black, circle] (6){6}
+ (-0.309, -0.951) node[line width=1.5, draw=black, circle] (7){7}
+ (0.309, -0.951) node[line width=1.5, draw=black, circle] (8){8}
+ (0.809, -0.588) node[line width=1.5, draw=black, circle] (9){9};
+ \begin{scope}[-]
+ \draw[line width=1.5] (0) to (5);
+ \draw[line width=1.5] (0) to (7);
+ \draw[line width=1.5] (0) to (9);
+ \draw[line width=1.5] (1) to (6);
+ \draw[line width=1.5] (1) to (7);
+ \draw[line width=1.5] (1) to (8);
+ \draw[line width=1.5] (1) to (9);
+ \draw[line width=1.5] (2) to (6);
+ \draw[line width=1.5] (2) to (8);
+ \draw[line width=1.5] (2) to (9);
+ \draw[line width=1.5] (3) to (7);
+ \draw[line width=1.5] (3) to (9);
+ \draw[line width=1.5] (4) to (8);
+ \draw[line width=1.5] (4) to (9);
+ \draw[line width=1.5] (5) to (8);
+ \draw[line width=1.5] (5) to (9);
+ \draw[line width=1.5] (6) to (7);
+ \draw[line width=1.5] (6) to (9);
+ \draw[line width=1.5] (7) to (8);
+ \draw[line width=1.5] (8) to (9);
+ \end{scope}
+ \end{tikzpicture}
+ \caption{Визуализация графа <<I?ABEdl~g>>, $i(G) = 5, fg(G) = 4$}
+\end{figure}
+
+\begin{figure}[h]
+ \centering
+ \begin{tikzpicture}[scale=4]
+ \draw
+ (1.0, 0.0) node[line width=1.5, draw=black, circle] (0){0}
+ (0.809, 0.588) node[line width=1.5, draw=black, circle] (1){1}
+ (0.309, 0.951) node[line width=1.5, draw=black, circle] (2){2}
+ (-0.309, 0.951) node[line width=1.5, draw=black, circle] (3){3}
+ (-0.809, 0.588) node[line width=1.5, draw=black, circle] (4){4}
+ (-1.0, -0.0) node[line width=1.5, draw=black, circle] (5){5}
+ (-0.809, -0.588) node[line width=1.5, draw=black, circle] (6){6}
+ (-0.309, -0.951) node[line width=1.5, draw=black, circle] (7){7}
+ (0.309, -0.951) node[line width=1.5, draw=black, circle] (8){8}
+ (0.809, -0.588) node[line width=1.5, draw=black, circle] (9){9};
+ \begin{scope}[-]
+ \draw[line width=1.5] (0) to (5);
+ \draw[line width=1.5] (0) to (6);
+ \draw[line width=1.5] (0) to (8);
+ \draw[line width=1.5] (1) to (5);
+ \draw[line width=1.5] (1) to (7);
+ \draw[line width=1.5] (1) to (8);
+ \draw[line width=1.5] (2) to (5);
+ \draw[line width=1.5] (2) to (7);
+ \draw[line width=1.5] (2) to (9);
+ \draw[line width=1.5] (3) to (6);
+ \draw[line width=1.5] (3) to (7);
+ \draw[line width=1.5] (3) to (9);
+ \draw[line width=1.5] (4) to (6);
+ \draw[line width=1.5] (4) to (8);
+ \draw[line width=1.5] (4) to (9);
+ \draw[line width=1.5] (5) to (7);
+ \draw[line width=1.5] (5) to (8);
+ \draw[line width=1.5] (6) to (8);
+ \draw[line width=1.5] (6) to (9);
+ \draw[line width=1.5] (7) to (9);
+ \end{scope}
+ \end{tikzpicture}
+ \caption{Визуализация графа <<I?BcrjMMo>>, $i(G) = 5, fg(G) = 5$}
+\end{figure}
+
+\begin{figure}[h]
+ \centering
+ \begin{tikzpicture}[scale=4]
+ \draw
+ (1.0, 0.0) node[line width=1.5, draw=black, circle] (0){0}
+ (0.809, 0.588) node[line width=1.5, draw=black, circle] (1){1}
+ (0.309, 0.951) node[line width=1.5, draw=black, circle] (2){2}
+ (-0.309, 0.951) node[line width=1.5, draw=black, circle] (3){3}
+ (-0.809, 0.588) node[line width=1.5, draw=black, circle] (4){4}
+ (-1.0, -0.0) node[line width=1.5, draw=black, circle] (5){5}
+ (-0.809, -0.588) node[line width=1.5, draw=black, circle] (6){6}
+ (-0.309, -0.951) node[line width=1.5, draw=black, circle] (7){7}
+ (0.309, -0.951) node[line width=1.5, draw=black, circle] (8){8}
+ (0.809, -0.588) node[line width=1.5, draw=black, circle] (9){9};
+ \begin{scope}[-]
+ \draw[line width=1.5] (0) to (7);
+ \draw[line width=1.5] (0) to (8);
+ \draw[line width=1.5] (0) to (9);
+ \draw[line width=1.5] (1) to (7);
+ \draw[line width=1.5] (1) to (8);
+ \draw[line width=1.5] (1) to (9);
+ \draw[line width=1.5] (2) to (9);
+ \draw[line width=1.5] (3) to (9);
+ \draw[line width=1.5] (4) to (9);
+ \draw[line width=1.5] (5) to (9);
+ \draw[line width=1.5] (6) to (9);
+ \draw[line width=1.5] (7) to (9);
+ \draw[line width=1.5] (8) to (9);
+ \end{scope}
+ \end{tikzpicture}
+ \caption{Визуализация графа <<I???EB?~w>>, $i(G) = 7, fg(G) = 2$}
+\end{figure}
+
+\begin{figure}[h]
+ \centering
+ \begin{tikzpicture}[scale=4]
+ \draw
+ (1.0, 0.0) node[line width=1.5, draw=black, circle] (0){0}
+ (0.809, 0.588) node[line width=1.5, draw=black, circle] (1){1}
+ (0.309, 0.951) node[line width=1.5, draw=black, circle] (2){2}
+ (-0.309, 0.951) node[line width=1.5, draw=black, circle] (3){3}
+ (-0.809, 0.588) node[line width=1.5, draw=black, circle] (4){4}
+ (-1.0, -0.0) node[line width=1.5, draw=black, circle] (5){5}
+ (-0.809, -0.588) node[line width=1.5, draw=black, circle] (6){6}
+ (-0.309, -0.951) node[line width=1.5, draw=black, circle] (7){7}
+ (0.309, -0.951) node[line width=1.5, draw=black, circle] (8){8}
+ (0.809, -0.588) node[line width=1.5, draw=black, circle] (9){9};
+ \begin{scope}[-]
+ \draw[line width=1.5] (0) to (6);
+ \draw[line width=1.5] (0) to (8);
+ \draw[line width=1.5] (1) to (7);
+ \draw[line width=1.5] (1) to (8);
+ \draw[line width=1.5] (2) to (8);
+ \draw[line width=1.5] (2) to (9);
+ \draw[line width=1.5] (3) to (8);
+ \draw[line width=1.5] (3) to (9);
+ \draw[line width=1.5] (4) to (8);
+ \draw[line width=1.5] (4) to (9);
+ \draw[line width=1.5] (5) to (8);
+ \draw[line width=1.5] (5) to (9);
+ \draw[line width=1.5] (6) to (9);
+ \draw[line width=1.5] (7) to (9);
+ \draw[line width=1.5] (8) to (9);
+ \end{scope}
+ \end{tikzpicture}
+ \caption{Визуализация графа <<I??CAB\{Nw>>, $i(G) = 6, fg(G) = 2$}
+\end{figure}
+
+\begin{figure}[h]
+ \centering
+ \begin{tikzpicture}[scale=4]
+ \draw
+ (1.0, 0.0) node[line width=1.5, draw=black, circle] (0){0}
+ (0.809, 0.588) node[line width=1.5, draw=black, circle] (1){1}
+ (0.309, 0.951) node[line width=1.5, draw=black, circle] (2){2}
+ (-0.309, 0.951) node[line width=1.5, draw=black, circle] (3){3}
+ (-0.809, 0.588) node[line width=1.5, draw=black, circle] (4){4}
+ (-1.0, -0.0) node[line width=1.5, draw=black, circle] (5){5}
+ (-0.809, -0.588) node[line width=1.5, draw=black, circle] (6){6}
+ (-0.309, -0.951) node[line width=1.5, draw=black, circle] (7){7}
+ (0.309, -0.951) node[line width=1.5, draw=black, circle] (8){8}
+ (0.809, -0.588) node[line width=1.5, draw=black, circle] (9){9};
+ \begin{scope}[-]
+ \draw[line width=1.5] (0) to (3);
+ \draw[line width=1.5] (0) to (4);
+ \draw[line width=1.5] (0) to (6);
+ \draw[line width=1.5] (0) to (7);
+ \draw[line width=1.5] (1) to (3);
+ \draw[line width=1.5] (1) to (5);
+ \draw[line width=1.5] (1) to (6);
+ \draw[line width=1.5] (1) to (8);
+ \draw[line width=1.5] (2) to (4);
+ \draw[line width=1.5] (2) to (5);
+ \draw[line width=1.5] (2) to (7);
+ \draw[line width=1.5] (2) to (8);
+ \draw[line width=1.5] (3) to (5);
+ \draw[line width=1.5] (3) to (7);
+ \draw[line width=1.5] (3) to (8);
+ \draw[line width=1.5] (3) to (9);
+ \draw[line width=1.5] (4) to (6);
+ \draw[line width=1.5] (4) to (7);
+ \draw[line width=1.5] (4) to (8);
+ \draw[line width=1.5] (4) to (9);
+ \draw[line width=1.5] (5) to (7);
+ \draw[line width=1.5] (5) to (9);
+ \draw[line width=1.5] (6) to (8);
+ \draw[line width=1.5] (6) to (9);
+ \draw[line width=1.5] (7) to (9);
+ \draw[line width=1.5] (8) to (9);
+ \end{scope}
+ \end{tikzpicture}
+ \caption{Визуализация графа <<IEhuTxyFw>>, $i(G) = 2, fg(G) = 3$}
+\end{figure}
+
+\conclusion
+
+В данной работе были рассмотрены и проанализированы такие понятия теории графов,
+как число независимого доминирования и принудительное геодезическое число.
+
+В результате выполнения этой работы было разработано программное обеспечение,
+позволяющее произвести вычисление этих параметров графов. При разработке этой
+программы, было уделено внимание эффективному перебору неизоморфных графов с
+помощью библиотеки nauty, а в последствии параллельному вычислению указанных
+параметров.
+
+Помимо этого, был разработан инструментарий для работы с графами на языке
+программирования Rust. Этот инструментарий может быть использован для
+дальнейших исследований в области анализа графов.
+
+На основе выполненного вычислительного эксперимента были предложены две
+гипотезы, которые также могут быть полезными в дальнейших исследованиях в
+областях доминирования и геодоминирования в графах.
+
+
+\begin{thebibliography}{10}
+ \bibitem{pds1}
+ Livingston, M. Perfect dominating sets / M. Livingston, Q.F. Stout // Congressus
+ Numerantium. -- 1990. -- Vol. 79. -- P. 187-203.
+ \bibitem{pds2}
+ Bauer, D. Domination alteration sets in graphs / D. Bauer,
+ F. Harary, J. Nieminen, C. L. Suffel // Discrete Mathematics. --
+ 1983. -- Vol. 47. -- P. 153-161.
+ \bibitem{TONG20091159}
+ Tong, L. The forcing hull and forcing geodetic numbers of graphs / L. Tong // Discrete Applied Mathematics. --- 2009. --- Vol. 157, no. 7 --- Pp. 1159 -- 1163.
+ \bibitem{GODDARD2013839}
+ Goddard, W. Independent domination in graphs: A survey and recent results / W. Goddard, M. A. Hennig // Discrete Mathematics. --- 2013. --- Vol. 313, no. 7 --- Pp. 839 -- 854.
+ \bibitem{mckay2014practical}
+ McKay, B. D. Practical graph isomorphism, II / B. D. McKay, A. Piperno // Journal of symbolic computation --- 2014. --- Vol. 60. --- Pp. 94 -- 112
+ \bibitem{graph6}
+ Description of graph6, sparse6 and digraph6 encodings [{Э}лектронный ресурс]. --- URL: URL:~\url{http://users.cecs.anu.edu.au/~bdm/data/formats.txt} (Дата обращения 25.10.2024). Загл. с экр. Яз. англ.
+\end{thebibliography}
+
+\appendix
+
+\section{Исходный код программы подсчёта графов на языке Rust, файл main.rs}
+\label{app:rust1}
+\VerbatimInput{../graph-checker/src/main.rs}
+
+\section{Исходный код программы подсчёта графов на языке Rust, файл graph.rs}
+\label{app:rust2}
+\VerbatimInput{../graph-checker/src/graph.rs}
+
+\section{Исходный код программы подсчёта графов на языке Rust, файл geng.rs}
+\label{app:rust3}
+\VerbatimInput{../graph-checker/src/geng.rs}
+
+\section{Исходный код программы подсчёта графов на языке Rust, файл compute.rs}
+\label{app:rust4}
+\VerbatimInput{../graph-checker/src/compute.rs}
+
+\section{Исходный код программы подсчёта графов на языке Rust, файл build.rs}
+\label{app:rust5}
+\VerbatimInput{../graph-checker/build.rs}
+
+\section{Исходный код программы подсчёта графов на языке Rust, файл geng-iter.c}
+\label{app:geng_iter}
+\VerbatimInput{../graph-checker/nauty/geng-iter.c}
+
+\section{Исходный код программы генерации таблиц на языке Rust}
+\label{app:tables}
+\VerbatimInput{../tables/src/main.rs}
+
+\section{Исходный код программы визуализации графов на языке Python}
+\label{app:drawer}
+\VerbatimInput{../drawer/src/drawer/__init__.py}
+
+\end{document}
|