\documentclass[12pt]{article}

% Автор: Беляев Станислав

\usepackage{polyglossia}
\usepackage{amsthm, amsmath, amssymb}
\usepackage{amssymb}
\usepackage[russian]{hyperref}
\usepackage{datetime}
\usepackage{cmap}
\usepackage{enumerate}
\usepackage{hologo}
\usepackage{minted}
\usepackage{unicode-math}
\usepackage{wasysym}
\usepackage{marvosym}

\defaultfontfeatures{Ligatures=TeX}
\setmainfont{CMU Serif}  
\setmonofont{CMU Typewriter Text}  
\setsansfont[Mapping=tex-text]{CMU Sans Serif}
\setmathfont{Latin Modern Math}
\setdefaultlanguage[spelling=modern]{russian}
\setotherlanguage{english}

\sloppy

\voffset=-20mm
\textheight=220mm
\hoffset=-25mm
\textwidth=180mm

\newenvironment{MyList}{
  \begin{enumerate}[1.]
  \setlength{\parskip}{-5pt}
  \setlength{\itemsep}{5pt}
}{
  \end{enumerate}
}

\def\EPS{\varepsilon}
\def\SO{\Rightarrow}
\def\EQ{\Leftrightarrow}
\def\t{\texttt}
\def\O{\mathcal{O}}
\newcommand{\q}[1]{\langle #1 \rangle} % <x>
\newcommand\URL[1]{{\footnotesize{\url{#1}}}}
\def\myindent{\hspace*{\parindent}}
\def\up{\vspace*{-\baselineskip}}
\def\NO{\t{\#}}
\newcommand{\ITEM}[1]{{\bf \underline{#1}}\hspace{0.5em}}
\newcommand{\Section}[1]{\section{#1}\vspace{-1.5em}\myindent\unskip}
\def\LINE{\noindent \underline{\hbox to 1\textwidth{{ } \hfil{ } \hfil{ } }}}
\newcommand{\BTEXT}[1]{\rlap{\hbox{\scriptsize{#1}}}}
\newcommand{\UBR}[2]{\underbrace{#1}_{\BTEXT{#2}}}
\newcommand{\OBR}[2]{\overbrace{#1}^{\BTEXT{#2}}}
\newcommand{\CTEXT}[1]{\rlap{\hbox{\tiny{#1}}}}
\newcommand{\UBRS}[2]{\underbrace{#1}_{\CTEXT{#2}}}
\newcommand{\OBRS}[2]{\overbrace{#1}^{\CTEXT{#2}}}

\begin{document}

\begin{center}
  {\Large \bf Лекция по алгоритмам \t{\#15}} \\ 
  \vspace{0.5em}
  {\Large \bf Тема: Карп, Йен, A$^*$} \\
  \vspace{0.5em}
  {\large 16 декабря} \\
  \vspace{0.5em}
  {Собрано {\today} в {\currenttime}}
\end{center}

\vspace{-1em}
\LINE

\Section{Цикл минимального среднего веса}

\ITEM{Задача:} найти в взвешенном орграфе цикл минимального среднего веса.\\
$$w_{ave}=\frac{\OBR{\sum\limits_{i=1}^{k}{w_i}}{ребра из цикла}}{\UBR{k}{размер цикла}}\to min$$
$$w_{min} \leqslant w_{ave} \leqslant w_{max}$$
{\bf Решение \NO{1.}} Бинпоиск.
Предикат с аргументом $x$ проверяет, что:
$$\frac{\sum\limits_{i=1}^{k}{w_i}}{k} < x \EQ \sum\limits_{i=1}^{k}{w_i} < \sum\limits_{i=1}^{k}{x} \EQ \UBR{\sum\limits_{i=1}^{k}{(w_i-x)} < 0}{цикл отрицательного веса}$$
Изменим вес ребер с $(w_i)$ на $(w_i-x)$ и будем искать цикл отрицательного веса алгоритмом Гольдберга. Время работы: $\O({\OBR{E\sqrt{V}log_2V}{алгоритм Гольдберга}}*log_2{|BS|})$ Оценим $|BS|$:\\
$BS.L=w_{min}$, $BS.R=w_{max}$ $\SO$ $|BS|=log_2{(\frac{w_{max}-w_{min}}{EPS})}$\\
Оценим $EPS$ (веса целочисленные):
$$\UBR{\frac{W_1}{k_1}-\frac{W_2}{k_2}}{$\neq$ 0} \geqslant \UBRS{\frac{1}{k_1k_2} \geqslant \frac{1}{n^2}}{в цикле не более n ребер} \SO EPS=\frac{1}{2n^2}$$
Таким образом:
$$|BS|=log_2{[2n^2(w_{max}-w_{min})]}$$\\
{\bf Решение \NO{2.}} Карп, $78$. Добавим в граф новую вершину $s$, с нулевыми ребрами во все остальные вершины. $d[k,v]$ - минимальный суммарный вес пути из $s$ в $v$ из $k$ ребер. Вычисляем $d$ Форд-Беллманом. Для $k=0$: $\forall v\neq s~d[0,v]=+\infty$\\
Введем новые величины ($\infty - \infty = \infty$):\\
$$M[v] =\limits^{def} {max}\limits_{k=0..n-1}{\frac{d[n,v]-d[k,v]}{n-k}}$$
$$\mu =\limits^{def} {min}\limits_{v \in V}{M[v]}$$
$$x =\limits^{def} \hbox{минимальный средний вес цикла}$$
\ITEM{Утверждение:} $x = \mu$ в графе $w_i=w_i-x-\EPS$\\
\ITEM{Лемма 1:} $w\to w + \UBRS{C}{const} \SO$
\begin{enumerate}
\item [1)] $x\to x + C$ (следует из определения)
\item [2)] $\mu\to \mu + C$ (следует из определения)
\end{enumerate}
\ITEM{Лемма 2:} Пусть докажем, что: ($x=0 \SO \mu=0$), тогда: $\forall x:\mu=x$
\begin{enumerate}
\item [1)] Вычтем $x$ из всех ребер.
\item [2)] По лемме 1: новый $x=0$, по предположению новый $\mu=0 \SO \mu=x$
\item [3)] $+x$ обратно. 
\end{enumerate}
\ITEM{Лемма 3:}
\begin{enumerate}
\item [a)] $\forall v: M[v] \geqslant 0$\\
Рассмотрим $M[v]$: знаменатель положителен $\SO$ знак определяется выражением:
$${max}\limits_{\BTEXT{k=0..n-1}}{(d[n,v]-d[k,v])}=d[n,v]-{min}\limits_{\BTEXT{k=0..n-1}}{(d[k,v])}=d[n,v]-d[v]$$
где $d[v]$ - кратчайший путь из $s$ до $v$ $\SO$ $d[v] \leqslant d[n,v] \SO d[n,v]-d[v] \geqslant 0$
\item[b)] $\exists v:M[v]=0$\\
Предполагаем, что $x=0 \SO \exists~0$-цикл. $u$ - какая-то вершина на цикле. Пусть существует какой-то путь из $s$ в $u$, состоящий из $k$ ребер. Проходимся по нему и, начиная с $u$, будем ходить по циклу. Пройдем еще $(n-k)$ ребер, остановясь в вершине $v$, принадлежащей циклу. Пусть $A$ - сумма весов ребер на пути из $u$ в $v$, $B$ - сумма весов ребер на пути из $v$ в $u$ далее по циклу. \boxed{$A+B=0$}\\
С одной стороны, очевидно, что: $d[v] \leqslant d[n,v]$\\
С другой стороны:
$$\UBR{d[v]<d[n,v]}{предположение}\leqslant \OBR{d[u]+A}{какой-то путь до $v$ из $n$ ребер}$$
$$\UBR{d[u]\leqslant d[v]+B<d[u]+A+B=d[u]}{противоречие}$$
Таким образом: $d[v]\geqslant d[n,v] \SO d[v]=d[n,v] \SO M[v]=0$\\
\end{enumerate}
\ITEM{Д-во утверждения:} Пусть $x=0$, по определению: $\mu = {min}\limits_{v \in V}{M[v]} {\SO}\limits^{Lm~3.a}$ если $\exists v:M[v]=0$, то $\mu=0 {\SO}\limits^{Lm~3.b} \mu = 0$, откуда ${\SO}\limits^{Lm~2}$ $\forall x:\mu=x$\\
\ITEM{Восстановление цикла:} Храним $p[k,v]$ - предок $v$ на пути из $k$ ребер. Пусть: $v:\mu={min}\limits_{i \in V}{M[i]}=M[v] \SO d[v]=d[n,v] \SO$ путь до $v$ содержит $0$-цикл $\SO$ откатываемся по предкам от $v \to$ находим цикл.\\
\ITEM{Если цикла нет:} $\UBR{d[k-1,u]}{~~~C(k-1)}+\UBR{w}{C}<\UBR{d[k,v]}{~~Ck} \SO p[k,v]=-1$\\
\ITEM{Алгоритм:}
\begin{enumerate}
\item [1)] Форд-Беллман от $S$
\item [2)] Формула, считающая $\mu$
\item [3)] Восстановление цикла по предкам
\end{enumerate}
\end{document}
