\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.2017г.
\end{spacing}
Име: \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_, ФН:\_\_\_\_\_, Група:\_\_\_\_\_\_\_ 
\end{center}

\begin{center}
\begin{tabular}{|l|c|c|c|c|c|c||c|}
\hline
Задача & 1 & 2 & 3 & 4 & 5 & Общо \\ 
\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{Забележка:} Предайте домашното на вашия асистент най-късно на 19 януари, преди започване на упражнението на групата Ви !

\paragraph{Задача 1.} 
Решете рекурентното уравнение:

$R_n=R_{n-1}+2R_{n-2}+n$ при начални условия $R_0=0, R_1=1$.


\paragraph{Задача 2.}  
Дадено е нечетно естествено число $n=2k+1$.
Пресметнете по колко начина $n$ може да се представи като сума на две четни и едно нечетно число.
Трите числа в сумата са естествени (включително и нула).

\emph{Забележка:} Две представяния са различни, ако едното не се получава от другото с разместване на събираемите. 

%\emph{Упътване:} Ползвайте принципа за включване и изключване.

\paragraph{Задача 3.} 
Докажете, че графът на хиперкуба $B_k$ не е планарен за $k>3$.

\emph{Дефиниция:} Върховете на $B_k$ са всички редици от нули и единици с дължина $k$.
Два върха са свързани с ребро, ако съответните им редици се различават в точно една позиция.

\paragraph{Задача 4.}
Дърветата $T_1(V,E_1)$ и $T_2(V,E_2)$ имат общо множество върхове, но някои от ребрата се различават.

Ако точно $k$ ребра в двете дървета са различни ($|E_1 \backslash E_2|=|E_2 \backslash E_1|=k$), 
постройте редица от дървета $S_0, S_1, \ldots , S_k$ със свойства:

(1) Всяко от дърветата в редицата има множество от върхове $V$.

(2) $S_0$ съвпада с $T_1$, а $S_k$ съвпада с $T_2$.

(3) поредните дървета в редицата $S_i$ и $S_{i+1}$ се различават по точно едно ребро.

\paragraph{Задача 5.} Пътна мрежа е множество градове и шосета, като всяко шосе свързва два града. Пътната
мрежа на някаква държава е такава, че от всеки град може да се стигне до всеки, но по един
единствен начин, и освен това броят на шосетата е четно число. Докажете, че има поне един град,
от който излизат четен брой шосета.

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

\paragraph{Задача 2.} Нека $n=x+y+z$, където $x\leq y$ са четни, а $z$ е нечетно. 

Ще преброим по колко начина можем да изберем $x$ и $y$ при фиксирано $z$.
Очевидно $x+y=n-z=2c$ е четно, нека $x=2a, y=2b$. Тогава $a+b=c, a\leq b$.
Разглеждаме два случая:

Ако $c$ е четно, $a$ може да приема стойности от 0 до $c/2$, 
броят на възможните случаи за двойката $(a,b)$ e $c/2+1$.

Ако $c$ е нечетно, $a$ може да приема стойности от 0 до $(c-1)/2$, 
броят на възможните случаи за двойката $(a,b)$ e $(c+1)/2$.

Когато $z$ се мени от 1 до $n=2k+1$, $2c$ ще приема четни стойности от 0 до $2k$, 
тоест  $c$ ще приема стойности от 0 до $k$.

Разглеждаме два случая за $k$:

(a) $k=2l$ е четно.

В този случай $c$ приема четни стойности $0, 2 \ldots 2l$.
Броят варианти за двойката $(a,b)$ e \\
$\sum_{i=0}^l{(2i/2+1)}=\sum_{i=0}^l{(i+1)}=l(l+1)/2+l+1=(l+1)(l+2)/2$.

$c$ приема нечетни стойности $1, 3 \ldots 2l-1$.
Броят варианти за двойката $(a,b)$ e \\
$\sum_{i=0}^{l-1}{((2i+1)+1)/2)}=\sum_{i=0}^{l-1}{(i+1)}=l(l+1)/2$.

Събираме случаите на четно и нечетно обхождане за $c$ и получаваме всички варианти за $(a,b)$:

$(l+1)(l+2)/2+l(l+1)/2=(l+1)(2l+2)/2=(l+1)^2=(k/2+1)^2=((n-1)/4+1)^2$

(b) $k=2l+1$ е нечетно.

В този случай $c$ приема четни стойности $0, 2 \ldots 2l$.
Броят варианти за двойката $(a,b)$ e \\
$\sum_{i=0}^l{(2i/2+1)}=\sum_{i=0}^l{(i+1)}=l(l+1)/2+l+1=(l+1)(l+2)/2$.

$c$ приема нечетни стойности $1, 3 \ldots 2l+1$.
Броят варианти за двойката $(a,b)$ e \\
$\sum_{i=0}^{l}{((2i+1)+1)/2)}=\sum_{i=0}^{l}{(i+1)}=(l+1)(l+2)/2$.

Събираме случаите на четно и нечетно обхождане за $c$ и получаваме всички варианти за $(a,b)$:

$(l+1)(l+2)/2+(l+1)(l+2)/2=(l+1)(l+2)=(k+1)(k+3)/4=(n+1)(n+5)/16$

Окончателно при четно $k$ различните начини са $(k/2+1)^2=((n-1)/4+1)^2=(n+3)^2/16$.

При нечетно $k$ различните начини са $(k+1)(k+3)/4=(n+1)(n+5)/16$.

\paragraph{Задача 3.} На лекции сме отбелязвали, че $B_k$ е подграф на $B_{k+1}$, 
следователно е достатъчно да покажем, че $B_4$ не е планарен.
Ще ползваме теоремата на Куратовски за първите два начина:

(a - свиване до $K_5$) 

Вземаме подграфа $G$ на $B_4$, породен от върховете с нула, 
една и две единици в булевите вектори и свързващите ги ребра. 
Всеки връх с две единици в $G$ е свързан с точно два други върха с по една единица.
 
Примерно връх 0110 е свързан с двата върха 0100 и 0010.
Пътят (0100,0110,0010) се свива до ребро в свития граф $G'$ (0100,0010).

В свития граф всички върхове с по две единици ще изчезнат при свиването, 
а ще се появят ребра между коя да е двойка върхове с по една единица.

Така в свития граф ще останат 5 върха - 0000, 0001, 0010, 0100 и 1000 и ребра между всеки два от тях, 
той е изоморфен на $K_5$.

(b - свиване до $K_{3,3}$) 

Вземаме подграф $G_0$ на $B_4$, с върхове 0000, 0001, 0010, 0100, 0011, 0110 и ребрата между тях.
 
$G_0$ е двуделен граф с дялове (0000, 0011, 0110) и (0001, 0010, 0100), но не е пълен.

За да стане пълен, трябва да добавим 2 ребра -- (0100,0011) и (0110,0001).

Добавяме следните пътища от $B_4$ към $G_0$:

(0100, 0101, 0111, 0011) и (0110,1110,1111,1101,1001,0001)

В полученият по-голям граф $G$ всички нови (спрямо $G_0$) върхове имат степен 2.
При свиването на добавените пътища получаваме търсените 2 ребра, които правят свития граф $G'$
изоморфен на $K_{3,3}$.

(c - чрез формула на Ойлер)

\emph{Решението предложи студентът Данаил Цветанов.}

Допускаме, че $B_k$ е планарен.

За всеки планарен граф е в сила формулата на Ойлер:
\begin{equation}
 v-e+f=2 
\end{equation}
където $v$ е броят на върховете, $e$ -- броят на ребрата, 
а $f$ е броят на лицата (площите, оградени от ребра),
включително външната безкрайна площ около рисунката.

Нека броят ребра, ограждащи $i$-тата площ е $m_i$. 
Тъй като всяко ребро граничи с две площи, вярна е формулата: 
\begin{equation}
 \sum_{i=1}^f m_i=2e 
\end{equation}
Тъй като графът на хиперкуба $B_k$ е двуделен, всяка площ има четен брой ограждащи ребра 
(ограждащите ребра образуват цикъл, а в двуделните графи всички цикли са с четна дължина).
Освен това в $B_k$ няма цикли с дължина 2 (той е обикновен неориентиран граф).
Следователно всяка площ има поне 4 ограждащи ребра, т.е. $m_i\geq 4$.
Получаваме веригата неравенства:
\begin{equation}
 4f=\sum_{i=1}^f 4 \leq \sum_{i=1}^f m_i=2e 
\end{equation}
или $f\leq \frac{e}{2}$. Заместваме във формулата на Ойлер и получаваме:
$ v-e+\frac{e}{2}\geq 2 $ или 
\begin{equation}\label{l1}
 v-\frac{e}{2}\geq 2 
\end{equation}
В $B_k$ от всеки връх излизат точно $k$ ребра, и тъй като всяко ребро свързва точно два върха,
вярно е равенството $kv=2e$.
Броят на върховете е $v=2^k$, а за броя ребра получаваме $e=k2^{k-1}$. 
Заместваме в (\ref{l1}):
\begin{equation}
 2^k-k2^{k-2}\geq 2
\end{equation}
Делим на $2^{k-2}$:
\begin{equation}
 4-k\geq 2^{3-k} > 0
\end{equation}
еквивалентно на $4>k$, но по условие $k>3$ -- противоречие.

\paragraph{Задача 4.} 
Ако $k=0$, задачата е тривиална, нека $k>0$.
Нека $S_0$ съвпада с $T_1$, ще построим $S_1$ по два различни начина така, 
че да удовлетвори условията в задачата.

%\mbox{}\\

\emph{Първи начин:} Избираме ребро $e_1$ от $S_0=T_1$, което не се среща в $S_k=T_2$.
Махаме $e_1$ от $S_0$. Това действие ще го превърне в гора с две дървета. 
Нека $V_1$ и $V_2$ са техните върхове. 

Тъй като $T_2$ е свързан, поне едно ребро в него ще свързва $V_1$ и $V_2$.
Да означим това ребро с $e_2$, то не може да е от $S_0$, 
тъй като единственото ребро, свързващо  $V_1$ и $V_2$ в $S_0$ е $e_1$, но то не се среща в $T_2$.

Сега добавяме $e_2$ към гората, получена при изтриването на $e_1$ от $S_0$.
Полученият граф е дърво, означаваме го с $S_1$. 
Той се различава от $S_0$ по едно ребро (заменихме $e_1$ с $e_2$).
Очевидно $S_1$ се различава от $S_k$ по $k-1$ ребра.


\emph{Втори начин:} Избираме ребро $e_2$ от $S_k=T_2$, което не се среща в $S_0=T_1$.
Добавяме $e_2$ към $S_0$. 
Ще получим цикъл, в който има поне едно ребро, което не е от $S_k=T_2$. 
Да означим това ребро с $e_1$, изтриваме го и късаме цикъла.

Полученият граф е дърво, означаваме го с $S_1$. 
Той се различава от $S_0$ по едно ребро (заменихме $e_1$ с $e_2$).
Очевидно $S_1$ се различава от $S_k$ по $k-1$ ребра.

Търсената редица от дървета ще получим, като повторим гореописаната стъпка още $k-1$ пъти -- 
като заменим ребро от $S_1$ ще получим $S_2$, после от $S_2$ ще получим $S_3$ и т.н.

За да опишем формално стъпките на строеж на редицата, трябва да ползваме индукция.
Оставяме това упражнение на читателя. 

\end{document}