\documentclass[11pt,oneside,a4paper]{article}
\usepackage[margin=2cm]{geometry}
\usepackage{fancyhdr}
\usepackage{amsmath,amsthm,amssymb}
\usepackage{graphicx}
\usepackage{hyperref}

\usepackage{mathtext}
\usepackage[T1,T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[english,bulgarian]{babel}
\usepackage{setspace}

%\usepackage{array}

%\usepackage[chapter]{algorithm}
%\usepackage[noend]{algpseudocode}
%\usepackage{float}
%\floatname{algorithm}{Алгоритъм}

%\usepackage{myalg}

\setlength{\parindent}{10pt} 
\setlength{\parskip}{1ex}

\begin{document}

\begin{center}
\begin{spacing}{2}
Второ домашно по Дискретни структури, 03.01.2018 г.
\end{spacing}
Име: \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_, ФН:\_\_\_\_\_, Група:\_\_\_\_\_\_\_ 
\end{center}

\begin{center}
\begin{tabular}{|l|c|c|c|c|c|c||c|}
\hline
Задача & 1 & 2a & 2b & 3 & 4 & Общо \\ 
\hline
\hline
получени точки & $\quad \quad$ & $\quad \quad$ & $\quad \quad$ & $\quad \quad$ & $\quad \quad$ & \\
\hline
максимум точки &  1 & 1 & 1 & 1 & 1 & 5 \\
\hline
\end{tabular}
\end{center}

\emph{Забележка:} Предайте домашното на вашия асистент най-късно на 18 януари, преди започване на упражнението на групата Ви !

\paragraph{Задача 1.} 
Бълха скача между съседните точките с цели координати в равнината.
При скока тя се мести или надясно или нагоре, тоест от точка $(x,y)$
бълхата отива или в точка $(x+1,y)$, или в $(x,y+1)$.

По колко различни начина бълхата може да стигне от точка $(0,0)$ до точка $(m,n)$.

\paragraph{Задача 2.} 
Графът на хиперкуба $B_n$ дефинираме така: \\
Върховете на $B_n$ са всички редици от нули и единици с дължина $n$.
Два върха са свързани с ребро, ако съответните им редици се различават в точно една позиция.

Разстояние между два върха е дължината на най-краткия път между тях.

(a) Нека имаме три върха в $B_n$. Докажете, че два от тях са на разстояние не по-голямо от $\frac{2n}{3}$.

(b) Посочете четири върха в $B_{3k}, k>0$, такива, че всеки два от тях са на разстояние $2k$.

\paragraph{Задача 3.}
В дървото $T(V,E)$ върхове имат степен 1 или 3 (от всеки връх излизат 1 или 3 ребра).
Докажете, че листата (върховете със степен 1) са с 2 повече от вътрешните върхове (върховете със степен 3).

\paragraph{Задача 4.}
Графът $G(V,E)$ е 3-регулярен (от всеки връх излизат точно 3 ребра).
В $G$ няма цикли с дължина 3 и 4.
Докажете, че $G$ има поне 10 върха.
Възможно ли е $G$ да има точно 10 върха?

%\end{document}

\newpage
\subsection*{Решения}

\paragraph{Задача 1.} За да стигне от точка $(0,0)$ до точка $(m,n)$, бълхата трябва да направи 
$m$ скока надясно и $n$ скока нагоре, независимо от реда на скоковете. 
Различните начини на придвижване можем да представим като редица от $m+n$ букви. 
Членовете на редицата можем да означим с букви "r" (за скок надясно) и "u" (за скок нагоре).
Всяка редица ще съдържа точно $m$ букви "r" и точно $n$ букви "u".
Броят на различните редици е $\binom{m+n}{m}=\binom{m+n}{n}$.

\paragraph{Задача 2.a} Нека $A, B$ и $C$ са 3 върха на $B_n$.

Нека $\alpha_i, \beta_i, \gamma_i$ представят $i$-та координата на редиците от нули и единици, представящи трите върха.

Тъй като координатите са 0 или 1, поне две от трите стойности $\alpha_i, \beta_i$ и $\gamma_i$
съвпадат. Ще използваме това свойство, за да решим задачата.

Разглеждаме 4 варианта за тройката $\alpha_i, \beta_i, \gamma_i$:
\begin{enumerate}
  \item трите координати съвпадат
  \item $\alpha_i=\beta_i$, $\gamma_i$ е различно
  \item $\alpha_i=\gamma_i$, $\beta_i$ е различно
  \item $\beta_i=\gamma_i$, $\alpha_i$ е различно
\end{enumerate}

Нека броят тройки от 4-те варианта е $x_1, x_2, x_3, x_4$. 
Общият брой тройки е $n$.

Нека $k=x_2+x_3+x_4$ е броят на тройките с различия. 
Най-голямото от числата $x_2, x_3, x_4$ ще е поне $k/3$.

Нека това най-голямо число е $x_2$ (разсъжденията в останалите 2 случая са аналогични).
Този случай описва ситуацията, когато $AB$ е най-късата страна в триъгълника $ABC$.

Щом $x_2\ge k/3$ следва, че $x_3+x_4\le 2k/3$. От $k\le n$ следва $x_3+x_4\le 2n/3$.

Върховете $A$ и $B$ имат съвпадащи координати в $x_1+x_2$ случая и различаващи се координати в останалите $x_3+x_4$ случая. 

Но $x_3+x_4\le 2n/3$, а най-краткият път в хиперкуба между $A$ и $B$ е броят на различните битове в описанието на върховете, следователно $A$ и $B$ са на разстояние не по-голямо от $\frac{2n}{3}$.


\paragraph{Задача 2.b} 
Да разгледаме най-малкия случай -- $k=1$, това е обикновения куб $B_3$.
В него лесно намираме 4 върха, всеки два на разстояние 2, примерно върховете $000, 011, 101, 110$.

За произволно $k$ получаваме търсената четворка върхове, като повторим $k$ пъти всеки бит във вече построените 4 върха за обикновения куб. 

\paragraph{Задача 3.} 
%В дървото $T(V,E)$ върхове имат степен 1 или 3 (от всеки връх излизат 1 или 3 ребра).
%Докажете, че листата (върховете със степен 1) са с 2 повече от вътрешните върхове (върховете със степен 3).

Нека $n_1$ е броят на върховете във степен 1, $n_3$ е броят на върховете във степен 3, 
а $m$ е броят на ребрата в $T$.

Тъй като $T$ е дърво, върховете са с едно повече от ребрата: $m=n_1+n_3-1$.

От всеки връх излизат толкова ребра, колкото е степента му, 
от всички върхове на $T$ излизат $n_1+3n_3$ ребра.
Всяко ребро се брои 2 пъти, защото има два края, следователно $2m=n_1+3n_3$.

Изключваме $m$ от двете равенства: $2(n_1+n_3-1)=n_1+3n_3$ 

Получаваме $n_1=n_3+2$, което и трябваше да се докаже.


\paragraph{Задача 4.} 
Ако графът не е свързан, разсъждаваме за една свързана компонента в него.
Тоест, ще покажем, че всяка свързана компонента има поне 10 върха.

Нека $s$ е произволен връх в $G$, обхождаме графа в ширина, тръгвайки от $s$.
Обхождането ще раздели графа на слоеве. В слой $L_0$ е само върха $s$.

В слой $L_1$ ще попаднат върховете, пряко свързани с $s$. 
От условието следва, че това са 3 върха, да ги означим с $a, b, c$.
Не може да има ребро между някои от тези 3 върха, тъй като ще получим триъгълник (цикъл с дължина 3).

Следователно от всеки от върховете  $a, b, c$ 
излизат по две ребра към върхове от следващия слой $L_2$ 
(третото им ребро е назад към $s$).

Нека от $a$ излизат ребра към $a_1, a_2$, 
от $b$ излизат ребра към $b_1, b_2$ 
и от $c$ излизат ребра към $c_1, c_2$.

Ако допуснем, че два от новите шест върха съвпадат, ще получим цикъл с дължина 4.
Примерно, ако допуснем че $a_1$ и $b_2$ са един и същ връх, ще получим цикъла $s,a,a_1,b$.

От горните разсъждения следва, че графът има поне 10 върха - един в $L_0=\{s\}$, 
три в $L_1=\{a,b,c\}$ и шест в $L_2=\{a_1, a_2, b_1, b_2, c_1, c_2\}$.

Графът може да е с точно 10 върха.

Можем да се убедим в това като добавим нови ребра в конструкцията с нивата от обхождането, без да добавяме нови върхове.

Добавяме шест ребра, свързващи върховете от слой $L_2$ в цикъл $(a_1, b_1, c_1, a_2, b_2, c_2)$.
В полученият граф всеки връх е от степен 3 и няма цикли с дължина 3 и 4.

Този граф е единствен с точност до изоморфизъм -- това е графът на Петерсен.


\end{document}