1 files changed, 135 insertions, 0 deletions
diff --git a/graphs-exam/graphs-exam.tex b/graphs-exam/graphs-exam.tex
index 1b59218..f7a137e 100644
--- a/graphs-exam/graphs-exam.tex
+++ b/graphs-exam/graphs-exam.tex
@@ -16,6 +16,7 @@
 \renewcommand{\emptyset}{\varnothing}
 \renewcommand{\qedsymbol}{$\blacksquare$}
 \newcommand{\link}{\hyperref}
+\newcommand{\ds}{\displaystyle}
 
 \input{style.tex}
 
@@ -51,6 +52,140 @@
   \label{def:universal-set}
 \end{definition}
 
+\begin{definition}[Операции над отношениями]
+  Пусть $\rho, \sigma \subseteq A \times B$.
+  \begin{enumerate}
+    \item
+      Пересечение: $\rho \cap \sigma = \set{(a, b) \in A \times B : (a, b) \in
+      \rho \land (a, b) \in \sigma}$
+    \item
+      Объединение: $\rho \cap \sigma = \set{(a, b) \in A \times B : (a, b) \in
+      \rho \lor (a, b) \in \sigma}$
+    \item
+      Дополнение: $\overline{\rho} = \set{(a, b) \in A \times B : (a, b) \not\in
+      \rho}$
+    \item
+      Обращение: $\rho^{-1} \subseteq B \times A,\, \rho^{-1} = \set{(b, a) \in
+      B \times A : (a, b) \in \rho}$
+    \item
+      Умножение. Пусть $\rho \subseteq A \times B,\, \sigma \subseteq B \times
+      C$. Тогда $\rho \circ \sigma \subseteq A \times C,\, \rho \circ \sigma =
+      \set{(a, c) \in A \times C : (\exists b \in B) (a, b) \in \rho \land (b,
+      c) \in \sigma}$.
+  \end{enumerate}
+  \label{def:rel-op}
+\end{definition}
+
+
+\section{Операции над матрицами: пересечение, сложение, дополнение,
+транспонирование, умножение. Связь между операциями над матрицами и
+отношениями.}
+
+\begin{definition}[Операции над матрицами]
+  $M(m, n)$ --- множество всех двоичных булевых матриц размерности $m \times n$.
+  Пусть $M, N \in M(m, n)$.
+
+  \begin{enumerate}
+    \item Пересечение: $M \land N : (M \land N)_{ij} = M_{ij} \cdot N_{ij}$
+    \item Сложение: $M + N : (M + N)_{ij} = M_{ij} + N_{ij}$
+    \item Дополнение: $M' : (M')_{ij} = (M_{ij})'$
+    \item Транспонирование: $M^T \in M(n, m),\, (M^T)_{ij} = M_{ji}$
+    \item
+      Умножение $M \in M(m, n),\, N \in M(n, p)$: $MN \in M(m, p),\,
+      (MN)_{ik} = \sum_{j = 1}^n M_{ij} N_{jk}$
+  \end{enumerate}
+  \label{def:mat-op}
+\end{definition}
+
+\begin{theorem}[Связь между операциями над отношениями и их матрицами]
+  Пусть $\rho, \sigma \in A \times B (|A| = m, |B| = n)$. Тогда
+  \begin{enumerate}
+    \item $M(\rho \cap \sigma) = M(\rho) \land M(\sigma)$
+    \item $M(\rho \cup \sigma) = M(\rho) + M(\sigma)$
+    \item $M(\overline\rho) = (M(\rho))'$
+    \item $M(\rho^{-1}) = (M(\rho))^T$
+    \item
+      $\rho \subseteq A \times B,\, \sigma \subseteq B \times C : M(\rho \circ
+      \sigma) = M(\rho) M(\sigma)$
+  \end{enumerate}
+  \label{def:mat-rel-op}
+\end{theorem}
+
+
+\section{Срез отношения через элемент и через множество. Тождественное
+отношение. Классификация отношений: рефлексивность, антирефлексивность,
+симметричность, антисимметричность. Отношение эквивалентности, отношение
+порядка.}
+
+\begin{definition}
+  Срезом отношения $\rho \subseteq A \times B$ через элемент $a \in A$
+  называется множество $\rho(a) = \set{b \in B : (a, b) \in \rho} \subseteq B$.
+  \label{def:slice-elem}
+\end{definition}
+
+\begin{definition}
+  Срезом отношения $\rho \subseteq A \times B$ через подмножество $X \subseteq
+  A$ называется множество $\rho(a) = \ds\bigcup_{a \in X} \rho(a) \subseteq B$.
+  \label{def:slice-set}
+\end{definition}
+
+\begin{definition}
+  Отношения между элементами одного и того же множества называются отношениями
+  на множестве $A$. $\rho \subseteq A \times A$.
+  \label{def:self-rel}
+\end{definition}
+
+\begin{definition}
+  Тождественное отношение на множестве $A$ обозначается $\Delta \subseteq A
+  \times A$.
+  \begin{align*}
+    (x, y) \in \Delta &\iff x = y \\
+    M(\Delta) = E&,\, E = \begin{cases}
+      0, &i \neq j \\
+      1, &i = j
+    \end{cases}
+  \end{align*}
+  \label{def:identity-rel}
+\end{definition}
+
+\begin{definition}[Классификация отношений]
+  \begin{enumerate}
+    \item
+      Отношение $\rho \subseteq A \times A$ называется рефлексивным $(\forall x
+      \in A) ((x, x) \in \rho)$. В матрице отношения элементы главной диагонали
+      равны 1.
+    \item
+      Отношение $\rho \subseteq A \times A$ называется рефлексивным $(\forall
+      x \in A) ((x, x) \not\in \rho)$. В матрице отношения элементы главной
+      диагонали равны 0.
+    \item
+      Отношение $\rho \subseteq A \times A$ симметрично $\iff (\forall x, y
+      \in A) ((x, y) \in \rho \implies (y, x) \in \rho)$. Матрица отношения
+      симметрична относительно главной диагонали.
+    \item
+      Отношение $\rho \subseteq A \times A$ антисимметрично $\iff (\forall x,
+      y \in A) ((x, y) \in \rho \land (y, x) \in \rho) \implies (x = y)$. В
+      матрице отношения элементы, симметричные единицам относительно главной
+      диагонали, равны нулю (исключение --- сама главная диагональ).
+    \item
+      Отношение $\rho \subseteq A \times A$ транзитивно $\iff (\forall x, y, z
+      \in A) ((x, y) \in \rho \land (y, z) \in \rho \implies (x, z) \in \rho)$.
+  \end{enumerate}
+  \label{def:rel-classification}
+\end{definition}
+
+\begin{definition}
+  Отношением эквивалентности на $A$ называется отношение $\varepsilon \subseteq
+  A \times A$, которое одновременно рефлексивно, симметрично и транзитивно.
+  \label{def:equivalence}
+\end{definition}
+
+\begin{definition}
+  Отношение $\omega \subseteq A \times A$ называется отношением порядка, если
+  оно рефлексивно, антисимметрично и транзитивно.
+  \label{def:order}
+\end{definition}
+
 
 \chapter{Основные алгебраические конструкции для графов}