\documentclass[fullscreen=true,unicode,bookmarks=false]{beamer}
\usetheme{default}
%\includeonlyframes{showGA}

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

\definecolor{MidnightBlue}{rgb}{0.2,0.2,0.7}
\definecolor{myblue}{rgb}{0.2,0.5,0.9}
\definecolor{mygreen}{rgb}{0.7,1,0.7}
\definecolor{darkgreen}{rgb}{0,0.5,0}
\definecolor{greenyellow}{rgb}{0.8,1,0.6}
\definecolor{yellow}{rgb}{1,1,0.7}
\definecolor{lightgray}{rgb}{0.9,0.9,0.9}
\newcommand<>{\srccell}{\only#1{\color{darkgreen}}}
\newcommand<>{\blccell}{\only#1{\color{black}}}
\newcommand<>{\btxtcell}{\only#1{\textcolor{darkgreen}}}
\newcommand<>{\rtxtcell}{\only#1{\textcolor{red}}}
\newcommand<>{\rescell}{\only#1{\color{red}}}
\newcommand<>{\colorhide}{\only#1{\color{lightgray}}}

\DeclareMathOperator{\IndSets}{IndSets}

\newcommand{\Neighbors}{\Gamma}
\newcommand{\microsection}[1]{{\color{MidnightBlue}#1}}
\newcommand{\recarrow}{\tikz \draw[->] (2ex,0ex) .. controls (0ex,0ex) .. (0ex,2ex);}

\title{Некоторые методы решения задачи о максимальном независимом множестве}
\subtitle{Учебная презентация}
\author{{Т. С. Синяк} \and {Е. А. Максименко}}
\institute{Южный федеральный университет}

\hypersetup{pdfkeywords={максимальное независимое множество,
maximal independent set, алгоритм Брона-Кербоша,
метод ветвей и границ, генетический алгоритм
%, Bron-Kerbosch's algorithm,
%branch and bound algorithm, genetic algorithm
}}

\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}{Неориентированный граф, смежность}
Пусть $G=(V,E)$~--- неориентированный граф\\с множеством вершин
$V(\neq\varnothing)$ и множеством рёбер $E(\subset C_V^2)$,\\где
$C_V^2=\{\{u,v\}\colon u,v\in V,\ u\ne v\}$~--- множество
двухэлементных подмножеств множества $V$.\\
\begin{tikzpicture}[scale=1, baseline=(current bounding
box.north)]
\tikzstyle{every node}=[circle,text centered,draw=black]
\tikzstyle{M}=[fill=mygreen] \tikzstyle{V}=[fill=yellow]

\visible<1>{

\node[] (v1) at (-1,0) {$1$};
\node[] (v2) at (0.2,0) {$2$};
\node[] (v3) at (1.4,0) {$3$};
\node[] (v4) at (1.4,-1.2) {$4$};
\node[] (v5) at (0.2,-1.2) {$5$};
\node[] (v6) at (-1,-1.2) {$6$};}

\visible<2>{

\node[] (v1) at (-1,0) {$1$};
\node[] (v2) at (0.2,0) {$2$};
\node[M] (v3) at (1.4,0) {$3$};
\node[M] (v4) at (1.4,-1.2) {$4$};
\node[] (v5) at (0.2,-1.2) {$5$};
\node[] (v6) at (-1,-1.2) {$6$};}

\visible<3>{

\node[] (v1) at (-1,0) {$1$};
\node[] (v2) at (0.2,0) {$2$};
\node[M] (v3) at (1.4,0) {$3$};
\node[V] (v4) at (1.4,-1.2) {$4$};
\node[M] (v5) at (0.2,-1.2) {$5$};
\node[] (v6) at (-1,-1.2) {$6$};}

\visible<4>{

\node[V] (v1) at (-1,0) {$1$};
\node[M] (v2) at (0.2,0) {$2$};
\node[M] (v3) at (1.4,0) {$3$};
\node[V] (v4) at (1.4,-1.2) {$4$};
\node[M] (v5) at (0.2,-1.2) {$5$};
\node[] (v6) at (-1,-1.2) {$6$};}

\draw (v1) to (v2);
\draw (v2) to (v3);
\draw (v2) to (v5);
\draw (v3) to (v4);
\draw (v4) to (v5);
\draw (v5) to (v6);

\end{tikzpicture}
\nolinebreak\quad
\begin{minipage}[t]{5cm}
\par\medskip
\only<3>{
$u=4$\\
$\Neighbors(4)=\{3,5\}$}
\only<4>{
$V'=\{1,4\}$\\
$\Neighbors(V')=\{2,3,5\}$\\}
\end{minipage}
\par\medskip
\visible<2->{Вершины $u$ и $v$ называют \emph{смежными
(соседними)} в графе $G$, если $\{u,v\}\in E$.}
\par\medskip
\visible<3->{$\Neighbors(u)$~--- множество всех вершин, смежных с вершиной $u$.}
\par\medskip
\visible<4->{$\Neighbors(V')\quad(V'\subset V)$~--- множество
всех вершин, соседних с вершинами из $V'$:\\
\qquad\qquad\qquad\qquad $\Neighbors(V') = \cup
\{\Neighbors(v)\colon v\in V'\}$}
\end{frame}

\subsection{Определение независимого множества}
\begin{frame}{Определение независимого множества}
Пусть $G=(V,E)$~--- неориентированный граф.\\\medskip

Множество $M\subset V$ называют \emph{независимым множеством} в
графе $G$, если $\forall u,v\in M\quad \{u,v\}\notin E$.\\\medskip

Другими словами, если $M\cap\Neighbors(M) = \varnothing$.\\\medskip

\visible<2->{Множество всех
независимых множеств в графе $G$ обозначим через $\IndSets(G)$.\\}

\visible<3->{
\begin{tikzpicture}[scale=1, baseline=(current bounding box.north)]
\tikzstyle{every node}=[circle,text centered,draw=black]
\tikzstyle{M}=[fill=mygreen]

\visible<3>{

\node[M] (v1) at (0,0) {$1$};
\node[] (v2) at (2,0) {$2$};
\node[M] (v3) at (4,0) {$3$};
\node[M] (v4) at (1,-1) {$4$};
\node[] (v5) at (3,-1) {$5$};
\node[] (v6) at (5,-1) {$6$};}

\visible<4>{

\node[] (v1) at (0,0) {$1$};
\node[M] (v2) at (2,0) {$2$};
\node[] (v3) at (4,0) {$3$};
\node[] (v4) at (1,-1) {$4$};
\node[M] (v5) at (3,-1) {$5$};
\node[] (v6) at (5,-1) {$6$};}

\visible<5-6>{

\node[] (v1) at (0,0) {$1$};
\node[M] (v2) at (2,0) {$2$};
\node[] (v3) at (4,0) {$3$};
\node[] (v4) at (1,-1) {$4$};
\node[M] (v5) at (3,-1) {$5$};
\node[M] (v6) at (5,-1) {$6$};}

\draw (v1) to (v2);
\draw (v2) to (v4);
\draw (v2) to (v3);
\draw (v4) to (v5);
\draw (v5) to (v3);
\draw (v3) to (v6);
\end{tikzpicture}}
\nolinebreak\qquad
\begin{minipage}[t]{4cm}
\visible<3->{$\{1,3,4\}\in\IndSets(G)$}\\
\visible<4->{$\{2,5\}\in\IndSets(G)$}\\
\visible<5->{$\{2,5,6\}\in\IndSets(G)$}\\
\visible<5->{$\;\ldots\ldots$}
\end{minipage}
\par\medskip
\visible<3>{Рассмотрим пример.\\}
\visible<6->{Независимые множества можно сравнивать\\
по числу элементов: $\#\{2,5\}<\#\{1,3,4\}$\\
и по включению: $\{2,5\}\subset\{2,5,6\}$.}
\end{frame}

\subsection{Формулировка задачи и пример}
\begin{frame}{Формулировка задачи}

Дано: неориентированный граф $G(V,E)$.\\\medskip

Задача: найти максимальное по числу элементов независимое
множество в графе $G$.\\\medskip

\begin{tikzpicture}[scale=1, baseline=(current bounding
box.north)]

\tikzstyle{every node}=[circle,text centered,draw=black]
\tikzstyle{M}=[fill=mygreen]

\visible<1>{

\node[M] (v1) at (0,0) {$1$};
\node[] (v2) at (1,0) {$2$};
\node[] (v3) at (3,0) {$3$};
\node[M] (v4) at (4,0) {$4$};
\node[] (v5) at (2,-2) {$5$};
\node[M] (v6) at (2,-1) {$6$};
\node[M] (v7) at (2,1) {$7$};
\node[] (v8) at (2,2) {$8$}; }

\visible<2>{

\node[] (v1) at (0,0) {$1$};
\node[] (v2) at (1,0) {$2$};
\node[] (v3) at (3,0) {$3$};
\node[] (v4) at (4,0) {$4$};
\node[M] (v5) at (2,-2) {$5$};
\node[M] (v6) at (2,-1) {$6$};
\node[M] (v7) at (2,1) {$7$};
\node[M] (v8) at (2,2) {$8$}; }

\visible<3>{

\node[] (v1) at (0,0) {$1$};
\node[M] (v2) at (1,0) {$2$};
\node[M] (v3) at (3,0) {$3$};
\node[] (v4) at (4,0) {$4$};
\node[M] (v5) at (2,-2) {$5$};
\node[] (v6) at (2,-1) {$6$};
\node[] (v7) at (2,1) {$7$};
\node[M] (v8) at (2,2) {$8$}; }

\draw (v1) to (v2);
\draw (v1) to (v5);
\draw (v1) to (v8);
\draw (v3) to (v4);
\draw (v4) to (v5);
\draw (v4) to (v8);
\draw (v2) to (v6);
\draw (v2) to (v7);
\draw (v3) to (v6);
\draw (v3) to (v7);
\end{tikzpicture}
\nolinebreak\quad
\begin{minipage}[t]{5cm}
Максимальное независимое множество:\quad $\{1,4,6,7\}$
\par\medskip
\visible<2->{Есть и другие максимальные независимые множества:}\\
\visible<2->{\qquad\qquad\qquad $\{5,6,7,8\}$}\\
\visible<3->{\qquad\qquad\qquad $\{2,3,5,8\}$}
\end{minipage}
\end{frame}

\section{Точные методы решения}

\subsection{Алгоритм Брона-Кербоша}

\begin{frame}{Алгоритм Брона-Кербоша: основные объекты}
Находит все максимальные по включению независимые множества.\\
\medskip
На каждом шаге алгоритма множество $V$ разбито на четыре части:\\
\medskip
$M$ \visible<2->{~--- текущее независимое множество;}\\
\medskip
$\Neighbors(M)$ \visible<3->{~--- множество вершин, смежных с $M$;}\\
\medskip
$K$ \visible<4->{~--- множество кандидатов, т.~е. вершин,
каждая из которых может быть добавлена в $M$;}\\
\medskip
$P$ \visible<5->{~--- множество просмотренных вершин, каждая из которых не может быть добавлена в текущее $M$, 
так как уже добавлялась ранее.}
\end{frame}

\begin{frame}{Алгоритм Брона-Кербоша: демонстрация}
\begin{tabular}{@{}lr@{}}
\begin{tabular}{@{}r@{}|c|c|c|c@{}}
& $M$ & $K$ & $P$ & $v$\\
\cline{2-5}

\uncover<19,20,21>{$\rightarrow$}& $\varnothing$ &
\srccell<20>\btxtcell<2,3,5>1, 2, \btxtcell<5>3, \btxtcell<5>4 &
\srccell<6,21>$\varnothing$ &
\visible<2->{\srccell<5,6,20,21>\rescell<2,3>1}
\\

\visible<4->{ \uncover<15,16,17>{$\rightarrow$}& 1 &
\rescell<5>\srccell<8,9,11,16>\visible<5->{2}&
\rescell<6>\srccell<12,17>\visible<6->{$\varnothing$}&
\srccell<11,12,16,17>\rescell<8,9>\visible<8->{2}}
\\

\visible<10->{\uncover<14->{$\blacktriangleright$}& 1, 2 &
\rescell<11>\visible<11->{$\varnothing$}&
\rescell<12>\visible<12->{$\varnothing$}
\\\cline{2-5}}

\visible<15-> { & 1 & \rescell<16>\visible<16->{$\varnothing$}&
\rescell<17>\visible<17->2 &
\\\cline{2-5}}

\visible<19->{ \uncover<28>{$\rightarrow$}& $\varnothing$ &
\rescell<20>\visible<20->{\btxtcell<23,24>2, 3, 4} &
\rescell<21>\visible<21->1 & \rescell<23,24>\visible<23->2}
\\

\visible<25->{ \uncover<27>{$\rightarrow$}& 2 & 3 & 1 & 3}
\\

\visible<26->{ \uncover<26->{$\blacktriangleright$}& 2, 3 &
$\varnothing$ & $\varnothing$&
\\
\cline{2-5}}

\visible<27->{ & 2 & $\varnothing$ & 1, 3 &
\\
\cline{2-5}}

\visible<28->{ \uncover<30>{$\rightarrow$}& $\varnothing$ & 3, 4 &
1, 2 & 3}
\\

\visible<29->{ & 3 & $\varnothing$ & 2 &
\\
\cline{2-5}}

\visible<30->{ \uncover<32>{$\rightarrow$}& $\varnothing$ & 4 & 1,
2, 3 & 4}
\\
\visible<31->{ \uncover<31->{$\blacktriangleright$}& 4 &
$\varnothing$ & $\varnothing$ &
\\
\cline{2-5}}

\visible<32->{ & $\varnothing$ & $\varnothing$ & 1, 2, 3, 4 &}
\end{tabular}
&
\begin{tabular}{@{}l@{}}
\qquad
\begin{tikzpicture}[scale=1]
\tikzstyle{every node}=[circle,text centered,draw=black]
\tikzstyle{M}=[fill=mygreen]
\tikzstyle{K}=[fill=yellow]
\tikzstyle{P}=[fill=lightgray]

\visible<1-3,19>{

\node[K] (v1) at (0,0) {$3$};
\node[K] (v2) at (1.5,1) {$2$};
\node[K] (v3) at (0,1) {$1$};
\node[K] (v4) at (1.5,0) {$4$}; }

\visible<4>{

\node[K] (v1) at (0,0) {$3$};
\node[K] (v2) at (1.5,1) {$2$};
\node[M] (v3) at (0,1) {$1$};
\node[K] (v4) at (1.5,0) {$4$};}

\visible<5-9,15>{

\node[] (v1) at (0,0) {$3$};
\node[K] (v2) at (1.5,1) {$2$};
\node[M] (v3) at (0,1) {$1$};
\node[] (v4) at (1.5,0) {$4$}; }

\visible<10-14>{

\node[] (v1) at (0,0) {$3$};
\node[M] (v2) at (1.5,1) {$2$};
\node[M] (v3) at (0,1) {$1$};
\node[] (v4) at (1.5,0) {$4$}; }

\visible<16>{

\node[] (v1) at (0,0) {$3$};
\node[] (v2) at (1.5,1) {$2$};
\node[M] (v3) at (0,1) {$1$};
\node[] (v4) at (1.5,0) {$4$}; }

\visible<17,18>{

\node[] (v1) at (0,0) {$3$};
\node[P] (v2) at (1.5,1) {$2$};
\node[M] (v3) at (0,1) {$1$};
\node[] (v4) at (1.5,0) {$4$}; }

\visible<20>{

\node[K] (v1) at (0,0) {$3$};
\node[K] (v2) at (1.5,1) {$2$};
\node[] (v3) at (0,1) {$1$};
\node[K] (v4) at (1.5,0) {$4$}; }

\visible<21-24>{

\node[K] (v1) at (0,0) {$3$};
\node[K] (v2) at (1.5,1) {$2$};
\node[P] (v3) at (0,1) {$1$};
\node[K] (v4) at (1.5,0) {$4$}; }

\visible<25>{

\node[K] (v1) at (0,0) {$3$};
\node[M] (v2) at (1.5,1) {$2$};
\node[P] (v3) at (0,1) {$1$};
\node[] (v4) at (1.5,0) {$4$}; }

\visible<26>{

\node[M] (v1) at (0,0) {$3$};
\node[M] (v2) at (1.5,1) {$2$};
\node[] (v3) at (0,1) {$1$};
\node[] (v4) at (1.5,0) {$4$}; }

\visible<27>{

\node[P] (v1) at (0,0) {$3$};
\node[M] (v2) at (1.5,1) {$2$};
\node[P] (v3) at (0,1) {$1$};
\node[] (v4) at (1.5,0) {$4$}; }

\visible<28>{

\node[K] (v1) at (0,0) {$3$};
\node[P] (v2) at (1.5,1) {$2$};
\node[P] (v3) at (0,1) {$1$};
\node[K] (v4) at (1.5,0) {$4$}; }

\visible<29>{

\node[M] (v1) at (0,0) {$3$};
\node[P] (v2) at (1.5,1) {$2$};
\node[] (v3) at (0,1) {$1$};
\node[] (v4) at (1.5,0) {$4$}; }

\visible<30>{

\node[P] (v1) at (0,0) {$3$};
\node[P] (v2) at (1.5,1) {$2$};
\node[P] (v3) at (0,1) {$1$};
\node[K] (v4) at (1.5,0) {$4$}; }

\visible<31>{

\node[] (v1) at (0,0) {$3$};
\node[] (v2) at (1.5,1) {$2$};
\node[] (v3) at (0,1) {$1$};
\node[M] (v4) at (1.5,0) {$4$}; }

\visible<32>{

\node[P] (v1) at (0,0) {$3$};
\node[P] (v2) at (1.5,1) {$2$};
\node[P] (v3) at (0,1) {$1$};
\node[P] (v4) at (1.5,0) {$4$}; }

\draw (v1) to (v4);
\draw (v1) to (v3);
\draw (v2) to (v4);
\draw (v3) to (v4);
\end{tikzpicture}
\\
\srccell<1,7,13,18,22>while K != $\varnothing$ or M != $\varnothing$:\\
\quad if K != $\varnothing$:\\
\srccell<2,8,23>\qquad v = K.first\\
\srccell<3,9,24>\qquad push M, K, P, v\\
\srccell<4,10,25>\qquad M = M + \{v\}\\
\srccell<5,11,25>\qquad K = K -- $\Neighbors$(v) -- \{v\}\\
\srccell<6,12,25>\qquad P = P -- $\Neighbors$(v)\\
\quad else:\\
\srccell<14>\qquad if P == $\varnothing$: вывод M\\
\srccell<15,19>\qquad pop v, P, K, M\\
\srccell<16,20>\qquad K = K -- \{v\}\\
\srccell<17,21>\qquad P = P + \{v\}
\end{tabular}
\end{tabular}
\visible<14->{Вывод: \{1,2\}} \visible<26->{, \{2,3\}}
\visible<31->{, \{4\}}
\end{frame}

\subsection{Метод ветвей и границ}

\begin{frame}[label=branchs]{Метод ветвей и границ: описание}
Находит максимальное независимое множество в графе $G$.\\\medskip
\texttt{static G, record = 0, M\_rec = $\varnothing$}\\
\texttt{procedure MaxIndSet(M, K):}\\
\quad \texttt{while K != $\varnothing$:}\\
\qquad \texttt{v = K.first}\\
\qquad \texttt{if \#M + \#(K -- $\Neighbors$(v)) > record:}\\
\qquad\quad \texttt{MaxIndSet(M + v, K -- v -- $\Neighbors$(v))}\\
\qquad \texttt{K --= v}\\
\quad \texttt{if \#M > record:}\\
\qquad \texttt{record = \#M}\\
\qquad \texttt{M\_rec = M}\\
\medskip
Обозначения:\qquad\texttt{M}~--- текущее независимое множество;\\
\qquad\qquad\qquad\qquad\texttt{K}~--- множество кандидатов;\\
\qquad\qquad\qquad\qquad\texttt{record}~--- максимальное число элементов\\
\qquad\qquad\qquad\qquad среди просмотренных \texttt{M};\\
\qquad\qquad\qquad\qquad\texttt{X.first}~--- первый элемент в \texttt{X}.
\end{frame}

\begin{frame}[label=branch]{Метод ветвей и границ: демонстрация}
\vphantom{$\{1\}$}
\only<1-5>{record = 0,\qquad M\_rec = $\varnothing$}
\only<6-11>{record = 2,\qquad M\_rec = $\{1,2\}$}
\only<12-28>{record = 3,\qquad M\_rec = $\{1,4,5\}$}

\par\medskip
\begin{tabular}{lr@{}}
\begin{minipage}[t]{6.5cm}
\visible<1->{%
\vphantom{$\{1\}$}%
M = $\varnothing$,%
\quad%
\only<1-18>{K = $\{\rtxtcell<2,18>1,2,3,4,5\}$}%
\only<19,20>{K = $\{\rtxtcell<20>2,3,4,5\}$}%
\only<21,22>{K = $\{\rtxtcell<22>3,4,5\}$}%
\only<23,24>{K = $\{\rtxtcell<24>4,5\}$}%
\only<25,26>{K = $\{\rtxtcell<26>5\}$}%
\only<27-28>{K = $\varnothing$}%
}\\
\visible<3->{%
\vphantom{$\{1\}$}%
\visible<18>{\recarrow}%
\;%
\visible<3-18>{M = $\{1\}$,}%
\only<3-6>{\quad K = $\{\rtxtcell<4,6>2,4,5\}$}%
\only<7-14>{\quad K = $\{\rtxtcell<8,14>4,5\}$}%
\only<15,16>{\quad K = $\{\rtxtcell<16>5\}$}%
\only<17,18>{\quad K = $\varnothing$}%
}\\
\visible<5->{%
\vphantom{$\{1\}$}%
{\quad}%
\visible<6,14>{\recarrow}%
\;%
\only<5,6>{M = $\{1,2\}$,}%
\only<9-14>{M = $\{1,4\}$,}%
{\quad}%
\only<5,6,13,14>{K = $\varnothing$}%
\only<9-12>{K = $\{\rtxtcell<10,12>5\}$}%
}\\
\visible<11,12>{%
\vphantom{$\{1\}$}%
{\qquad}%
\visible<12>{\recarrow}\;%
M = $\{1,4,5\}$,%
{\quad}%
K = $\varnothing$%
}\\
\begin{overlayarea}{\textwidth}{6ex}
\vphantom{$\{v\}$}
\only<2,4,8,10,16,20,22,24,26>{v = K.first\\
\#M + \#(K -- $\Neighbors(v)$) > record:\\}%
\only<2>{\phantom{00000}K -- $\Neighbors(v)$ = $\{1,2,4,5\}$\\}%
\only<4,20>{\phantom{00000}K -- $\Neighbors(v)$ = $\{2\}$\\}%
\only<8,24>{\phantom{00000}K -- $\Neighbors(v)$ = $\{4,5\}$\\}%
\only<10,16,26>{\phantom{00000}K -- $\Neighbors(v)$ = $\{5\}$\\}%
\only<22>{\phantom{00000}K -- $\Neighbors(v)$ = $\{3,4,5\}$\\}%
\only<2>{\phantom{00000}$0+4>0$}
\only<4>{\phantom{00000}$1+1>0$}
\only<8>{\phantom{00000}$1+2>2$}
\only<10>{\phantom{00000}$2+1>2$}
\only<16>{\phantom{00000}$1+1\ngtr3$\\}
\only<20>{\phantom{00000}$0+1\ngtr3$\\}
\only<22>{\phantom{00000}$0+3\ngtr3$\\}
\only<24>{\phantom{00000}$0+2\ngtr3$\\}
\only<26>{\phantom{00000}$0+1\ngtr3$\\}
\only<3,5,9,11>{
M = M + $\{v\}$\\
K = K -- $\{v\}$ -- $\Neighbors(v)$
}
\only<6,12,14,16,18,20,22,24,26>{K = K -- $\{v\}$}
\only<27-28>{Вывод: $\{1,4,5\}$.}
\end{overlayarea}
\end{minipage}
&
\begin{tikzpicture}[scale=1, baseline=(current bounding
box.north)]
\tikzstyle{every node}=[circle,text
centered,draw=black]
\tikzstyle{M}=[fill=mygreen]
\tikzstyle{K}=[fill=yellow]
\visible<1,2,18>{
\node[K] (v1) at (0,1.5) {$1$};
\node[K] (v2) at (0,0) {$2$};
\node[K] (v3) at (1.5,1.5) {$3$};
\node[K] (v4) at (1.5,0) {$4$};
\node[K] (v5) at (1.5,-1.5) {$5$};}
\visible<3,4,6>{
\node[M] (v1) at (0,1.5) {$1$};
\node[K] (v2) at (0,0) {$2$};
\node[] (v3) at (1.5,1.5) {$3$};
\node[K] (v4) at (1.5,0) {$4$};
\node[K] (v5) at (1.5,-1.5) {$5$};}
\visible<5>{
\node[M] (v1) at (0,1.5) {$1$};
\node[M] (v2) at (0,0) {$2$};
\node[] (v3) at (1.5,1.5) {$3$};
\node[] (v4) at (1.5,0) {$4$};
\node[] (v5) at (1.5,-1.5) {$5$};}
\visible<7,8,14>{
\node[M] (v1) at (0,1.5) {$1$};
\node[] (v2) at (0,0) {$2$};
\node[] (v3) at (1.5,1.5) {$3$};
\node[K] (v4) at (1.5,0) {$4$};
\node[K] (v5) at (1.5,-1.5) {$5$};}
\visible<9,10,12>{
\node[M] (v1) at (0,1.5) {$1$};
\node[] (v2) at (0,0) {$2$};
\node[] (v3) at (1.5,1.5) {$3$};
\node[M] (v4) at (1.5,0) {$4$};
\node[K] (v5) at (1.5,-1.5) {$5$};}
\visible<11>{
\node[M] (v1) at (0,1.5) {$1$};
\node[] (v2) at (0,0) {$2$};
\node[] (v3) at (1.5,1.5) {$3$};
\node[M] (v4) at (1.5,0) {$4$};
\node[M] (v5) at (1.5,-1.5) {$5$};}
\visible<13>{
\node[M] (v1) at (0,1.5) {$1$};
\node[] (v2) at (0,0) {$2$};
\node[] (v3) at (1.5,1.5) {$3$};
\node[M] (v4) at (1.5,0) {$4$};
\node[] (v5) at (1.5,-1.5) {$5$};}
\visible<15,16>{
\node[M] (v1) at (0,1.5) {$1$};
\node[] (v2) at (0,0) {$2$};
\node[] (v3) at (1.5,1.5) {$3$};
\node[] (v4) at (1.5,0) {$4$};
\node[K] (v5) at (1.5,-1.5) {$5$};}
\visible<17>{
\node[M] (v1) at (0,1.5) {$1$};
\node[] (v2) at (0,0) {$2$};
\node[] (v3) at (1.5,1.5) {$3$};
\node[] (v4) at (1.5,0) {$4$};
\node[] (v5) at (1.5,-1.5) {$5$};}
\visible<19,20>{
\node[] (v1) at (0,1.5) {$1$};
\node[K] (v2) at (0,0) {$2$};
\node[K] (v3) at (1.5,1.5) {$3$};
\node[K] (v4) at (1.5,0) {$4$};
\node[K] (v5) at (1.5,-1.5) {$5$};}
\visible<21,22>{
\node[] (v1) at (0,1.5) {$1$};
\node[] (v2) at (0,0) {$2$};
\node[K] (v3) at (1.5,1.5) {$3$};
\node[K] (v4) at (1.5,0) {$4$};
\node[K] (v5) at (1.5,-1.5) {$5$};}
\visible<23,24>{
\node[] (v1) at (0,1.5) {$1$};
\node[] (v2) at (0,0) {$2$};
\node[] (v3) at (1.5,1.5) {$3$};
\node[K] (v4) at (1.5,0) {$4$};
\node[K] (v5) at (1.5,-1.5) {$5$};}
\visible<25,26>{
\node[] (v1) at (0,1.5) {$1$};
\node[] (v2) at (0,0) {$2$};
\node[] (v3) at (1.5,1.5) {$3$};
\node[] (v4) at (1.5,0) {$4$};
\node[K] (v5) at (1.5,-1.5) {$5$};}
\visible<27,28>{
\node[M] (v1) at (0,1.5) {$1$};
\node[] (v2) at (0,0) {$2$};
\node[] (v3) at (1.5,1.5) {$3$};
\node[M] (v4) at (1.5,0) {$4$};
\node[M] (v5) at (1.5,-1.5) {$5$};}
\draw (v1) to (v3);
\draw (v2) to (v3);
\draw (v2) to (v4);
\draw (v2) to (v5);
\end{tikzpicture}
\end{tabular}

\bigskip
\visible<28>{
В этом примере показана типичная ситуация для МВГ:\\в
конце работы алгоритма большинство ветвей отсекается.}
\end{frame}

\begin{frame}[label=branch3]{Некоторые способы оптимизации МВГ}

\begin{itemize}
\item
Сделать $\mathtt{M}$ статической переменной (перед вызовом рекурсивной процедуры добавляем в $\mathtt{M}$ выбранную вершину, после выхода удаляем её из $\mathtt{M}$).\\
\medskip
\item
Вместо локальной переменной $\mathtt{K}$ хранить массив $\mathtt{K[\phantom{i}]}$, где $\mathtt{K[i]}$ соответствуют $\mathtt{i}$-му уровню рекурсии.\\
Экономим на выделении и освобождении памяти.\\
\medskip
\item
На каждом уровне рекурсии элементы множества $\mathrm{K}$ упорядочивать по числу соседей и выбирать их по очереди. Оказывается, выгоднее упорядочивать по убыванию числа соседей. При таком подходе придётся постоянно пересчитывать
для каждой вершины из $\mathrm{K}$ число её соседей в $\mathrm{K}$.
\end{itemize}
\end{frame}

\section{Неточные методы решения}

\subsection{Расширение и урезание}

\begin{frame}{Случайное расширение}
Дано: граф $G(V;E)$, $M$~--- независимое множество.\\\medskip

Цель: расширить $M$ до какого-нибудь максимального по включению
независимого множества.\\\medskip

Метод: пока $K\neq\varnothing$, добавлять в $M$ случайную вершину
из $K$.\\\medskip

Здесь $K$~--- множество вершин, не принадлежащих $M$ и несмежных с
$M$: $K=V\setminus(M\cup\Neighbors(M))$.\\\medskip

\visible<2-> {
\begin{tikzpicture}[scale=1, baseline=(current bounding box.north)]
\tikzstyle{every node}=[circle,text centered,draw=black]
\tikzstyle{M}=[fill=mygreen] \tikzstyle{K}=[fill=yellow]
\visible<2>{

\node[M] (v1) at (2,0) {$1$};
\node[] (v2) at (4,0) {$2$};
\node[] (v3) at (3,-1) {$3$};
\node[] (v4) at (4,-2) {$4$};
\node[] (v5) at (0,-2) {$5$};
\node[] (v6) at (2,-2) {$6$};
\node[] (v7) at (1,-1) {$7$};
\node[M] (v8) at (0,0) {$8$};
\node[] (v9) at (5,-1) {$9$};}

\visible<3,4>{

\node[M] (v1) at (2,0) {$1$};
\node[] (v2) at (4,0) {$2$};
\node[] (v3) at (3,-1) {$3$};
\node[K] (v4) at (4,-2) {$4$};
\node[] (v5) at (0,-2) {$5$};
\node[K] (v6) at (2,-2) {$6$};
\node[K] (v7) at (1,-1) {$7$};
\node[M] (v8) at (0,0) {$8$};
\node[K] (v9) at (5,-1) {$9$};}

\visible<5>{

\node[M] (v1) at (2,0) {$1$};
\node[] (v2) at (4,0) {$2$};
\node[] (v3) at (3,-1) {$3$};
\node[M] (v4) at (4,-2) {$4$};
\node[] (v5) at (0,-2) {$5$};
\node[K] (v6) at (2,-2) {$6$};
\node[K] (v7) at (1,-1) {$7$};
\node[M] (v8) at (0,0) {$8$};
\node[K] (v9) at (5,-1) {$9$};}

\visible<6,7>{

\node[M] (v1) at (2,0) {$1$};
\node[] (v2) at (4,0) {$2$};
\node[] (v3) at (3,-1) {$3$};
\node[M] (v4) at (4,-2) {$4$};
\node[] (v5) at (0,-2) {$5$};
\node[K] (v6) at (2,-2) {$6$};
\node[K] (v7) at (1,-1) {$7$};
\node[M] (v8) at (0,0) {$8$};
\node[] (v9) at (5,-1) {$9$};}

\visible<8,9>{

\node[M] (v1) at (2,0) {$1$};
\node[] (v2) at (4,0) {$2$};
\node[] (v3) at (3,-1) {$3$};
\node[M] (v4) at (4,-2) {$4$};
\node[] (v5) at (0,-2) {$5$};
\node[K] (v6) at (2,-2) {$6$};
\node[M] (v7) at (1,-1) {$7$};
\node[M] (v8) at (0,0) {$8$};
\node[] (v9) at (5,-1) {$9$};}

\visible<10,11>{

\node[M] (v1) at (2,0) {$1$};
\node[] (v2) at (4,0) {$2$};
\node[] (v3) at (3,-1) {$3$};
\node[M] (v4) at (4,-2) {$4$};
\node[] (v5) at (0,-2) {$5$};
\node[M] (v6) at (2,-2) {$6$};
\node[M] (v7) at (1,-1) {$7$};
\node[M] (v8) at (0,0) {$8$};
\node[] (v9) at (5,-1) {$9$};}

\draw (v1) to (v2);
\draw (v1) to (v3);
\draw (v2) to (v3);
\draw (v3) to (v6);
\draw (v3) to (v9);
\draw (v4) to (v9);
\draw (v5) to (v6);
\draw (v5) to (v7);
\draw (v5) to (v8);
\end{tikzpicture}
\nolinebreak\quad
\begin{minipage}[t]{4cm}
\visible<2->{$M$} \qquad\qquad\quad \visible<3->{$K$} \\
\visible<2->{$\{1,8\}$} \qquad\quad \visible<3->{$\{\rtxtcell<4-6>4,6,7,9\}$} \\
\visible<5->{$\{1,4,8\}$} \qquad \visible<6->{$\{6,\rtxtcell<7-9>7\}$} \\
\visible<8->{$\{1,4,7,8\}$} \quad \visible<9->{$\{6\}$} \\
\visible<10->{$\{1,4,6,7,8\}$}
\end{minipage}}
\par\medskip
\begin{overlayarea}{\textwidth}{6ex}
\only<2>{Рассмотрим пример.}
\only<3>{ Формируем множество кандидатов.}
\only<4,7>{ Случайно выбираем вершину из $K$.}
\only<5,8>{ Добавляем выбранную вершину в $M$.}
\only<6,9>{ Удаляем из $K$ выбранную вершину и вершины, смежные с ней.}
\only<10>{ Оставшуюся вершину в $K$ добавляем в $M$.}
\only<11>{Ответ: $\{1,4,6,7,8\}$.}
\end{overlayarea}
\end{frame}

\begin{frame}{Жадное расширение}
Дано: граф $G=(V,E)$, $M$~--- независимое множество.\\\medskip

Цель: расширить $M$ до какого-нибудь максимального по включению
независимого множества.\\\medskip

Метод: пока $K\ne\varnothing$, добавлять в $M$ ту вершину из $K$, которая имеет наименьшее число соседей среди вершин множества $K$.\\\medskip

\visible<2-> {
\begin{tikzpicture}[scale=1, baseline=(current bounding box.north)]
\tikzstyle{every node}=[circle,text centered,draw=black]
\tikzstyle{M}=[fill=mygreen] \tikzstyle{K}=[fill=yellow]
\visible<2>{

\node[] (v1) at (2,0) {$1$};
\node[] (v2) at (4,0) {$2$};
\node[] (v3) at (3,-1) {$3$};
\node[] (v4) at (4,-2) {$4$};
\node[] (v5) at (0,-2) {$5$};
\node[] (v6) at (2,-2) {$6$};
\node[M] (v7) at (1,-1) {$7$};
\node[] (v8) at (0,0) {$8$};
\node[M] (v9) at (5,-1) {$9$};}

\visible<3,4>{

\node[K] (v1) at (2,0) {$1$};
\node[K] (v2) at (4,0) {$2$};
\node[] (v3) at (3,-1) {$3$};
\node[] (v4) at (4,-2) {$4$};
\node[] (v5) at (0,-2) {$5$};
\node[K] (v6) at (2,-2) {$6$};
\node[M] (v7) at (1,-1) {$7$};
\node[K] (v8) at (0,0) {$8$};
\node[M] (v9) at (5,-1) {$9$};}

\visible<5-7>{

\node[K] (v1) at (2,0) {$1$};
\node[K] (v2) at (4,0) {$2$};
\node[] (v3) at (3,-1) {$3$};
\node[] (v4) at (4,-2) {$4$};
\node[] (v5) at (0,-2) {$5$};
\node[K] (v6) at (2,-2) {$6$};
\node[M] (v7) at (1,-1) {$7$};
\node[M] (v8) at (0,0) {$8$};
\node[M] (v9) at (5,-1) {$9$};}

\visible<8-10>{

\node[K] (v1) at (2,0) {$1$};
\node[K] (v2) at (4,0) {$2$};
\node[] (v3) at (3,-1) {$3$};
\node[] (v4) at (4,-2) {$4$};
\node[] (v5) at (0,-2) {$5$};
\node[M] (v6) at (2,-2) {$6$};
\node[M] (v7) at (1,-1) {$7$};
\node[M] (v8) at (0,0) {$8$};
\node[M] (v9) at (5,-1) {$9$};}

\visible<11>{

\node[M] (v1) at (2,0) {$1$};
\node[K] (v2) at (4,0) {$2$};
\node[] (v3) at (3,-1) {$3$};
\node[] (v4) at (4,-2) {$4$};
\node[] (v5) at (0,-2) {$5$};
\node[M] (v6) at (2,-2) {$6$};
\node[M] (v7) at (1,-1) {$7$};
\node[M] (v8) at (0,0) {$8$};
\node[M] (v9) at (5,-1) {$9$};}

\visible<12-13>{

\node[M] (v1) at (2,0) {$1$};
\node[] (v2) at (4,0) {$2$};
\node[] (v3) at (3,-1) {$3$};
\node[] (v4) at (4,-2) {$4$};
\node[] (v5) at (0,-2) {$5$};
\node[M] (v6) at (2,-2) {$6$};
\node[M] (v7) at (1,-1) {$7$};
\node[M] (v8) at (0,0) {$8$};
\node[M] (v9) at (5,-1) {$9$};}

\draw (v1) to (v2);
\draw (v1) to (v3);
\draw (v2) to (v3);
\draw (v3) to (v6);
\draw (v3) to (v9);
\draw (v4) to (v9);
\draw (v5) to (v6);
\draw (v5) to (v7);
\draw (v5) to (v8);
\end{tikzpicture}}
\nolinebreak\quad
\begin{minipage}[t]{4cm}
\visible<2->{$M$} \qquad\qquad\quad \visible<3->{$K$} \\
\visible<2->{$\{7,9\}$} \qquad\quad \visible<3->{$\{1,2,6,\rtxtcell<4-6>8\}$} \\
\visible<5->{$\{7,8,9\}$} \qquad \visible<6->{$\{1,2,\rtxtcell<7-9>6\}$} \\
\visible<8->{$\{6,7,8,9\}$} \quad \visible<9->{$\{\rtxtcell<10-12>1,2\}$}\\
\visible<11->{$\{1,6,7,8,9\}$}
\end{minipage}
\par\medskip
\begin{overlayarea}{\textwidth}{6ex}
\only<2>{Рассмотрим на примере.}
\only<3>{ Формируем множество кандидатов $K$.}
\only<4,7,10>{ Выбираем вершину из $K$ с наименьшим числом соседей среди вершин этого множества.}
\only<5,8,11>{ Добавляем выбранную вершину в $M$.}
\only<6,9,12>{Удаляем из $K$ выбранную вершину и смежные с ней вершины.}
\only<13>{Ответ: $\{1,6,7,8,9\}$}
\end{overlayarea}
\end{frame}

\begin{frame}{Жадное урезание}
Дано: граф $G=(V,E)$, множество $M$ ($M\subset V$).\\\medskip

Цель: урезать $M$ до независимого множества.\\\medskip

Метод: пока $M\notin\IndSets(G)$, удалять из множества $M$
вершину, имеющую наибольшее число соседей в $M$.\\\medskip
\visible<2->{
\begin{tikzpicture}[scale=1, baseline=(current bounding box.north)]
\tikzstyle{every node}=[circle,text centered,draw=black]
\tikzstyle{M}=[fill=mygreen]

\visible<2,3>{

\node[M] (v1) at (2,0) {$1$};
\node[] (v2) at (4,0) {$2$};
\node[M] (v3) at (3,-1) {$3$};
\node[] (v4) at (4,-2) {$4$};
\node[M] (v5) at (0,-2) {$5$};
\node[] (v6) at (2,-2) {$6$};
\node[M] (v7) at (1,-1) {$7$};
\node[M] (v8) at (0,0) {$8$};
\node[] (v9) at (5,-1) {$9$};}

\visible<4,5>{

\node[M] (v1) at (2,0) {$1$};
\node[] (v2) at (4,0) {$2$};
\node[M] (v3) at (3,-1) {$3$};
\node[] (v4) at (4,-2) {$4$};
\node[] (v5) at (0,-2) {$5$};
\node[] (v6) at (2,-2) {$6$};
\node[M] (v7) at (1,-1) {$7$};
\node[M] (v8) at (0,0) {$8$};
\node[] (v9) at (5,-1) {$9$};}

\visible<6-8>{

\node[] (v1) at (2,0) {$1$};
\node[] (v2) at (4,0) {$2$};
\node[M] (v3) at (3,-1) {$3$};
\node[] (v4) at (4,-2) {$4$};
\node[] (v5) at (0,-2) {$5$};
\node[] (v6) at (2,-2) {$6$};
\node[M] (v7) at (1,-1) {$7$};
\node[M] (v8) at (0,0) {$8$};
\node[] (v9) at (5,-1) {$9$};}

\draw (v1) to (v2);
\draw (v1) to (v3);
\draw (v2) to (v3);
\draw (v3) to (v6);
\draw (v3) to (v9);
\draw (v4) to (v9);
\draw (v5) to (v6);
\draw (v5) to (v7);
\draw (v5) to (v8);
\end{tikzpicture}}
\nolinebreak\qquad
\begin{minipage}[t]{4cm}
\visible<2->{$M$} \\
\visible<2->{$\{1,3,\rtxtcell<3,4>5,7,8\}$}\\
\visible<4->{$\{\rtxtcell<5>1,3,7,8\}$}\\
\visible<6->{$\{3,7,8\}$}
\end{minipage}
\par\medskip
\begin{overlayarea}{\textwidth}{6ex}
\only<2>{Рассмотрим пример.}
\only<3>{ Выбираем вершину с наибольшим числом соседей в $M$.}
\only<4>{ Удаляем из $M$ выбранную вершину.}
\only<5>{ Выбираем вершину с наибольшим числом соседей в $M$.}
\only<6>{ Удаляем из $M$ выбранную вершину.}
\only<7>{У вершин из $M$ нет соседей среди элементов этого множества.}
\only<8>{Ответ: $\{3,7,8\}$.}
\end{overlayarea}
\end{frame}

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

\begin{frame}{Генетический алгоритм: основные объекты}

\textbf{Хромосома (особь)}~--- независимое множество вершин графа; хранится в виде двоичного вектора, длина которого равна числу вершин графа (на $i$-ом месте стоит 1, если $i$-ая вершина принадлежит множеству).\\\medskip

\textbf{Приспособленность хромосомы}~--- число вершин в независимом множестве.\\\medskip

\textbf{Популяция} хранится как упорядоченный массив хромосом. Хромосомы упорядочены по приспособленности, а хромосомы с одинаковой приспособленностью~--- лексикографически. Обеспечивается уникальность хромосом.\\\medskip

\end{frame}


\begin{frame}{Генетический алгоритм: схема алгоритма}
Создать начальную популяцию\\
Для $t=1\ldots T$ ($T$~--- число поколений):\\
\qquad Для $i=1\ldots NP/2$ ($NP$~--- число особей):\\
\qquad\qquad Случайно выбрать две особи\\
\qquad\qquad Скрестить выбранные особи\\
\qquad\qquad Применить к потомкам метод урезания и расширения\\
\qquad\qquad Поместить потомков во множество потомков\\
\qquad Для $i=1\ldots NP$:\\
\qquad\qquad Мутировать $i$-ую особь\\
\qquad\qquad Применить к мутанту метод урезания и расширения\\
\qquad\qquad Поместить мутанта во множество мутантов\\
\qquad Добавить всех потомков и мутантов в популяцию\\
\qquad Отсортировать популяцию и удалить дубликаты\\
\qquad Провести отбор усечением
\end{frame}

\begin{frame}[label=mutation]{Генетический алгоритм: мутация}

\microsection{1-й способ. Мутация случайного числа генов.}\\
Дана максимальная доля $\mu$ инвертируемых генов.\\
Случайно генерируем число \texttt{m} ($\mathtt{0\leqslant m<n\cdot\mu}$).\\
Случайно выбираем и инвертируем \texttt{m} генов.

\medskip
\begin{tabular}{ccc}
\visible<2->{\texttt{\{2,4,5,8\}} $\rightleftharpoons$}
\vphantom{$\overline{\overline{0}}$}
\only<2,3>{$\mathtt{01011001}$}%
\only<4->{$\mathtt{01\overline{0}11\overline{\overline{0}}01}$}%
 & \visible<5->{$\mapsto$} &
\visible<5->{\texttt{01111001} $\leftrightharpoons$ \texttt{\{2,3,4,5,8\}}} \\
\visible<3->{\texttt{m} = 3,\quad \texttt{k} = 6, 3, 6 & &}
\end{tabular}

\bigskip
\visible<6->{
\microsection{2-й способ. Однородная мутация.}\\
Каждый ген инвертируем с заданной вероятностью \texttt{p}.}

\bigskip
\begin{tabular}{rcc}
\visible<7->{\texttt{\{2,4,5,8\}} $\rightleftharpoons$}
\only<7>{$\mathtt{01011001}$}%
\only<8->{$\mathtt{0\overline{1}011\overline{0}01}$}%
& \visible<9->{$\mapsto$} &
\visible<9->{\texttt{00011101} $\leftrightharpoons$ \texttt{\{4,5,6,8\}}} \\
\visible<8->{инвертируем?\quad \texttt{FTFFFTFF}} & &
\end{tabular}

\bigskip
\visible<10->{Урезаем каждого мутанта жадным алгоритмом до
независимого множества и дополняем его до максимального
по включению независимого множества.}
\end{frame}

\begin{frame}[label=crossover]{Генетический алгоритм: скрещивание}

\microsection{Одноточечное скрещивание}\\
Случайная точка разрыва, обмен концами:

\par\medskip
\begin{tabular}{rcl}
\texttt{\{1,3,4,6\}} $\leftrightharpoons$
\texttt{10110\alert<3->{100}} & & \visible<4->{\texttt{10110011}
$\rightleftharpoons$ \texttt{\{1,3,4,7,8\}}}
\\%
\visible<2->{\texttt{k = 5}}\hfill%
\visible<3->{\phantom{0}$\updownarrow$\phantom{0}} &
\visible<3->{$\mapsto$} &
\\
\texttt{\{1,2,5,7,8\}} $\leftrightharpoons$
\texttt{11001\alert<3->{011}} & & \visible<4->{\texttt{11001100}
$\rightleftharpoons$ \texttt{\{1,2,5,6\}}}
\end{tabular}

\par\medskip
\visible<5->{
\microsection{Двухточечное скрещивание}\\
Две случайные точки разрыва, обмен серединами:
\par\medskip
\begin{tabular}{rcl}
\texttt{\{1,3,4,6\}} $\leftrightharpoons$
\texttt{10\alert<7->{110}100}& & \visible<8->{\texttt{10001100}
$\rightleftharpoons$ \texttt{\{1,5,6\}}}
\\%
\visible<6->{$\mathtt{k_1 = 2,\;k_2 = 5}$}\hfill\hfill%
\visible<7->{$\updownarrow$\phantom{0}\phantom{0}\phantom{0}\phantom{0}}
& \visible<7->{$\mapsto$} &
\\
\texttt{\{1,2,5,7,8\}} $\rightleftharpoons$
\texttt{11\alert<7->{001}011}& & \visible<8->{\texttt{11110011}
$\rightleftharpoons$ \texttt{\{1,2,3,4,7,8\}}}
\end{tabular}}

\par\medskip
\visible<9->{
\microsection{Однородное скрещивание}\\
Обмен генами осуществляется с заданной вероятностью:
\par\medskip
\begin{tabular}{rcl}
\texttt{\{1,3,4,6\}} $\leftrightharpoons$
\texttt{\alert<10->{1}0\alert<10->{1}10\alert<10->{10}0}& &
\visible<12->{\texttt{10010010} $\rightleftharpoons$
\texttt{\{1,4,7\}}}
\\%
\only<10>{\texttt{обмен?}}\hfill%
\only<10>{\texttt{TFTFFTTF}}%
\only<11,12>{$\updownarrow$\phantom{0}$\updownarrow$\phantom{0}\phantom{0}$\updownarrow$$\updownarrow$\phantom{0}}
& \visible<11->{$\mapsto$} &
\\
\texttt{\{1,2,5,7,8\}} $\rightleftharpoons$
\texttt{\alert<10->{1}1\alert<10->{0}01\alert<10->{01}1}& &
\visible<12->{\texttt{11101101} $\rightleftharpoons$
\texttt{\{1,2,3,5,6,8\}}}
\end{tabular}}
\end{frame}

\begin{frame}[label=showGA]{Генетический алгоритм: демонстрация}
\begin{tikzpicture}[ycomb,xscale=0.4,yscale=0.08, baseline=(current bounding box.north)]
\draw (0,5) node[anchor=east] {$5$};
\draw (0,10) node[anchor=east] {$10$};
\draw (0,15) node[anchor=east] {$15$};
\draw (0,20) node[anchor=east] {$20$};
\draw (0,25) node[anchor=east] {$25$};
\draw (0,30) node[anchor=east] {$30$};
\draw (0,35) node[anchor=east] {$35$};
\draw (0,40) node[anchor=east] {$40$};
\draw (0,45) node[anchor=east] {$45$};
\draw (0,50) node[anchor=east] {$50$};
\draw (0,55) node[anchor=east] {$55$};
\draw (0,60) node[anchor=east] {$60$};
\draw (0,65) node[anchor=east] {$65$};
\draw (0,70) node[anchor=east] {$70$};
\draw[color=gray,thin] (0,5)--(10,5);
\draw[color=gray,thin] (0,10)--(10,10);
\draw[color=gray,thin] (0,15)--(10,15);
\draw[color=gray,thin] (0,20)--(10,20);
\draw[color=gray,thin] (0,25)--(10,25);
\draw[color=gray,thin] (0,30)--(10,30);
\draw[color=gray,thin] (0,35)--(10,35);
\draw[color=gray,thin] (0,40)--(10,40);
\draw[color=gray,thin] (0,45)--(10,45);
\draw[color=gray,thin] (0,50)--(10,50);
\draw[color=gray,thin] (0,55)--(10,55);
\draw[color=gray,thin] (0,60)--(10,60);
\draw[color=gray,thin] (0,65)--(10,65);
\draw[color=gray,thin] (0,70)--(10,70);

\tikzstyle{plotline}=[line width=0.3cm,color=darkgreen]
\visible<1>{
\draw[style=plotline] plot coordinates {(1,70) (2,0) (3,0) (4,0) (5,0) (6,0) (7,0) (8,0) (9,0) (10,0)};}

\visible<2>{
\draw[style=plotline] plot coordinates {(1,0) (2,0) (3,0) (4,7) (5,59) (6,4) (7,0) (8,0) (9,0) (10,0)};}

\visible<3>{
\draw[style=plotline] plot coordinates {(1,0) (2,0) (3,0) (4,0) (5,33) (6,37) (7,0) (8,0) (9,0) (10,0)};}

\visible<4>{
\draw[style=plotline] plot coordinates {(1,0) (2,0) (3,0) (4,0) (5,0) (6,56) (7,14) (8,0) (9,0) (10,0)};}

\visible<5>{
\draw[style=plotline] plot coordinates {(1,0) (2,0) (3,0) (4,0) (5,0) (6,41) (7,29) (8,0) (9,0) (10,0)};}

\visible<6>{
\draw[style=plotline] plot coordinates {(1,0) (2,0) (3,0) (4,0) (5,0) (6,16) (7,49) (8,5) (9,0) (10,0)};}

\visible<7>{
\draw[style=plotline] plot coordinates {(1,0) (2,0) (3,0) (4,0) (5,0) (6,0) (7,58) (8,11) (9,1) (10,0)};}

\visible<8,9>{
\draw[style=plotline] plot coordinates {(1,0) (2,0) (3,0) (4,0) (5,0) (6,0) (7,46) (8,21) (9,3) (10,0)};}

\draw[->] (0,0)--(12,0); \draw (12,0) node[anchor=north] {\text{размер}};
\draw[->] (0,0)--(0,75); \draw (0,75) node[anchor=west] {\text{число особей}};
\foreach \xpos in {1,...,9}
  \draw (\xpos,0) node[anchor=north]{$\xpos$};
\end{tikzpicture}
\nolinebreak
\begin{minipage}[t]{4cm}
\par\medskip
Входные данные:
\par\medskip
$G=(V,E)$\\
\#$V=100$\\
density = $50\%$\\
\medskip

NP = $70$\\
$\textrm{P}_{\textrm{mutation}} = 0.1$\\
$\textrm{P}_{\textrm{crossover}} = 0.2$
\end{minipage}
\begin{overlayarea}{\textwidth}{2ex}
\only<1>{Начальная популяция.}
\only<2>{5-ое поколение.}
\only<3>{10-ое поколение.}
\only<4>{15-ое поколение.}
\only<5>{20-ое поколение.}
\only<6>{25-ое поколение.}
\only<7>{30-ое поколение.}
\only<8>{35-ое поколение.}
\only<9>{9 вершин в максимальном независимом множестве.}
\end{overlayarea}
\end{frame}

\section{Эффективность различных методов}

\subsection{Алгоритм Брона-Кербоша}
\begin{frame}[label=compare]{Эффективность алгоритма Брона-Кербоша}
\microsection{Случайный граф с плотностью 70\%.}
\begin{tabular}{ccl}
\textrm{Число вершин} & \textrm{Размер} & \textrm{Время} \\
$50$ & $5$ & $0.03$\;\textrm{сек}\\
$100$ & $6$ & $0.3$\;\textrm{сек}\\
$150$ & $6$ & $1.5$\;\textrm{сек}\\
\end{tabular}

\microsection{Случайный граф с плотностью 50\%.}
\begin{tabular}{ccl}
\textrm{Число вершин} & \textrm{Размер} & \textrm{Время} \\
$50$ & $11$ & $3.6$\;\textrm{сек}\\
$100$ & $15$ & $7.2$\;\textrm{мин}\\
$150$ & $17$ & $>1$\;\textrm{ч}\\
\end{tabular}

\microsection{Случайный граф с плотностью 20\%.}
\begin{tabular}{ccl}
\textrm{Число вершин} & \textrm{Размер} & \textrm{Время}\\
$50$ & $16$ & $50.5$\;\textrm{сек}\\
$100$ & $20$ & $>1$\;\textrm{ч}\\
$150$ & $23$ & $>1$\;\textrm{ч}\\
\end{tabular}
\end{frame}

\subsection{Метод ветвей и границ}
\begin{frame}[label=compare1]{Эффективность метода ветвей и границ}
\microsection{Случайный граф с плотностью 70\%.}
\begin{tabular}{ccl}
\textrm{Число вершин} & \textrm{Размер} & \textrm{Время} \\
$50$ & $5$ & $0$\;\textrm{сек}\\
$100$ & $6$ & $0$\;\textrm{сек}\\
$150$ & $6$ & $0.03$\;\textrm{сек}\\
\end{tabular}

\microsection{Случайный граф с плотностью 50\%.}
\begin{tabular}{ccl}
\textrm{Число вершин} & \textrm{Размер} & \textrm{Время} \\
$50$ & $11$ & $0.02$\;\textrm{сек}\\
$100$ & $15$ & $0.4$\;\textrm{сек}\\
$150$ & $17$ & $10$\;\textrm{cек}\\
\end{tabular}

\microsection{Случайный граф с плотностью 20\%.}
\begin{tabular}{ccl}
\textrm{Число вершин} & \textrm{Размер} & \textrm{Время} \\
$50$ & $16$ & $0.02$\;\textrm{сек}\\
$100$ & $20$ & $3.6$\;\textrm{сек}\\
$150$ & $23$ & $2.5$\;\textrm{мин}\\
\end{tabular}

\end{frame}

\subsection{Генетический алгоритм}
\begin{frame}[label=compare2]{Эффективность генетического алгоритма}

\microsection{Случайный граф $G=(V,E)$ с плотностью 50\%.}\\\medskip
\begin{tabular}{@{}ccccccl@{}}
$\mathrm{\#V}$ & $\mathrm{T}$ & $\mathrm{NP}$ & $\mathrm{P_{mutation}}$ & $\mathrm{P_{crossover}}$ & \textrm{Размер} & \textrm{Время} \\
$150$ & $60$ & $150$ & $0.07$ & $0.2$ & $17\,(17)$ & $20$\;\textrm{сек}\\
$200$ & $60$ & $200$ & $0.06$ & $0.2$ & $16\,(17)$ & $40$\;\textrm{сек}
\end{tabular}
\par\medskip
\microsection{Случайный граф $G=(V,E)$ с плотностью 30\%.}\\\par\medskip
\begin{tabular}{@{}ccccccl@{}}
$\mathrm{\#V}$ & $\mathrm{T}$ & $\mathrm{NP}$ & $\mathrm{P_{mutation}}$ & $\mathrm{P_{crossover}}$ & \textrm{Размер} & \textrm{Время} \\
$150$ & $60$ & $150$ & $0.06$ & $0.2$ & $16\,(16)$ & $19$\;\textrm{сек}\\
$200$ & $60$ & $200$ & $0.07$ & $0.2$ & $17\,(19)$ & $46$\;\textrm{сек}
\end{tabular}
\par\medskip
\microsection{Тестовый граф frb30-15-1.mis в DIMACS формате.}\\\par\medskip
\begin{tabular}{ccccccl}
$\mathrm{\#V}$ & $\mathrm{T}$ & $\mathrm{NP}$ & $\mathrm{P_{mutation}}$ & $\mathrm{P_{crossover}}$ & \textrm{Размер} & \textrm{Время} \\
$450$ & $10$ & $600$ & $0.1$ & $0.2$ & $24\,(30)$ & $2.6$\;\textrm{мин}
\end{tabular}
\end{frame}

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