\documentclass[fullscreen=true,unicode,bookmarks=false]{beamer}
\usetheme{Boadilla}
%\includeonlyframes{defgeomcrossover}
%\includeonlyframes{GA}
%\includeonlyframes{mincoloring}
%\includeonlyframes{graphpart}
%\includeonlyframes{cross}
%\includeonlyframes{distpart}
%\includeonlyframes{stablecross}
%\includeonlyframes{greedy}
%\includeonlyframes{results}
%\includeonlyframes{ex2}

\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath,amsfonts,amssymb}
\usepackage{tikz}

\theoremstyle{definition}
\newtheorem{mydefinition}{Определение}
\newtheorem{myproblem}{Задача}
\newtheorem{mysign}{Обозначение}
\newtheorem{algorithm}{Алгоритм}
\newtheorem{given}{Дано}
\newtheorem{result}{Результат}
\theoremstyle{remark}
\newtheorem{remark}{Замечание}

\theoremstyle{example}
\newtheorem{myexample}{Пример}

\definecolor{MidnightBlue}{rgb}{0.2,0.2,0.7}
\definecolor{myblue}{rgb}{0.2,0.5,0.9}
\definecolor{lightyellow}{rgb}{1,1,0.7}
\definecolor{lightblue}{rgb}{0.7,0.8,1}
\definecolor{mygreen}{rgb}{0.7,1,0.7}
\definecolor{darkgreen}{rgb}{0,0.5,0}
\definecolor{greenyellow}{rgb}{0.8,1,0.6}
\definecolor{ellipsecolor}{rgb}{0.8,1,0.8}
\definecolor{lightgray}{rgb}{0.7,0.7,0.7}

\newcommand{\bigpoint}{circle(0.07)}

\newcommand<>{\colorhide}{\only#1{\textcolor{lightgray}}}
\newcommand<>{\txtcell}{\only#1{\textcolor{darkgreen}}}
\newcommand<>{\txtblue}{\only#1{\textcolor{blue}}}
\newcommand<>{\txtred}{\only#1{\textcolor{red}}}

\newcommand{\bZ}{{\mathbb Z}}
\newcommand{\bZpositiv}{{\mathbb Z_+}}
\newcommand{\bZnonnegativ}{{\mathbb Z_{\ge0}}}
\renewcommand{\emptyset}{\ensuremath{\varnothing}}

\renewcommand{\le}{\leqslant}
\renewcommand{\ge}{\geqslant}
\DeclareMathOperator{\logOR}{or}
\DeclareMathOperator{\logAND}{and}
\DeclareMathOperator{\Time}{Time}
\DeclareMathOperator{\Length}{Length}
\DeclareMathOperator{\Max}{Max}
\DeclareMathOperator{\NPclass}{NP}
\DeclareMathOperator{\Pclass}{P}
\newcommand{\mysim}[1]{\stackrel{#1}{\sim}}
\newcommand{\notmysim}[1]{\stackrel{#1}{\nsim}}
\newcommand{\Partitions}{{\mathcal{P}}}
\newcommand{\Colorings}{{\mathcal{C}}}
\newcommand{\eqdef}{\stackrel{\textrm{def}}{=}}

\tikzstyle{thickarrow}=[densely dashed,very thick]
\tikzstyle{edgeweight}=[circle,text centered,fill=lightblue]


%% Little modification of beamer: add advisor to title page
\makeatletter
\newcommand{\advisor}{\@dblarg\beamer@advisor}
\long\def\beamer@advisor[#1]#2{%
  \def\insertadvisor{#2}%
  \def\beamer@shortadvisor{#1}%
  }
\advisor{}

\setbeamertemplate{title page}
{
  \vbox{}
  \vfill
  \begin{centering}
    \begin{beamercolorbox}[sep=8pt,center]{title}
      \usebeamerfont{title}\inserttitle\par%
      \ifx\insertsubtitle\@empty%
      \else%
        \vskip0.25em%
        {\usebeamerfont{subtitle}\usebeamercolor[fg]{subtitle}\insertsubtitle\par}%
      \fi%
    \end{beamercolorbox}%
    \vskip1em\par
    \begin{beamercolorbox}[sep=8pt,center]{author}
      \usebeamerfont{author}\insertauthor
    \end{beamercolorbox}\vskip1em
    \begin{beamercolorbox}[sep=8pt,center]{advisor}
      \usebeamerfont{institute}{Руководитель: \insertadvisor}
    \end{beamercolorbox}
    \begin{beamercolorbox}[sep=8pt,center]{institute}
      \usebeamerfont{institute}\insertinstitute
    \end{beamercolorbox}
    \begin{beamercolorbox}[sep=8pt,center]{date}
      \usebeamerfont{date}\insertdate
    \end{beamercolorbox}\vskip0.5em
    {\usebeamercolor[fg]{titlegraphic}\inserttitlegraphic\par}
  \end{centering}
  \vfill
}
\makeatother
%% End of beamer-modification

\title[Жадное скрещивание разбиений]{Жадный алгоритм\\
устойчивого скрещивания разбиений}
\author{Т. С. Синяк}
\advisor{Е. А. Максименко}
\date{25 апреля 2008 г.}
\institute[ЮФУ]{Южный федеральный университет}
\keywords{разбиения множеств, скрещивание разбиений, генетические алгоритмы,
жадный алгоритм, расстояние между разбиениями}

\AtBeginSection[]{
\begin{frame}{План доклада}
\tableofcontents[currentsection]
\end{frame}
}

\begin{document}

\begin{frame}[label=titlepage]
\titlepage
\end{frame}

\begin{frame}{План доклада}
\tableofcontents
\end{frame}

\section{Введение}

\subsection{Пример задачи, связанной с перебором разбиений}

\begin{frame}[label=graphpart]{Пример задачи, связанной с перебором разбиений}
\framesubtitle{Разбиение графа с минимизацией связей между долями и несвязей внутри долей}

\begin{myproblem}
\begin{description}
\item[Дано:] неориентированный граф $G=(V,E)$.
\item[Найти:] разбиение $P$ множества вершин $V$, для которого\\
минимальна величина $B(V,E,P)+2C(V,E,P)$, где\\
$B(V,E,P)$~--- число отсутствующих связей внутри долей,\\
$C(V,E,P)$~--- число связей между долями.
\end{description}
\end{myproblem}

\begin{myexample}
\begin{tikzpicture}[scale=1,
baseline=(current bounding box.north)]
\tikzstyle{every node}=[circle,text centered,draw=black]
\tikzstyle{G}=[fill=mygreen]
\tikzstyle{Y}=[fill=lightyellow]
\tikzstyle{M}=[fill=lightblue]

\visible<1>{
\node[] (v6) at (0,0) {$6$};
\node[] (v3) at (0,-1.75) {$3$};
\node[] (v2) at (2,-1.75) {$2$};
\node[] (v4) at (-2,-1.75) {$4$};
\node[] (v1) at (1.5,-0.6) {$1$};
\node[] (v5) at (-1.5,-0.6) {$5$};
\node[] (v7) at (3,-0.8) {$7$};
}

\visible<2->{
\node[M] (v6) at (0,0) {$6$};
\node[Y] (v3) at (0,-1.75) {$3$};
\node[G] (v2) at (2,-1.75) {$2$};
\node[Y] (v4) at (-2,-1.75) {$4$};
\node[G] (v1) at (1.5,-0.6) {$1$};
\node[Y] (v5) at (-1.5,-0.6) {$5$};
\node[G] (v7) at (3,-0.8) {$7$};
}

\visible<1->{
\draw (v1) to (v2);
\draw (v1) to (v3);
\draw (v1) to (v7);
\draw (v2) to (v3);
\draw (v3) to (v4);
\draw (v3) to (v5);
\draw (v3) to (v6);
\draw (v4) to (v5);
}

\visible<3->{
\draw[red, thickarrow] (v2) to (v7);
}

\uncover<4->{
\draw[red, very thick] (v1) to (v3);
\draw[red, very thick] (v2) to (v3);
\draw[red, very thick] (v3) to (v6);
}

\end{tikzpicture}
\nolinebreak\qquad
\begin{minipage}[t]{5cm}
\visible<2->{$\{\{1,2,7\},\{3,4,5\},\{6\}\}$}\par\medskip
\visible<3->{$B=1$}\qquad\visible<4->{$C=3$}\par\medskip
\visible<5->{$B+2C=7$}
\end{minipage}
\end{myexample}

\end{frame}


\subsection{Генетические алгоритмы}

\begin{frame}[label=GA]{Генетические алгоритмы}

\begin{block}{Что такое ГА?}
Один из подходов к решению оптимизационных задач,\\
основанный на имитации биологической эволюции.\\
Достоинство ГА: достаточно быстро дают приближённое решение.
\end{block}

\begin{block}{Рассматриваемая схема ГА}
\begin{itemize}
\item мутация (заменяется не более $7\%$ генов в хромосоме)
\item скрещивание (родители выбираются с помощью рулетки)
\item отбор усечением (фиксируется максимальный объём популяции)
\end{itemize}
\end{block}

\begin{block}{Разбиения хранятся в виде раскрасок}
\begin{overlayarea}{\textwidth}{6ex}
\[
\texttt{\{\alert<2>{\{1\}},\alert<3>{\{2,5\}},\alert<4>{\{3,4,6\}}\}}
\quad\leftrightharpoons\quad
\only<1>{%
\texttt{%
\underline{\phantom{1}}\ \underline{\phantom{2}}\ \underline{\phantom{3}}\ %
\underline{\phantom{3}}\ \underline{\phantom{2}}\ \underline{\phantom{3}}%
}}
\only<2>{%
\texttt{%
\alert<2>{1}\ \underline{\phantom{2}}\ \underline{\phantom{3}}\ %
\underline{\phantom{3}}\ \underline{\phantom{2}}\ \underline{\phantom{3}}%
}}
\only<3>{%
\texttt{%
1\ \alert<3>{2}\ \underline{\phantom{3}}\ \underline{\phantom{3}}\ \alert<3>{2}\ \underline{\phantom{3}}%
}}
\only<4>{%
\texttt{%
1\ 2\ \alert<4>{3}\ \alert<4>{3}\ 2\ \alert<4>{3}%
}}
\]
\end{overlayarea}
\end{block}
\end{frame}

\subsection{Тривиальный алгоритм скрещивания разбиений}

\begin{frame}[label=cross]{Тривиальный алгоритм скрещивания разбиений}

\begin{block}{}
\only<1>{Разбиения хранятся в виде раскрасок:}
\only<2->{Обмен генами осуществляется с заданной вероятностью:}
\par\medskip
\visible<1->{
\begin{tabular}{@{}rcl@{}}
\texttt{\{1,2,3,4,5,6\}}
$\leftrightharpoons$
\texttt{1\alert<2->{1}\alert<2->{1}11\alert<2->{1}}& &
\visible<4->{%
\texttt{122112} $\rightleftharpoons$
\texttt{\{\{1,4,5\},\{2,3,6\}\}}
}
\\%
\only<2>{\texttt{обмен?}}\hfill%
\only<2>{\texttt{FTTFFT}}%
\only<3->{\phantom{0}$\updownarrow$$\updownarrow$\phantom{0}\phantom{0}$\updownarrow$}
& \visible<3->{\,$\mapsto$} &
\\
\texttt{\{\{1\},\{2,3,4,5,6\}\}} $\rightleftharpoons$
\texttt{1\alert<2->{2}\alert<2->{2}22\alert<2->{2}}& &
\visible<4->{%
\texttt{111221} $\rightleftharpoons$
\texttt{\{\{1,2,3,6\},\{4,5\}\}}
\end{tabular}
}
}
\end{block}

\begin{block}{Недостаток}<visible@5->
Плохо согласуется со структурой разбиений.
\end{block}

\end{frame}



\section{Жадный алгоритм устойчивого скрещивания разбиений}


\subsection{Геометрическое и устойчивое скрещивания}

\begin{frame}[label=defgeomcrossover]{Геометрическое и устойчивое скрещивания}

\begin{block}{}
Пусть \ $(X,d)$~--- метрическое пр-во,\quad
$(\Omega,\mu)$~--- вероятностное пр-во.\\
\[
  f\colon X\times X\times\Omega\to X,\qquad
  (a,b,\omega)\mapsto c.
\]
\end{block}

\begin{block}{Геометрическое скрещивание (Moraglio \& Poli, 2005)}
\[
  d(a,c)+d(c,b)=d(a,b)
\qquad
\begin{tikzpicture}[baseline={(0,0)}]
\draw[thick] (-2,-0.4)--(2,0.4);
\filldraw (-2,-0.4) \bigpoint;
\draw (-2,-0.4) node[anchor=east] {$a$};
\filldraw (2,0.4) \bigpoint;
\draw (2,0.4) node[anchor=west] {$b$};
\filldraw[color=red] (-1,-0.2) \bigpoint;
\draw (-1,-0.2) node[anchor=south] {$c$};
\end{tikzpicture}
\]
\end{block}

\begin{block}{$\alpha$-устойчивое скрещивание ($\alpha\ge1$)}
\[
  d(a,c)+d(c,b)\le \alpha d(a,b)
  \qquad
\begin{tikzpicture}[baseline={(0,0)}]
\filldraw[fill=ellipsecolor] ellipse(2 and 1.2);
\filldraw (-1.6,0) \bigpoint;
\draw (-1.6,0) node[anchor=north] {$a$};
\filldraw (1.6,0) \bigpoint;
\draw (1.6,0) node[anchor=north] {$b$};
\filldraw[color=red] (0.5,0.5) \bigpoint;
\draw (0.5,0.5) node[anchor=south] {$c$};
\end{tikzpicture}
\]
\end{block}
\end{frame}


\subsection{Расстояние между разбиениями}

\begin{frame}[label=distpart]{Расстояние между разбиениями}

\begin{block}{Определение расстояния между разбиениями (R\'egnier)}
\textcolor{red}{Расстояние} между разбиениями определяется как
минимальное число элементарных операций, необходимых
для превращения одного разбиения в другое.
Здесь элементарная операция~--- перемещение одного элемента
из одной доли в другую (возможно, пустую).
\end{block}

\begin{overlayarea}{\textwidth}{30ex}
\only<1>{
\begin{myexample}
$P=\{\{1,2,5\},\{3,4\}\},\quad Q=\{\{1,4\},\{2,5\},\{3\}\},\quad d(P,Q)=2$\\
$P=\{\{1,2,5\},\{3,4\}\}\to\{\{2,5\},\{1,3,4\}\}\to
\{\{2,5\},\{1,4\},\{3\}\}=Q$
\end{myexample}
}

\only<2->{
\begin{block}{Расстояние между разбиениями в терминах раскрасок}
Пусть $a,b$~--- раскраски множества $\{1,\ldots,n\}$.
Тогда
\[
d(P_a,P_b)=\min_{\varphi\in S_n}d_{H}(\varphi\circ a,b),
\]
где $d_{H}$~--- расстояние Хэмминга,\\
\qquad $S_n$~--- множество всех перестановок порядка $n$,\\
\qquad\qquad\ \ т.~е. биективных отображений множества $\{1,\ldots,n\}$ в себя.
\end{block}
}
\end{overlayarea}
\end{frame}

\subsection{Жадный алгоритм устойчивого скрещивания разбиений}

\begin{frame}[label=stablecross]{Жадный алгоритм устойчивого скрещивания разбиений}

\begin{columns}[T]

\begin{column}{3.3cm}
\vspace{0.35cm}
\begin{block}{Родители}
$a=(\alert<3,24>1,\alert<4,24>1,\alert<5,25>2,\alert<4,24>1,\alert<6,25>2,\alert<5,25>2)$\\
\medskip
$b=(\alert<3>1,\alert<4>2,\alert<5>3,\alert<4>2,\alert<6>2,\alert<5>3)$
\end{block}
\end{column}

\begin{column}{8.2cm}
\begin{overlayarea}{\textwidth}{45ex}
\only<2-8>{
\begin{block}{Граф для родителей}
\begin{center}
\begin{tikzpicture}

\node[circle,text centered,draw=black](x1) at (0,0.75) {1};
\node[circle,text centered,draw=black](x2) at (1,0.75) {2};
\node[circle,text centered,draw=black](x3) at (2,0.75) {3};
\node[circle,text centered,draw=black](x4) at (3,0.75) {4};
\node[circle,text centered,draw=black](x5) at (4,0.75) {5};
\node[circle,text centered,draw=black](x6) at (5,0.75) {6};

\node[circle,text centered,draw=black](y1) at (0,-0.75) {1};
\node[circle,text centered,draw=black](y2) at (1,-0.75) {2};
\node[circle,text centered,draw=black](y3) at (2,-0.75) {3};
\node[circle,text centered,draw=black](y4) at (3,-0.75) {4};
\node[circle,text centered,draw=black](y5) at (4,-0.75) {5};
\node[circle,text centered,draw=black](y6) at (5,-0.75) {6};


\pgfsetshapeinnerysep{0pt}
\visible<3->{
\draw[->](x1) -- node[edgeweight]{\tiny 1} (y1);
}
\visible<4->{
\draw[->](x1) -- node[edgeweight]{\tiny 2} (y2);
}
\visible<5->{
\draw[->](x2) to node[edgeweight]{\tiny 2} (y3);
}
\visible<6->{
\draw[->](x2) to node[edgeweight]{\tiny 1} (y2);
}

\end{tikzpicture}
\end{center}
\end{block}
}

\only<7>{
\begin{block}{Задача о максимальном паросочетании}
Теперь в построенном графе нужно найти максимальное 
(по весу) паросочетание.\\
Точные алгоритмы решают эту задачу сравнительно долго,
поэтому рассмотрим приближённый жадный алгоритм,\\
работающий за время $O(n\log n)$.
\end{block}
}


\only<8-13>{
\begin{block}{Граф для родителей в виде массива троек
(вес дуги, начало, конец)}
\[
T=((1,1,1),(2,1,2),(1,2,2),(2,2,3))
\]
\end{block}
}

\only<10-13>{
\begin{block}{Массив троек, отсортированный  в порядке
убывания весов}
\[
T=(\txtred<12>{(\alert<10>2,1,2)},\txtred<13>{(\alert<10>2,2,3)},\colorhide<12->{(\alert<10>1,1,1)},
\colorhide<12->{(\alert<10>1,2,2)})
\]
\end{block}
}

\only<11-21>{
\begin{block}{Паросочетание}
\[
\only<11>{
M=\varnothing\vphantom{\{}\phantom{0\,(2,3)(1,2)}
}
\only<12>{
M=\{\alert<12>{(1,2)}\}\phantom{,(2,3)}
}
\only<13>{
M=\{(1,2),\alert<13>{(2,3)}\}
}
\only<14->{
M=\{\alert<16>{(1,2)},\alert<17>{(2,3)}\}
}
\]
\end{block}
}


\only<15-25>{
\begin{block}{Cоответствие для $a$ и $b$}
\[
\varphi=\left(
\begin{array}{@{}c@{}c@{}c@{}c@{}c@{}c@{}}
\alert<24>1&\alert<25>2&3&4&5&6\\
\visible<16->{\downarrow}&\visible<17->{\downarrow}&\visible<18->{\downarrow}&\visible<19->{\downarrow}&\visible<20->{\downarrow}&\visible<21->{\downarrow}\\
\visible<16->{\txtblue<24>2}&\visible<17->{\txtblue<25>3}&\visible<18->{1}&\visible<19->{4}&\visible<20->{5}&\visible<21->6
\end{array}
\right)
\]
\only<16-17>{
Из паросочетания строим инъекцию.
}
\only<18-21>{
Достраиваем инъекцию до биекции.
}
\end{block}
}

\only<23-25>{
\begin{block}{Изменение родителя согласно соответствию}
\begin{overlayarea}{\textwidth}{16ex}
\[
\tilde{a}=\varphi\circ a
\]
\only<23>{
\[
\tilde{a}=(\underline{\phantom{2}},
           \underline{\phantom{2}},
           \underline{\phantom{3}},
           \underline{\phantom{2}},
           \underline{\phantom{3}},
           \underline{\phantom{3}})
\]
}
\only<24>{
\[
\tilde{a}=(\txtblue<24>2,
           \txtblue<24>2,
           \underline{\phantom{3}},
           \txtblue<24>2,
           \underline{\phantom{3}},
           \underline{\phantom{3}})
\]
}
\only<25>{
\[
\tilde{a}=(2,2,\txtblue<25>3,2,\txtblue<25>3,\txtblue<25>3)
\]
}
\end{overlayarea}
\end{block}
}

\only<26->{
\begin{block}{Изменение родителя согласно соответствию}
\[
\tilde{a}=(2,2,3,2,3,3)
\]
\end{block}
}

\only<27->{
\begin{block}{Тривиальное скрещивание $\tilde{a}$ и $b$}
\begin{center}
\begin{tabular}{@{}l@{}l@{}}
$\tilde{a}=$ & $(\alert<25->2,2,\alert<25->3,\alert<25->2,3,3)$\\
 & \phantom{(}$\updownarrow$\phantom{,,00}$\updownarrow$\phantom{0}$\updownarrow$\\
$b=$ & $(\alert<25->1,2,\alert<25->3,\alert<25->2,2,3)$
\end{tabular}
\end{center}
\end{block}
}

\only<28->{
\begin{block}{Потомки}
\[
c=(1,2,3,2,3,3)
\]
\[
d=(2,2,3,2,2,3)
\]
\end{block}
}
\end{overlayarea}

\end{column}

\end{columns}
\end{frame}



\subsection{Свойство жадного алгоритма}

\begin{frame}{Свойство жадного алгоритма}

\begin{block}{Теорема}
Пусть%
\quad\ $P,Q$~--- разбиения множества $\{1,\ldots,n\}$,\\
\qquad\qquad$S,T$~--- потомки, построенные жадным алгоритмом,\\
\qquad\qquad$d_{g}(P,Q)$~--- приближённое расстояние между $P$ и $Q$,\\
\qquad\qquad\qquad\qquad\quad\  найденное жадным алгоритмом.\\
Тогда\\
\qquad $d(P,S)+d(S,Q)=d(P,T)+d(T,Q)=d_{g}(P,Q)\le 2d(P,Q)$.
\end{block}

\begin{block}{Результаты для $n=7$ ($877$ разбиений)}
\begin{tikzpicture}[xcomb,xscale=0.1,yscale=0.42, baseline=(current bounding box.west)]

\tikzstyle{plotline}=[line width=0.3cm,color=darkgreen]

\draw[style=plotline] plot coordinates {(84,0) (15,1) (1,2) (0,3)};

\draw (84.5,0) node[anchor=west] {$84\%$};
\draw (15.5,1) node[anchor=west] {$15\%$};
\draw (1.5,2) node[anchor=west] {$1\%$};

\draw[->] (0,-1)--(0,4);
\draw (0,3.8) node[anchor=west] {$\Delta d=d_g-d$};
\foreach \xpos in {0,1,2,3}
  \draw (-.5,\xpos) node[anchor=east]{$\xpos$};
\end{tikzpicture}
\end{block}
\end{frame}



\section{Экспериментальные результаты}

\begin{frame}[label=results]{Результаты для задачи о наилучшем разбиении графа}

\begin{myproblem}
\begin{description}
\item[Дано:] неориентированный граф $G=(V,E)$.
\item[Найти:] разбиение $P$ мн-ва $V$:
$B(V,E,P)+2C(V,E,P)\to\min$.
\end{description}
\end{myproblem}

\begin{block}{}
\begin{tikzpicture}[ycomb,xscale=1.3,yscale=0.5, baseline=(current bounding box.west)]

\tikzstyle{plotline}=[line width=0.5cm,color=darkgreen]

%\draw[style=plotline] plot coordinates {(0.5,1) (1.5,2) (2.5,3) (3.5,4)};

\draw[style=plotline] plot coordinates {(0.5,6.13) (1.5,6.23) (2.5,6.67) (3.5,6.72)};

\draw (0.5,6.13) node[above] {$612.8$};
\draw (1.5,6.23) node[above] {$622.7$};
\draw (2.5,6.67) node[above] {$666.8$};
\draw (3.5,6.72) node[above] {$672.3$};

\draw[->] (0,0)--(0,7);
\draw (0,7) node[anchor=east] {$B+2C$};

\draw[->] (0,0)--(4,0);

\draw (0.5,0) node[anchor=north]{$\substack{\displaystyle\text{Уст.}\\\displaystyle\text{скрещ.}}$};
\draw (1.5,0) node[anchor=north]{$\substack{\displaystyle\text{Трив.}\\\displaystyle\text{скрещ.}}$};
\draw (2.5,0) node[anchor=north]{$\substack{\displaystyle\text{Мут.}\\\displaystyle\text{без}\\\displaystyle\text{скрещ.}}$};
\draw (3.5,0) node[anchor=north]{$\substack{\displaystyle\text{Монте-}\\\displaystyle\text{Карло}}$};
\end{tikzpicture}
\quad\nolinebreak
\begin{minipage}{4.5cm}
%\begin{block}{}
$|V|=50$\\
$\text{Плотность графа}=0.5$\\
$\text{Размер популяции}=60$\\
$\text{Вер-ть мутации}=0.07$\\
$\text{Вер-ть скрещивания}=0.6$
%\end{block}
\end{minipage}
\end{block}

\end{frame}


\begin{frame}{Источники}

\begin{thebibliography}{2}

\beamertemplatebookbibitems
\bibitem{GareyJohnson}
\textsc{Гэри~М., Джонсон~Д.}\\
Вычислительные машины и труднорешаемые задачи.~---
М.: <<Мир>>, 1982.

\beamertemplatearticlebibitems
\bibitem{DenoeudGuenoche_DistancePartition}
\textsc{L.~Denoeud et A.~Guenoche.}\\
Distance des transferts entre partitions.~--- 5~p.

\beamertemplatearticlebibitems
\bibitem{Denoeud_Comparison_distance_partition}
\textsc{L.~Denoeud, H.~Garreta and A.~Guenoche.}\\
Comparison of distancce indices between partitions.~--- 9~p.

\beamertemplatearticlebibitems
\bibitem{SaipLucchesi}
\textsc{H.~A.~Baier~Saip, C.~L.~Lucchesi.}\\
Matching algorithms for bipartite graphs.~---
Relat\'orio T\'ecnico DCC~---
03/93.

\beamertemplatearticlebibitems
\bibitem{PoliMoraglio}
\textsc{A.~Moraglio and R.~Poli.}\\
Geometric crossover for sets, multisets and partitions.~---
Department of Computer Science,
University of Essex, 2005.~--- 10~p.

\end{thebibliography}

\end{frame}


\begin{frame}[label=end]
\vfill
\begin{center}
\textcolor{MidnightBlue}{Спасибо за внимание!}
\end{center}
\vfill
\end{frame}

\end{document}
