From 9e30b5950eaad2ef8e5cce251e166a71b13cf336 Mon Sep 17 00:00:00 2001
From: Andrew Guschin <guschin@altlinux.org>
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

