From dcfac8227b2628c7e2c1e06a551300a6403f2b79 Mon Sep 17 00:00:00 2001 From: Andrew Guschin Date: Tue, 29 Oct 2024 18:51:55 +0400 Subject: wip(nir): report --- nir/nir.tex | 1431 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1431 insertions(+) create mode 100644 nir/nir.tex (limited to 'nir/nir.tex') 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{Визуализация графа <>} + \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{Визуализация графа <>} + \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{Визуализация графа <>, $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{Визуализация графа <>, $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{Визуализация графа <>, $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{Визуализация графа <>, $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{Визуализация графа <>, $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{Визуализация графа <>, $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{Визуализация графа <>, $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{Визуализация графа <>, $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{Визуализация графа <>, $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{Визуализация графа <>, $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{Визуализация графа <>, $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{Визуализация графа <>, $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{Визуализация графа <>, $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{Визуализация графа <>, $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(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(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(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{Визуализация графа <>, $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(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(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(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(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(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{Визуализация графа <>, $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} -- cgit v1.2.3