\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}
Второ контролно (теория) по Дискретни структури, 13.01.2017г.
\end{spacing}
Име: \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_, ФН:\_\_\_\_\_, Група:\_\_\_\_\_\_\_ 
\end{center}

\begin{center}
\begin{tabular}{|l|c|c|c|c|c|c||c|}
\hline
Задача & 1a & 1b & 2 & 3a & 3b & Общо \\ 
\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{Забележка:} За отлична оценка са достатъчни 100 точки!

\paragraph{Задача 1.}  \mbox{}

(a) Дефинирайте понятието 'свързана компонента' в неориентиран граф.

(b) Дефинирайте понятието 'силно свързана компонента' в ориентиран граф.

\paragraph{Задача 2.} \mbox{}

Докажете, че графът на хиперкуба $B_k$ е двуделен.

\emph{Дефиниция:} Графът $G(V,E)$ е двуделен, когато можем да боядисаме 
върховете с два цвята така, че всяко ребро има разноцветни краища.

\paragraph{Задача 3.}  \mbox{}

Булевата функция $f(x,y,z)$ приема стойност $1$, точно когато четен брой от променливите \`{и} са единици.

(a) Намерете нейната минимална ДНФ.

(b) Докажете, че множеството $F=\{f, \land \}$ е пълно.

\newpage

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

\paragraph{Задача 1.} % \mbox{}
Да означим графа с $G(V,E)$.

(a) Свързана компонента в неориентирания граф $G$ наричаме множеството \\
$[u]=\{v|v\in V, \; има \; път \; от \; u \; до \; v\}$,
за някой връх $u\in V$.

(b) Силно свързана компонента в ориентирания граф $G$ наричаме множеството \\
$[u]=\{v|v\in V, \; има \; път \; от \; u \; до \; v\ \; и \; има \; път \; от \; v \; до \; u\}$,
за някой връх $u\in V$.

\paragraph{Задача 2.} \mbox{}

Върховете на $B_k$ са булеви редици с дължина $k$.
Два върха са свързани с ребро, ако съответните им редици се различават в точно една позиция.
Бройките на единиците в два съседни върха на $B_k$ ще се различават с единица, следователно ще са с различна четност.

Ако боядисаме бели всички върхове с четен брой единици и черни всички върхове с нечетен брой единици, получаваме оцветяване на $B_k$, при което всяко ребро има разноцветни краища.


\paragraph{Задача 3.} \mbox{}

(a) $f(x,y,z)$ приема стойност $1$ в четири случая, при стойности на променливите съответно 000, 011, 101 и 110.
Тъй като съответните елементарни конюнкции се различават помежду си на 2 места, те не могат да бъдат съкратени и са прости импликанти.

Следователно съвършената и минимална ДНФ на $f(x,y,z)$ съвпадат и имат вида:

$f(x,y,z)=\overline{x}\overline{y}\overline{z} \lor \overline{x}yz \lor x\overline{y}z \lor xy\overline{z}$
 
(b - първи начин ) 

Разглеждаме $f(x,x,x)$. Тя е 1, когато x е 0 и приема стойност 0, ако x е 1.

Следователно $f(x,x,x)=\overline{x}$ и множеството $F=\{f, \land \}$ е пълно, 
тъй като с функции от $F$ изразяваме отрицание и конюнкция, които са известно пълно множество.

(b - втори начин ) 

С проста проверка установяваме, че $f(x,y,z)$ не запазва нулата и единицата и не е монотонна.

Конюнкцията пък не е линейна и самоспрегната.

От критерия на Пост-Яблонски следва, че двете образуват пълно множество.


\end{document}