\documentclass[14pt]{article}
\usepackage{graphicx}
\graphicspath{ {images/} }
\usepackage[utf8]{inputenc}
\usepackage{amsthm,amssymb, amsmath, amsfonts, amscd}
\usepackage[russian]{babel}
\usepackage[left=2cm,right=2cm,top=1cm,bottom=1cm,bindingoffset=0cm]{geometry}
\begin{document}
\title{28 сентября 2017}
\date{}
\maketitle
\vspace{-40pt}
Количество баллов на зачет: \textit{7.5}
\begin{enumerate}
\item \textit{(0.5 балла)} Невозрастающая последовательность неотрицательных чисел
$$
{\bf d}:=(d_1,d_2,\ldots,d_n) \,\,\colon\qquad d_1\geq d_2\geq \ldots\geq d_n\geq 0
$$
называется \emph{графовой,} \index{последовательность!- графовая}если она является последовательностью степеней вершин некоторого \emph{простого} графа $G$. Показать, что последовательности чисел $(1,1,0)$ и $(2,2,1,1)$ являются графовыми, предъявив для каждой из них соответствующие им простые графы.


\item \textit{(1 балл)} Какие из представленных ниже числовых последовательностей являются графовыми?
$$
\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}
$$
\item \textit{(2 балла)} Рассмотрим последовательность ${\bf d_1}:=(3,3,3,3,3,2,2,1)$. Удалим в ней число $3$, стоящее на первой позиции, а от следущих трех чисел отнимем по единице. В результате получим последовательность ${\bf d_2}:=(2,2,2,3,2,2,1)$, которая после переупорядочивания по невозрастанию примет вид $(3,2,2,2,2,2,1)$. В общем случае соответствующая пара последовательностей будет иметь следующий вид:
$$
\begin{array}{cccccccccc}
{\bf d_1}&:=&(s,&d_1,&d_2,&\ldots,&d_s,&d_{s+1},&\ldots,&d_n),\\
{\bf d_2}&:=&&(d_1-1,&d_2-1,&\ldots,&d_s-1,&d_{s+1},&\ldots,&d_n).
\end{array}
$$
Доказать, что последовательность ${\bf d_1}$ является графовой тогда и только тогда, когда таковой является и последовательность ${\bf d_2}$. Сформулировать на основании данного утверждения алгоритм проверки на графовость для невозрастающей числовой последовательности. 

\item \textit{(1.5 балла)} Любой элемент $a_{i,j}$ матрицы $M_a$ смежности графа $G$ можно трактовать как количество путей длины $1$ в графе $G$ из вершины $i$ в вершину $j$. Чему равны с этой точки зрения элементы матрицы $M_a^2$? Можно ли обобщить данный результат на случай произвольной степени $k>1$ матрицы $M_a$?

\item \textit{(1 балл)} Доказать, что для произвольного турнира $T$ справедливо равенство
$$
\sum\limits_{x\in V(T)}\text{outdeg}(x)^2=\sum\limits_{x\in V(T)}\text{indeg}(x)^2.
$$

\item \textit{(1.5 балла)} Орграф $D$ называется сбалансированным, если для любой вершины $x\in V(D)$ выполняется неравенство
$$
|\text{outdeg}(x)-\text{indeg}(x)|\leq 1.
$$
Доказать, что из любого неориентированного графа $G$ можно получить направленный сбалансированный орграф $D$.

\item \textit{(1 балл)} Пусть в графе $G$ ровно две вершины имеют нечетную степень. Доказать, что эти вершины являются связанными.

\item \textit{(1.5 балл)} Доказать, что в связном графе два максимальных простых пути имеют общую вершину.

\item \textit{(1.5 балла)} Пусть $G$ есть граф, вершины которого помечены битовыми строками длины $k\geq 1$. Вершины $x$ и $y$ в таком графе являются смежными тогда и только тогда, когда соответствующие им битовые строки отличаются ровно в двух позициях. Определить количество связных компонент в таком графе.

\item \textit{(1 балл)} Доказать, что любой маршрут, соединяющий вершины $x$ и $y$, содержит простой путь, соединяющий те же самые вершины.

\item \textit{(1 балл)} Доказать, что простой граф $G$, минимальная степень $\delta(G)$ \index{степень вершины!- минимальная $\delta(G)$} которого больше или равна $n/2$, является связным. Показать, что эта оценка точная, предъявив несвязный граф с $\delta(G)=n/2-1$.

\end{enumerate}
\end{document}