\documentclass[a4paper, 12pt]{article}
\usepackage[T2A]{fontenc}
\usepackage[cp1251]{inputenc}
\usepackage[russian]{babel}
\linespread{1.2}

\usepackage{amsthm,amssymb, amsmath, amsfonts, amscd}
\usepackage{texdraw}

\usepackage[left=2cm,right=2cm,top=2cm,bottom=2cm,bindingoffset=0cm]{geometry}


\def\geq{\geqslant}
\def\leq{\leqslant}
\def\iff{\Leftrightarrow}
\def\therefore{\Rightarrow}
\def\because{\Leftarrow}

\newcommand{\mytitle}[2] {
  \begin{center}
      \bf {#1}. {#2}.
  \end{center}
}

\newenvironment{solution} {

{\it Решение.}
} {
}




\begin{document}

\mytitle{Домашнее задание 6}{Основные понятия теории графов}
\begin{center}
      {Группа 102/3}
	  	  \\{\it Здесь могла быть Ваша реклама}
\end{center}

Количество баллов на зачёт: 8

\begin{enumerate}

\item (1 балл) В футбольной лиге имеется два дивизиона, в каждом --- по 13 команд; можно ли составить такое расписание игр, при котором каждая команда сыграет девять игр с командами из своего дивизиона и четыре --- с командами из другого дивизиона?
\begin{solution}
\end{solution}

\item (0,5 балла) Докажите, что любой турнир, построенный на $n$ вершинах, имеет не более одной вершины $x$, исходящая степень которой $outdeg(x)=n-1$.
\begin{solution}
\end{solution}

\item (0,5 балла) Докажите, что в случае нечетных $n$ существует турнир $T$, в котором для любой вершины $x$ выполняется равенство
$$
outdeg(x)=indeg(x).
$$
\begin{solution}
\end{solution}

\item (1 балл) Пусть $G$ есть граф, построенный на вершинах $1,\ldots,15$, в котором вершины $i$ и $j$ смежны тогда и только тогда, когда их наибольший общий делитель больше единицы. Подсчитать количество связных компонент такого графа, а также определить максимальную длину простого пути (path) в графе $G$.
\begin{solution}
\end{solution}

\item (1 балл)
Докажите, что в любом графе $G$ расстояние $d(x,y)$ между вершинами удовлетворяет неравенству треугольника
$$
d(x,z)+d(z,y)\geq d(x,y)\qquad \forall\quad x,y,z\in V(G). 
$$
\begin{solution}
\end{solution}

\item (1 балл)
Докажите, что радиус и диаметр графа связаны следующим образом:
$$
r(G)\leq diam(G)\leq 2r(G).
$$
Привести примеры графов, на которых оба неравенства достигаются (определения).
\begin{solution}
\end{solution}


\item (1,5 балла)
Докажите или опровергните следующее утверждение: объединение двух \emph{различных} маршрутов, соединяющих две вершины, содержит цикл.
\begin{solution}
\end{solution}


\item (1 балл) 
Невозрастающая последовательность неотрицательных чисел
$$
\bold{d} := (d_1, d_2, \ldots , d_n),\quad d_1 \geq d_2 \geq \ldots \geq d_n \geq 0,
$$
называется \textit{графовой}, если она является последовательностью степеней вершин некоторого \textit{простого} графа $G$. Какие из представленных ниже числовых последовательностей являются графовыми?
$$
\begin{array}{ll}
(1) &\text{5 2 2 1}\\
(2) &\text{2 2 1 1}\\
(3) &\text{1}\\
(4) &\text{2}\\
(5) &\text{1 1}\\
(6) &\text{6 5 4 3}
\end{array}
$$
\begin{solution}
\end{solution}

\item (2 балла)
Рассмотрим последовательность $\bold{d_1} := (3, 3, 3, 3, 3, 2, 2, 1)$. Удалим в ней число 3, стоящее на первой позиции, а от следущих трех чисел отнимем по единице. В результате получим последовательность $\bold{d_2} := (2, 2, 2, 3, 2, 2, 1)$, которая после переупорядочивания по невозрастанию примет вид $(3, 2, 2, 2, 2, 2, 1)$. В общем случае соответствующая пара последовательностей будет иметь следующий вид:

%\begin{equation}
\begin{alignat*}{2}
\bold{d_1} &:= (s, \quad d_1, \quad d_2,\quad  \ldots , d_s, &&d_{s+1}, \ldots , d_n), \\
\bold{d_2} &:= \quad (d_1-1, d_2-1, \ldots , d_s-1, {}&&d_{s+1}, \ldots , d_n).
\end{alignat*}
%\end{equation}

Докажите, что последовательность $\bold{d_1}$ является графовой тогда и только тогда, когда таковой является и последовательность $\bold{d_2}$. Сформулируйте на основании данного утверждения алгоритм проверки на графовость для невозрастающей числовой последовательности.
\begin{solution}
\end{solution}


\item (1,5 балла)
Докажите, что граф $Q_k$ (т. е. $k$-куб) действительно является $k$-регулярным двудольным графом. Подсчитайте количество вершин и ребер в таком графе. Сколько различных копий $P_3$ и $C_4$ содержит такой граф?
\begin{solution}
\end{solution}

\item (2 балла) Пусть $G$ есть простой граф, диаметр которого $diam(G)\geq 3$. Доказать, что его дополнение $\bar{G}$ имеет диаметр $diam(\bar{G})\leq 3$
\begin{solution}
\end{solution}

\item (2,5 балла) Докажите, что простой граф $G$, построенный на $10$ вершинах и имеющий $28$ ребер, содержит цикл длины $4$.  
\begin{solution}
\end{solution}

\end{enumerate}

\end{document}


