Solved ex 3 and 4 and party ex1 from dstr hw2

2 files changed, 90 insertions, 0 deletions

diff --git a/Year 1/Discrete math/Homeworks/Homework2.pdf b/Year 1/Discrete math/Homeworks/Homework2.pdf
new file mode 100644
index 0000000..99d3cf9
--- /dev/null
+++ b/Year 1/Discrete math/Homeworks/Homework2.pdf
diff --git a/Year 1/Discrete math/Homeworks/Homework2.tex b/Year 1/Discrete math/Homeworks/Homework2.tex
new file mode 100644
index 0000000..4eaaf7e
--- /dev/null
+++ b/Year 1/Discrete math/Homeworks/Homework2.tex
@@ -0,0 +1,90 @@
+% Document MUST be built with XeLaTeX!
+\documentclass[11pt,a4paper]{article}
+
+\usepackage[margin=1.5cm]{geometry}
+
+% Поддръжка на български език
+% Thanks to https://tex.stackexchange.com/a/136926
+\usepackage{fontspec}
+\defaultfontfeatures{Ligatures=TeX}
+\setmainfont{CMU Serif}
+\setsansfont{CMU Sans Serif}
+
+\usepackage[bulgarian,english]{babel}
+
+\usepackage{amsmath}            % Математически символи
+\usepackage{extarrows}
+\usepackage{amsfonts}           % Още математически символи
+\usepackage{cancel}             % Зачертаване
+\usepackage[dvipsnames]{xcolor} % Цветни кутийки + допълнителни цветове
+\newcommand{\answerbox}[1]{\colorbox{yellow}{$\displaystyle #1$}}
+
+\usepackage{enumitem}
+\setlist[enumerate]{label=\arabic*.}
+
+\usepackage[pdfauthor={Камен Димитров Младенов, КН Зимен семестър, 2021},
+		    pdftitle={Домашна работа 2 по ДСТР.},
+		    pdfsubject={},
+		    pdfkeywords={},
+		    colorlinks=true,
+		    urlcolor=blue]{hyperref}
+
+\title{\vspace{-1.5cm}Домашно №2 по Дискретни Структури на специалност Компютърни
+науки, 2 поток, зимен семестър 2021/2022г.}
+\author{Камен Димитров Младенов, Група 6}
+\date{06 Януари 2022}
+
+\begin{document}
+
+\maketitle
+
+\paragraph{\colorbox{yellow}{Задача 1} Решение:} Ще докажем равенството по индукция за $n$:
+\begin{align*}
+	& \textbf{База: } n = 1, \quad S(1) = \sum_{X \subseteq \{ 1 \}} \prod_{y \in X} y = \prod_{y \in \emptyset} y + \prod_{y \in {1}} y = 1 + 1 = 2 \quad (1+1)! = 2! = 2 \\
+	& \textbf{Индукционно предположение: } S(n) = (n+1)! \text{ е изпълнено за поне едно } n \in \mathbb{N}^+ \\
+	& \textbf{Индукционна стъпка: } S(n+1) = \sum_{X \subseteq \{ 1, ..., n+1 \}} \prod_{y \in X} y = \sum_{X \subseteq \{ 1, ..., n \}} \prod_{y \in X} y + (n+1) \prod_{y \in \{1, ..., n+1\}} y \xlongequal{\text{ИП}} \\
+	& \qquad \xlongequal{\text{ИП}} (n+1)! + (n+1) \prod_{y \in \{1, ..., n+1\}} y = (n+1)! + (n+1) \cdot 1 \cdot ... \cdot (n+1) = (n+1)! + (n+1)(n+1)! = \\
+	& \qquad = (n+1)!(n+1+1) = (n+2)!
+\end{align*}
+
+\paragraph{\colorbox{yellow}{Задача 2} Решение:} [TODO]
+
+\paragraph{\colorbox{yellow}{Задача 3} Решение:} Б.О.О. $G$ е свързан граф (иначе, разглеждаме всяка свързана компонента като отделен граф).
+
+\textbf{I.} $X \subseteq V$ е антиклика $\implies$ $V \setminus X$ е покриване
+
+$X$ е антиклика $\implies \forall x_1, x_2 \in X, x_1 \neq x_2 : (x_1, x_2) \notin E$.
+
+Нека $W = \{ v \in V : \exists x \in X, (v, x) \in E \}$. Понеже $X$ е антиклика, то $\forall v \in W : v \in V \setminus X$.
+
+Следователно $V \setminus X$ е покриване.
+
+\hfill
+
+\textbf{II.} $V \setminus X$ е покриване $\implies$ $X \subseteq V$ е антиклика
+
+$V \setminus X$ е покриване $\implies \forall (u, v)\in E : u \in V \setminus X \lor v \in V \setminus X$.
+
+Ако за произволни $x_1, x_2 \in X$ съществува $(x_1, x_2) \in E$, то $x_1, x_2 \notin V \setminus X \equiv x_1 \notin V \setminus X \land x_2 \notin V \setminus X$.
+
+Обаче по предположение, трябва $x_1 \in V \setminus X \lor x_2 \in V \setminus X$, противоречие!
+
+Следователно, $X$ е антиклика.
+
+
+\paragraph{\colorbox{yellow}{Задача 4} Решение:} Допускаме противното, тоест че съществува мост и всички върхове са от четна степен. Б.О.О. нека този мост да бъде $e \in E(G)$ с краища $m_1, m_2 \in V(G)$ и нека компонентите на $G - e$ да са $C_1$ и $C_2$.
+
+Понеже в $G$ степените на $m_1$ и $m_2$ са четни, то в $G - e$ те ще са нечетни. 
+
+Разглеждаме $C_1$ като самостоятелен граф. Сумата на степените ще бъде нечетно число (заради единствената нечетна степен на $m_1$), което противоречи на лемата "За всеки граф $G, \; \sum_{u \in V(G)} d(u) = 2m$". По конструкция $d(m_1)$ е нечетно, то тогава $\exists v_1 \in V(C_1), v_1 \neq m_1 : d(v_1)$ е нечетно.
+
+Аналогично за $C_2$, $\exists v_2 \in V(C_2), v_2 \neq m_2 : d(v_2)$ е нечетно.
+
+Стигаме до противоречие:
+\begin{itemize}
+	\item Ако реброто $(v_1, v_2) \notin V(G)$, то тогава имаме върхове от нечетна степен в $G$.
+
+	\item Ако реброто $(v_1, v_2) \in V(G)$, то тогава то ще е ребро между компонентите $C_1$ и $C_2$ и $e$ няма да бъде мост.
+\end{itemize}
+
+\end{document}
\ No newline at end of file