From 5a4e4956ebf0b3d6d72f951c69103fa4167ccf5e Mon Sep 17 00:00:00 2001 From: Andrew Guschin Date: Sun, 25 Dec 2022 14:47:03 +0400 Subject: =?UTF-8?q?=D0=94=D0=BE=D0=B1=D0=B0=D0=B2=D0=BB=D0=B5=D0=BD=D0=BE?= =?UTF-8?q?=20=D0=B2=D0=B2=D0=B5=D0=B4=D0=B5=D0=BD=D0=B8=D0=B5?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- graphs-exam/graphs-exam.pdf | Bin 228250 -> 258349 bytes graphs-exam/graphs-exam.tex | 135 ++++++++++++++++++++++++++++++++++++++++++++ graphs-exam/style.tex | 4 +- 3 files changed, 137 insertions(+), 2 deletions(-) (limited to 'graphs-exam') diff --git a/graphs-exam/graphs-exam.pdf b/graphs-exam/graphs-exam.pdf index 7a83a60..f9c210a 100644 Binary files a/graphs-exam/graphs-exam.pdf and b/graphs-exam/graphs-exam.pdf differ 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{Основные алгебраические конструкции для графов} diff --git a/graphs-exam/style.tex b/graphs-exam/style.tex index cd109fd..cb21fbf 100644 --- a/graphs-exam/style.tex +++ b/graphs-exam/style.tex @@ -21,10 +21,10 @@ \declaretheoremstyle[ headfont=\sffamily\bfseries,% notefont=\sffamily\bfseries,% - notebraces={}{},% + notebraces={(}{)},% headpunct=,% bodyfont=\sffamily\itshape,% - headformat=\color{definitioncolor}\NAME~\NUMBER\hfill\NOTE\smallskip\linebreak,% + headformat=\color{definitioncolor}\NAME~\NUMBER~\NOTE\hfill\smallskip\linebreak,% preheadhook=\begin{definitionbar},% postfoothook=\end{definitionbar},% ]{customDefinition} -- cgit v1.2.3