
 \documentclass[12pt, leqno]{article}
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}        % Кодировка входного документа;
                                    % при необходимости, вместо cp1251
                                    % можно указать cp866 (Alt-кодировка
                                    % DOS) или koi8-r.

\usepackage[english,russian]{babel} % Включение русификации, русских и
                                    % английских стилей и переносов
%%\usepackage{a4}
%%\usepackage{moreverb}
\usepackage{amsmath,amsfonts,amsthm,amssymb,amsbsy,amstext,amscd,amsxtra,multicol}
\usepackage{verbatim}
\usepackage{listings}
\usepackage{algorithm2e}


\usepackage{float}
\usepackage{tabto} %Табуляция
\usepackage{tikz} %Рисование автоматов
\usetikzlibrary{automata,positioning,trees,shapes.geometric}  

\usetikzlibrary{trees,arrows,positioning, calc, shadows, spy, backgrounds} 

\pgfdeclarelayer{back}
	\pgfdeclarelayer{front}
	\pgfsetlayers{back,main,front}

\tikzstyle{redVertex}  =[draw,fill=red,     circle,minimum size=18pt,inner sep=0pt, text=white]
\tikzstyle{blackVertex}=[draw,fill=black,   circle,minimum size=18pt,inner sep=0pt, text=white]
\tikzstyle{genVertex}= [draw,fill=gray!25, right color=gray!15, left color=gray!45,   circle,minimum size=18pt,inner sep=0pt, text=black]
\tikzstyle{nil}        =[draw,fill=black,rectangle,minimum size=15pt,inner sep=0pt, text=white, font=\tiny]
\tikzstyle{seg}        = [fill=blue!20, regular polygon, regular polygon sides=3,inner sep=1pt, outer sep=0pt] 
\tikzstyle{segedge} =[edge from parent path={(\tikzparentnode\tikzparentanchor) edge  (\tikzchildnode.north)}]

\definecolor{darkblue}{rgb}{0.2,0.2,0.6}
\definecolor{darkred}{rgb}{0.6,0.1,0.1}
\definecolor{darkgreen}{rgb}{0.2,0.6,0.2}

\def\arrow{
  (10.75:1.1) -- (6.5:1) arc (6.25:120:1) [rounded corners=0.5] --
  (120:0.9) [rounded corners=1] -- (130:1.1) [rounded corners=0.5] --
  (120:1.3) [sharp corners] -- (120:1.2) arc (120:5.25:1.2)
  [rounded corners=1] -- (10.75:1.1) -- (6.5:1) -- cycle
}

\tikzset{
  ashadow/.style={opacity=.25, shadow xshift=0.05, shadow yshift=-0.05},
}    
 
\tikzstyle{myarrows}=[line width=1mm,draw=gray!30,-triangle 60,postaction={draw, line width=2mm, shorten >=4mm, -}]

\def\bh{\mathbf{bh}}

%\newcommand{segedge}{}


   %[regular polygon, regular polygon sides=3,minimum size=15pt,inner sep=0pt, text=black] 
% triangle/.style = {fill=blue!20, regular polygon, regular polygon sides=3 }
\usepackage{multicol} %Несколько колонок
\usepackage{graphicx}
\usepackage[colorlinks,urlcolor=blue]{hyperref}
\usepackage[stable]{footmisc}
\usepackage{indentfirst}  % абзацный отступ после заголовка
\usepackage{enumitem} %Item tricks


%% \voffset-5mm
%% \def\baselinestretch{1.44}
\renewcommand{\theequation}{\arabic{equation}}
\def\hm#1{#1\nobreak\discretionary{}{\hbox{$#1$}}{}}
\newtheorem{Lemma}{Лемма}
\theoremstyle{definiton}
\newtheorem{Remark}{Замечание}
%%\newtheorem{Def}{Определение}
\newtheorem{Claim}{Утверждение}
\newtheorem{Cor}{Следствие}
\newtheorem{Theorem}{Теорема}
\newtheorem*{known}{Теорема}
\def\proofname{Доказательство}
\theoremstyle{definition}
\newtheorem{Def}{Определение}
\theoremstyle{definition}
\newtheorem{Example}{Пример}

%% \newenvironment{Example} % имя окружения
%% {\par\noindent{\bf Пример.}} % команды для \begin
%% {\hfill$\scriptstyle\qed$} % команды для \end






%\date{22 июня 2011 г.}
\let\leq\leqslant
\let\geq\geqslant
\def\MT{\mathrm{MT}}
%Обозначения ``ажуром''
\def\BB{\mathbb B}
\def\CC{\mathbb C}
\def\RR{\mathbb R}
\def\SS{\mathbb S}
\def\ZZ{\mathbb Z}
\def\NN{\mathbb N}
\def\FF{\mathbb F}
%греческие буквы
\let\epsilon\varepsilon
\let\es\varnothing
\let\eps\varepsilon
\let\al\alpha
\let\sg\sigma
\let\ga\gamma
\let\ph\varphi
\let\om\omega
\let\ld\lambda
\let\Ld\Lambda
\let\vk\varkappa
\let\Om\Omega
\def\first{\mathrm{ FIRST} }
\def\follow{\mathrm{ FOLLOW} }
\let\yield\Rightarrow
\def\abstractname{}

\def\R{{\cal R}}
\def\A{{\cal A}}
\def\B{{\cal B}}
\def\C{{\cal C}}
\def\D{{\cal D}}
\let\w\omega

%классы сложности
\def\REG{{\mathsf{REG}}}
\def\CFL{{\mathsf{CFL}}}
\def\PP{{\mathsf{P}}}
\def\NP{{\mathsf{NP}}}
\def\NPc{{\mathsf{NP}}\text{-}{\rm c}}
\def\coNP{{\rm co}\text{-}{\mathsf{NP}}}
\def\DTIME{{\mathsf{DTIME}}}
\def\NTIME{{\mathsf{NTIME}}}
\def\HALT{{\rm{HALT}}}
\def\SAT{{\rm{SAT}}}
\def\3SAT{{\rm{3\text{-}SAT}}}
\def\2SAT{{\rm{2\text{-}SAT}}}
\def\UNSAT{{\rm{UNSAT}}}
\def\LL{{\mathrm{LL}}}
\def\poly{{\rm{poly}}}
\newcounter{problem}
\newcounter{uproblem}
\newcounter{subproblem}
\def\pr{\medskip\noindent\stepcounter{problem}{\bf \theproblem .  }\setcounter{subproblem}{0} }
\def\prp{\medskip\noindent\stepcounter{problem}{\bf Задача \theproblem.\;}\setcounter{subproblem}{0}}
\def\prstar{\medskip\noindent\stepcounter{problem}{\bf Задача $\bf{\theproblem^*}\negmedspace .$  }\setcounter{subproblem}{0}}
\def\prdag{\medskip\noindent\stepcounter{problem}{\bf Задача $\mathbf\theproblem^\dagger$.\;}\setcounter{subproblem}{0}}
\def\upr{\medskip\noindent\stepcounter{uproblem}{\bf Упражнение \theuproblem .  }\setcounter{subproblem}{0} }
%\def\prp{\vspace{5pt}\stepcounter{problem}{\bf Задача \theproblem .  } }
%\def\prs{\vspace{5pt}\stepcounter{problem}{\bf \theproblem .*   }
\def\prsub{\medskip\noindent\stepcounter{subproblem}{\rm \thesubproblem .  } }  
\def\prsubr{\medskip\noindent\stepcounter{subproblem}{\rm \thesubproblem)} }  
%прочее
\def\quotient{\backslash\negthickspace\sim}
           



\begin{document}
\centerline{\LARGE Задание 9}

\medskip

\begin{center}
	{\Large Графы I }
\end{center}

\bigskip

{\bf Литература: }
\begin{enumerate}

	\item {\bf [Кормен 1]} {\em Кормен Т., Лейзерсон Ч., Ривест Р.}\\
	Алгоритмы: Построение и Анализ.\\ М.: МЦНМО, 2002.

	\item {\bf [Кормен 2]} {\em Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.}\\
	Алгоритмы: Построение и Анализ. (2-е изд.)\\ М.: Вильямс, 2005.

	\item {\bf [ДПВ]} {\em  Дасгупта С., Пападимитриу Х., Вазирани У.}\\ Алгоритмы.\\ М.: МЦНМО, 2014.  


\end{enumerate}
 

\section*{Домашнее задание}

\medskip
\noindent\textbf{Задачи 53-58} из КДЗ-2017.
\medskip

\prp Постройте такой граф $G$, что                                      

  \prsubr  поиск в ширину на $G$ в худшем случае работает за $O(|V|^2)$;

  \prsubr в результате топологической сортировки вершины оказываются упорядоченными единственным образом (не зависимо от обхода в глубину).

\textsl{Пункты задачи можно выполнять по отдельности.}


\end{document}

