\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}