1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
|
% 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
\noindent
\colorbox{YellowGreen}{\parbox{\textwidth}{\; 85/100 Точки \qquad [Коментарите са под определените места]}}
\paragraph{\colorbox{yellow}{Задача 1} Решение:} Ще докажем равенството по индукция за $n$: \hfill \colorbox{YellowGreen}{25т.}
\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 \; + \\
& + \prod_{y \in \{ n+1 \}} y + \prod_{y \in \{ 1, n+1 \}} y + \prod_{y \in \{ 2, n+1 \}} y + \cdots + \prod_{y \in \{ n, n+1 \}} y + \prod_{y \in \{ 1, 2, n+1 \}} y + \cdots + \prod_{y \in \{ 1, ..., n, n+1 \}} y = \\
& = \sum_{X \subseteq \{ 1, ..., n \}} \prod_{y \in X} y + (n+1) \left( \prod_{y \in \emptyset} y + \prod_{y \in \{ 1 \}} y + \prod_{y \in \{ 2 \}} y + \cdots + \prod_{y \in \{ n \}} y + \prod_{y \in \{ 1, 2 \}} y + \cdots + \prod_{y \in \{ 1, ..., n \}} y \right) = \\
& = \sum_{X \subseteq \{ 1, ..., n \}} \prod_{y \in X} y + (n+1)\sum_{X \subseteq \{ 1, ..., n \}} \prod_{y \in X} y \xlongequal{\text{ИП}} (n+1)! + (n+1)(n+1)! = (n+1)!(n+1+1) = (n+2)!
\end{align*}
\paragraph{\colorbox{yellow}{Задача 2} Решение:} Първо ще докажем с индукция по $n \in \mathbb{N}^+$, че за произволно попълване на квадратна таблица с размер $n$, броят на колоните с нечетна сума и броят на редовете с нечетна сума съвпадат по модул 2.
\textbf{База: } $n = 1$, \quad Имаме една колона и един ред, които съвпадат по стойност. Ако редът е нечетен, то и колоната ще е нечетна и обратно.
\textbf{Индукционно предположение: } Допускаме, че е изпълнено за поне едно $n$
\textbf{Индукционна стъпка: } Разглеждаме таблица $A$ с размер $n+1$. Разделяме я на таблица $B$ с размер $n$ и ред $r'$ и колона $c'$ с размери $n+1$ (имат една обща клетка). Твърдението е вярно за $B$ (от ИП) и за $r'$ и $c'$, когато имат еднаква четност.
Разглеждаме когато $r'$ и $c'$ имат различна четност. Б.О.О. нека колоните и редовете с нечетна сума в $B$ са нечетен брой, $r'$ е с четна сума и $c'$ е с нечетна сума. То тогава, четен брой колони от $B$ ще станат нечетни и броят на колоните ще е: нечетно - четно = нечетно. Аналогично, бройката редове също си остава нечетна. Следователно, взаимната нечетност се запазва.
\noindent
\colorbox{RedOrange}{\parbox{\textwidth}{Не е съвсем така. Тук $r'$ и $c'$ се припокриват в долния десен ъгъл. Има значение дали там стои 0 или 1, понеже от това също зависи колко редовете и колоните на $B$ ще си променят четността.}}
\hfill
Можем да представим всяка хубава $n$-мерна квадратна таблица като $(n-1)$-мерна квадратна таблица с произволни стойности, към която са добавени ред и колона с размер $n$, чиито стойности допълват редовете и колоните до "хубавост" (за ред с нечетна сума, слагаме 1-ца и т.н.).
Знаем, че при произволно попълване, броят на колоните и редовете с нечетни суми съвпада по четност. То тогава, добавените ред и колона към $(n-1)$-мерната таблица не променят "хубавостта".
Следователно, броят на хубави таблици е броят начини да се построят $(n-1)$-мерни таблици, тоест $\answerbox{2^{(n-1)^2}}$. \hfill \colorbox{YellowGreen}{20т.}
\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$ е покриване.
\noindent
\colorbox{RedOrange}{\parbox{\textwidth}{Това не е достатъчно ясно описано. Дефиницията за покриване се основава върху ребрата. Тоест трябва да избереш съвсем произволно ребро и да покажеш, че поне единият му край е във $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$ е антиклика. \hfill \colorbox{YellowGreen}{15т.}
\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}
\hfill \colorbox{YellowGreen}{25т.}
\end{document}
|
