From 9e30b5950eaad2ef8e5cce251e166a71b13cf336 Mon Sep 17 00:00:00 2001 From: Andrew Guschin Date: Tue, 10 Sep 2024 16:24:57 +0400 Subject: feat: changes in report --- report/forbidden.tex | 23 +++++++---------------- 1 file changed, 7 insertions(+), 16 deletions(-) (limited to 'report/forbidden.tex') diff --git a/report/forbidden.tex b/report/forbidden.tex index 4a37ab7..0091dbb 100644 --- a/report/forbidden.tex +++ b/report/forbidden.tex @@ -1,24 +1,15 @@ \section{Достаточные условия, основанные на запрещённых подграфах} Условия, представленные в данном разделе используют широко распространённую -концепцию запрещённых подграфов. Рассмотрим определение подграфа. -\begin{definition} - Подграфов графа $G = (V, \alpha)$ называется такой граф $G^* = (V^*, - \alpha^*)$, в котором $V^* \subseteq V, \alpha^* = \alpha \cap (V^* \times - V^*)$. То есть подграф состоит из некоторых вершин графа и \textbf{всех} - рёбер, соединяющих эти вершины в графе. - \label{def:subgraph} -\end{definition} - -Произвольный граф $G$ называют свободным от подграфа $H$ в том случае, если -ни один из подграфов графа $G$ не является изоморфным графу $H$. В общем -случае проверка на запрещённость подграфа является NP-полной задачей, так как -необходимо перебрать все подграфы и проверить их на изоморфность некоторому -другому подграфу. +концепцию запрещённых подграфов. Произвольный граф $G$ называют свободным от +подграфа $H$ в том случае, если ни один из подграфов графа $G$ не является +изоморфным графу $H$. В общем случае проверка на запрещённость подграфа является +NP-полной задачей, так как необходимо перебрать все подграфы и проверить их на +изоморфность некоторому другому подграфу. -Но есть возможность улучшения сложности данных проверок для графов, +Но есть возможность улучшения сложности проверок для графов, рассмотренных в данной работе с помощью алгоритма представленного в -статье \cite{hopcroft1974linear}, в которой представлен алгоритм проверки +статье \cite{hopcroft1974linear}, в которой описан алгоритм проверки изоморфизмов на планарных графах. Графы, рассмотренные в данной работе (рис. \ref{fig:forbidden}), очевидно планарные. В случае, если планарность графов не очевидна, существует линейный алгоритм проверки на планарность, представленный -- cgit v1.2.3