\documentclass[a4paper,12pt,brazil,landscape]{article}
\newcommand{\ultimamodificacao}{30 de julho de 2007}
\usepackage[latin1]{inputenc}
\usepackage[brazil]{babel}
\usepackage{comment}
\usepackage{epsfig,graphicx,color,latexsym,alltt,calc,ifthen,slides,hyperref} 
 
\newcounter{conta}
\begin{document}

\setbackgroundcolor{white}
\settextcolor{blue}
\setslidetitlecolor{red}
\setbordercolor{darkblue}

\setedition{slides.sty}
\newincluder{fulledition}
\setincluder{fulledition}{true}

\sffamily 
\bfseries 
\mathversion{bold}
\Hugesize 
%\Hugefont

\title{Caminhamentos \\ Baseado em Townsend (1987), Cap. 7}
\author{Newton José Vieira}
\lhead{Matemática Discreta}
\rhead{Capítulo 7}
\lfoot{UFMG}
%\rfoot{rsb}
\organization{UFMG}
\cfoot{\hyperlink{inicio}{\threebigotimes}~~~\hyperlink{sumario}{\threebigoplus}}
\date{\ultimamodificacao}
\titlepage

\newslide{SUMÁRIO}
\hypertarget{sumario}{}
%\begin{twoblocks}
\begin{itemize}
\item \hyperlink{circuitos-1}{Circuitos Eulerianos}
\item \hyperlink{ciclos}{Ciclos Hamiltonianos}
\item \hyperlink{caixeiro-viajante-1}{O Problema do Caixeiro Viajante}
\end{itemize}
%\centralbar{13cm}
%\begin{itemize}
%\item \hyperlink{comandos}{Comandos Especiais}
%\end{itemize}
%\end{twoblocks}

\pagenumbering{arabic}

%--------------------------------------------------------------------------------------------

\section{CIRCUITOS EULERIANOS}
\hypertarget{circuitos-1}{}
\setskiplink{capitulo7}

\newslide{Grafo Euleriano}

\begin{description}
 \item[Proposi\c{c}\~{a}o:] \
 
       Um grafo \textcolor{orange}{conexo} \'{e} \textcolor{black}{Euleriano} se, e somente se, o grau de todo v\'{e}rtice \'{e}
       par.
       
 \item[Prova:] \

       Em um circuito, o n\'{u}mero de arestas incidentes a cada v\'{e}rtice \'{e} par
       (metade de entrada e metade de sa\'{\i}da do v\'{e}rtice). Logo, se o grafo \'{e}
       Euleriano, o grau de todo v\'{e}rtice \'{e} par.     
       
       Suponha que o grau de todo v\'{e}rtice \'{e} par. Construindo-se um trajeto
       come\c{c}ando por um v\'{e}rtice $x_1$, e indo t\~{a}o longe quanto poss\'{\i}vel, sempre
       tomando uma aresta ainda n\~{a}o utilizada, at\'{e} voltar a $x_1$, forma-se um
       circuito (pois o n\'{u}mero de arestas \'{e} finito, e haver\'{a} sempre pares de
       entrada/sa\'{\i}da para cada v\'{e}rtice, exceto para $x_1$). Como o grafo \'{e}
       conexo, os circuitos assim formados (se forem formados mais de um) podem
       ser ``combinados'' em um circuito Euleriano. 
\end{description}

\vspace*{10mm}

\noindent \underline{Exemplo}:

%\begin{center}
\begin{picture}(160,160)(-100,0)
 \put(10,110){\makebox(0,0){a}}
 \put(20,100){\circle*{5}}
 \put(50,110){\makebox(0,0){i}}
 \put(60,100){\circle*{5}}
 \put(110,110){\makebox(0,0){j}}
 \put(100,100){\circle*{5}}
 \put(150,110){\makebox(0,0){d}}
 \put(140,100){\circle*{5}}
 \put(20,100){\line(1,0){120}}
 \put(20,100){\line(0,-1){40}}
 \put(10,50){\makebox(0,0){h}}
 \put(20,60){\circle*{5}}
 \put(50,70){\makebox(0,0){l}}
 \put(60,60){\circle*{5}}
 \put(110,70){\makebox(0,0){k}}
 \put(100,60){\circle*{5}}
 \put(150,50){\makebox(0,0){e}}
 \put(140,60){\circle*{5}}
 \put(20,60){\line(1,0){120}}
 \put(140,100){\line(0,-1){40}}
 
 \put(50,150){\makebox(0,0){b}}
 \put(60,140){\circle*{5}}
 \put(110,150){\makebox(0,0){c}}
 \put(100,140){\circle*{5}}
 \put(50,10){\makebox(0,0){g}}
 \put(60,20){\circle*{5}}
 \put(110,10){\makebox(0,0){f}}
 \put(100,20){\circle*{5}}
 \put(60,140){\line(1,0){40}}
 \put(60,20){\line(1,0){40}}
 \put(60,20){\line(0,1){120}}
 \put(100,20){\line(0,1){120}}
\end{picture}
%\end{center}

%--------------------------------------------------------------------------------------------

\newslide{Grafo randomicamente Euleriano}

\noindent Um grafo \'{e} \textcolor{black}{randomicamente Euleriano a partir de} $x$ se, e
somente se, todo trajeto construido come\c{c}ando no v\'{e}rtice $x$, e continuando em
frente sempre que poss\'{\i}vel, \'{e} circuito Euleriano.

\vspace*{10mm}
\noindent \underline{Aplica\c{c}\~{a}o}: planejamento de uma mostra de quadros.

\vspace*{10mm}
\noindent \underline{Exemplo}: 

\vspace*{5mm}
 O grafo a seguir \'{e} randomicamente Euleriano a partir de x:
 
\begin{center}
\begin{picture}(140,120)
 \put(10,10){\makebox(0,0){d}}
 \put(20,20){\circle*{5}}
 \put(10,60){\makebox(0,0){x}}
 \put(20,60){\circle*{5}}
 \put(10,110){\makebox(0,0){a}}
 \put(20,100){\circle*{5}}
 \put(20,20){\line(0,1){80}}
 \put(20,20){\line(1,0){100}}
 \put(20,100){\line(1,0){100}}
 \put(120,20){\line(0,1){80}}
 \put(130,10){\makebox(0,0){c}}
 \put(120,20){\circle*{5}}
 \put(130,110){\makebox(0,0){b}}
 \put(120,100){\circle*{5}}
 
 \put(20,60){\line(3,2){30}}
 \put(20,60){\line(3,-2){30}}
 \put(80,60){\line(-3,2){30}}
 \put(80,60){\line(-3,-2){30}}

 \put(50,90){\makebox(0,0){e}}
 \put(50,80){\circle*{5}}
 \put(50,30){\makebox(0,0){g}}
 \put(50,40){\circle*{5}}
 \put(90,60){\makebox(0,0){f}}
 \put(80,60){\circle*{5}}
\end{picture}
\end{center}

%--------------------------------------------------------------------------------------------

\newslide{Uma condi\c{c}\~ao necess\'aria e suficiente}

\noindent \begin{description}
 \item[Proposi\c{c}\~{a}o:] \
 
       Um grafo \textcolor{orange}{Euleriano} $G$ \'{e} \textcolor{black}{randomicamente Euleriano a partir de} $x$ se, e
       somente se, $x$ aparece em todo ciclo de $G$.
       
 \item[Prova:] \

       Exerc\'{\i}cio.
\end{description}

%--------------------------------------------------------------------------------------------

\newslide{Trajeto Euleriano}

\noindent Um \textcolor{black}{trajeto Euleriano} \'{e} um trajeto n\~{a}o fechado que inclui todas
as arestas do grafo.

\vspace*{10mm}
\noindent \begin{description}
 \item[Proposi\c{c}\~{a}o:] \
 
       Um grafo \textcolor{orange}{conexo} tem um \textcolor{black}{trajeto Euleriano} se, e somente se, tem exatamente
       2 v\'{e}rtices de grau \'{\i}mpar. E estes 2 v\'{e}rtices s\~{a}o as extremidades do
       trajeto.
       
 \item[Prova:] \

       Exerc\'{\i}cio.
\end{description}

%--------------------------------------------------------------------------------------------

\newslide{N\'umero m\'{\i}nimo de trajetos}
\vspace*{10mm}
\noindent \begin{description}
 \item[Proposi\c{c}\~{a}o:] \
 
       O \textcolor{black}{n\'{u}mero m\'{\i}nimo de trajetos necess\'{a}rio para particionar o conjunto
       das arestas} de um grafo \textcolor{orange}{conexo} \'{e} a metade do n\'{u}mero de v\'{e}rtices de
       grau \'{\i}mpar, exceto quando n\~{a}o h\'{a} vertices de grau \'{\i}mpar; neste caso, o
       n\'{u}mero m\'{\i}nimo \'{e} 1.

 \item[Prova:] \

       Exerc\'{\i}cio.
\end{description}

\vspace*{10mm}
\noindent \underline{Exemplo}: grafo das pontes de K\"onigsberg.

%--------------------------------------------------------------------------------------------

\section{CICLOS HAMILTONIANOS}
\hypertarget{ciclos}{}

\noindent Um \textcolor{black}{caminho Hamiltoniano} \'{e} um caminho simples gerador.

\vspace*{10mm}
\begin{itemize}
 \item Todo grafo Hamiltoniano cont\'{e}m caminho Hamiltoniano.

\vspace*{10mm}
 \item Existem grafos n\~{a}o Hamiltonianos que cont\^{e}m caminhos Hamiltonianos.
       Exemplo:
       
       \begin{center}
       \begin{picture}(100,70)
        \put(10,10){\makebox(0,0){d}}
        \put(20,20){\circle*{5}}
        \put(10,60){\makebox(0,0){a}}
        \put(20,50){\circle*{5}}
        \put(20,20){\line(0,1){30}}
        \put(20,20){\line(2,1){60}}
        \put(20,50){\line(2,-1){60}}
        \put(50,45){\makebox(0,0){b}}
        \put(50,35){\circle*{5}}
        \put(90,10){\makebox(0,0){e}}
        \put(80,20){\circle*{5}}
        \put(90,60){\makebox(0,0){c}}
        \put(80,50){\circle*{5}}
        \put(80,20){\line(0,1){30}}
       \end{picture}       
       \end{center}
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{Como determinar se o grafo \'e Hamiltoniano?}

\noindent Basta considerar \underline{grafos simples}, pois:
\begin{itemize}
 \item Com rela\c{c}\~{a}o a {caminhos\/} Hamiltonianos: la\c{c}os e arestas m\'{u}l\-ti\-plas
       n\~{a}o s\~{a}o relevantes para a exist\^{e}ncia dos mesmos.
 \item Com rela\c{c}\~{a}o a {ciclos\/} Hamiltonianos: la\c{c}os e arestas m\'{u}ltiplas s\'{o}
       s\~{a}o relevantes nos grafos triviais:
       
       \begin{center}
       \begin{picture}(160,70)
        \put(25,10){\makebox(0,0){a}}
        \put(25,20){\circle*{5}}
        \put(25,35){\circle{30}}
        \put(90,20){\makebox(0,0){e}}
        \put(145,10){\makebox(0,0){b}}
        \put(145,20){\circle*{5}}
        \put(145,60){\makebox(0,0){a}}
        \put(145,50){\circle*{5}}
        \put(145,35){\oval(10,30)}
       \end{picture}       
       \end{center}
\end{itemize}

\vspace*{10mm}
\begin{itemize}
 \item N\~{a}o h\'{a} caracteriza\c{c}\~{a}o simples nem eficiente para ciclos e caminhos
       Hamiltonianos.
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{T\'{e}cnicas para grafos de tamanho moderado}

\vspace*{10mm}
\begin{itemize}
 \item Usar o fato de que um ciclo Hamiltoniano cont\'{e}m \textcolor{black}{exatamente
       duas} das arestas incidentes a cada v\'{e}rtice.
       
%--------------------------------------------------------------------------------------------

\newslide{T\'{e}cnicas para grafos de tamanho moderado}      

       \underline{Exemplos}:
       
       \vspace*{10mm}
       \begin{picture}(170,110)
        \put(10,10){\makebox(0,0){f}}
        \put(20,20){\circle*{5}}
        \put(18,18){\line(0,1){30}}
        \put(18,18){\line(1,0){30}}
        \put(20,20){\line(1,0){120}}
        \put(80,10){\makebox(0,0){e}}
        \put(80,20){\circle*{5}}
        \put(150,10){\makebox(0,0){d}}
        \put(140,20){\circle*{5}}
        \put(140,20){\line(0,1){60}}
        \put(200,65){\makebox(0,0)[l]{O circuito induzido n\~{a}o}}
        \put(200,45){\makebox(0,0)[l]{inclui todos os v\'{e}rtices.}}
        \put(150,90){\makebox(0,0){c}}
        \put(140,80){\circle*{5}}
        \put(140,80){\line(-1,0){120}}
        \put(80,90){\makebox(0,0){b}}
        \put(80,80){\circle*{5}}
        \put(10,90){\makebox(0,0){a}}
        \put(20,80){\circle*{5}}
        \put(20,80){\line(0,-1){60}}
        \put(20,80){\line(1,-1){60}}
        \put(80,80){\line(0,-1){60}}
        \put(80,80){\line(1,-1){60}}
        \put(60,60){\makebox(0,0){g}}
        \put(50,50){\circle*{5}}
        \put(68,35){\line(-1,1){30}}
       \end{picture}

       \vspace*{10mm}
       \begin{picture}(430,200)
        \put(10,10){\makebox(0,0)[l]{Escolhendo $\{a,i\}i\{i,b\}$}}
        \put(10,40){\makebox(0,0){g}}
        \put(20,50){\circle*{5}}
        \put(20,50){\line(1,0){120}}
        \put(80,40){\makebox(0,0){f}}
        \put(80,50){\circle*{5}}
        \put(150,40){\makebox(0,0){e}}
        \put(140,50){\circle*{5}}
        \put(140,50){\line(0,1){120}}
        \put(150,110){\makebox(0,0){d}}
        \put(140,110){\circle*{5}}
        \put(150,180){\makebox(0,0){c}}
        \put(140,170){\circle*{5}}
        \put(140,170){\line(-1,0){120}}
        \put(80,180){\makebox(0,0){b}}
        \put(80,170){\circle*{5}}
        \put(10,180){\makebox(0,0){a}}
        \put(20,170){\circle*{5}}
        \put(10,110){\makebox(0,0){h}}
        \put(20,110){\circle*{5}}
        \put(20,170){\line(0,-1){120}}
        \put(20,110){\line(1,0){120}}
        \put(80,170){\line(0,-1){120}}
        \put(20,170){\line(1,-1){120}}
        \put(20,50){\line(1,1){120}}
        \put(100,120){\makebox(0,0){i}}
        \put(80,110){\circle*{5}}
        \put(53,140){\line(1,-1){24}}
        \put(77,116){\line(0,1){24}}
        
        \put(180,120){\line(1,0){60}}
        \put(180,100){\line(1,0){60}}
        \put(250,110){\line(-1,1){20}}
        \put(250,110){\line(-1,-1){20}}
        
        \put(280,40){\makebox(0,0){g}}
        \put(290,50){\circle*{5}}
        \put(290,50){\line(1,0){120}}
        \put(350,40){\makebox(0,0){f}}
        \put(350,50){\circle*{5}}
        \put(420,40){\makebox(0,0){e}}
        \put(410,50){\circle*{5}}
        \put(410,50){\line(0,1){120}}
        \put(420,110){\makebox(0,0){d}}
        \put(410,110){\circle*{5}}
        \put(420,180){\makebox(0,0){c}}
        \put(410,170){\circle*{5}}
        \put(410,170){\line(-1,0){60}}
        \put(350,180){\makebox(0,0){b}}
        \put(350,170){\circle*{5}}
        \put(350,170){\line(0,-1){60}}
        \put(280,180){\makebox(0,0){a}}
        \put(290,170){\circle*{5}}
        \put(280,110){\makebox(0,0){h}}
        \put(290,110){\circle*{5}}
        \put(290,170){\line(0,-1){120}}
        \put(290,170){\line(1,-1){60}}
        \put(370,120){\makebox(0,0){i}}
        \put(350,110){\circle*{5}}
        \put(323,140){\line(1,-1){24}}
        \put(347,116){\line(0,1){24}}
    \end{picture}

%--------------------------------------------------------------------------------------------

\newslide{T\'{e}cnicas para grafos de tamanho moderado}

 \item Se for poss\'{\i}vel particionar os v\'{e}rtices em dois conjuntos, de forma que

       \vspace*{5mm}
       \begin{flushleft}
       se $x$ e $y$ s\~{a}o adjacentes, \\
       ent\~{a}o $x$ \'{e} membro de um e $y$ \'{e} membro do outro,
       \end{flushleft}
       
       \vspace*{5mm}
      ent\~{a}o, em caminhos ou ciclos Hamiltonianos, deve haver
      \textcolor{black}{altern\^{a}ncia} de v\'{e}rtices dos dois conjuntos.

%--------------------------------------------------------------------------------------------

\newslide{T\'{e}cnicas para grafos de tamanho moderado}

       \underline{Exemplo}:

       \begin{center}       
       \begin{picture}(200,230) \normalsize
        \put(100,10){\makebox(0,0){B}}
        \put(100,20){\circle*{5}}
        \put(100,20){\line(0,1){20}}
        \put(107,35){\makebox(0,0){A}}
        \put(100,40){\circle*{5}}
        \put(100,20){\line(-1,1){60}}
        \put(100,20){\line(1,1){60}}
        \put(100,40){\line(-1,1){50}}
        \put(100,40){\line(1,1){50}}
        \put(30,80){\makebox(0,0){A}}
        \put(40,80){\circle*{5}}
        \put(50,80){\makebox(0,0){B}}
        \put(50,90){\circle*{5}}
        \put(40,80){\line(1,1){10}}
        \put(170,80){\makebox(0,0){A}}
        \put(160,80){\circle*{5}}
        \put(150,80){\makebox(0,0){B}}
        \put(150,90){\circle*{5}}
        \put(160,80){\line(-1,1){10}}
        
        \put(40,80){\line(0,1){70}}
        \put(50,90){\line(0,1){50}}
        \put(30,150){\makebox(0,0){B}}
        \put(40,150){\circle*{5}}
        \put(45,135){\makebox(0,0){A}}
        \put(50,140){\circle*{5}}
        \put(40,150){\line(1,-1){10}}
        
        \put(150,90){\line(0,1){50}}
        \put(160,80){\line(0,1){70}}
        \put(155,135){\makebox(0,0){A}}
        \put(150,140){\circle*{5}}
        \put(170,150){\makebox(0,0){B}}
        \put(160,150){\circle*{5}}
        \put(160,150){\line(-1,-1){10}}
        
        \put(40,150){\line(1,1){60}}
        \put(50,140){\line(1,1){50}}
        \put(160,150){\line(-1,1){60}}
        \put(150,140){\line(-1,1){50}}
        \put(100,220){\makebox(0,0){A}}
        \put(100,210){\circle*{5}}
        \put(107,195){\makebox(0,0){B}}
        \put(100,190){\circle*{5}}
        \put(100,190){\line(0,1){20}}
        
        \put(50,90){\line(1,0){100}}
        \put(50,90){\line(1,2){50}}
        \put(150,90){\line(-1,2){50}}
        \put(100,80){\makebox(0,0){A}}
        \put(100,90){\circle*{5}}
        \put(68,145){\makebox(0,0){A}}
        \put(75,140){\circle*{5}}
        \put(132,145){\makebox(0,0){A}}
        \put(125,140){\circle*{5}}
        
        \put(100,90){\line(0,1){25}}
        \put(75,140){\line(1,-1){25}}
        \put(125,140){\line(-1,-1){25}}
        \put(100,125){\makebox(0,0){B}}
        \put(100,115){\circle*{5}}
       \end{picture}
       \end{center}
       \begin{itemize}
        \item Existem 9 v\'{e}rtices do tipo A e 7 do tipo B.
        \item Logo, n\~{a}o existe ciclo nem caminho Hamiltoniano.
       \end{itemize}
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{Uma condi\c{c}\~ao suficiente}

\noindent \begin{description}
 \item[Proposi\c{c}\~{a}o:] \
 
       Seja $G$ um grafo simples com $n\geq 3$ v\'{e}rtices tal que
       $\mbox{\it grau\/}(u)+\mbox{\it grau\/}(v)\geq n$ para todo par de
       v\'{e}rtices distintos n\~{a}o adjacentes $u$ e $v$. Ent\~{a}o $G$ \'{e} Hamiltoniano.
       
 \item[Prova:] \


       Suponha o contr\'{a}rio. Seja $H$ um contra-exemplo, e adicionemos arestas a
       $H$ at\'{e} que a adi\c{c}\~{a}o de uma aresta $\{u,v\}$ resulte em um grafo
       Hamiltoniano. Seja o caminho Hamiltoniano com extremidades $u$ e $v$:
       \[u=x_1\{x_1,x_2\}x_2\ldots x_{n-1}\{x_{n-1},x_n\}x_n=v\mbox{.}\]
       
%--------------------------------------------------------------------------------------------

\newslide{Uma condi\c{c}\~ao suficiente}
       
       Se para qualquer $2\leq k\leq n$, $\{x_1,x_k\}$ \'{e} uma aresta, ent\~{a}o
       $\{x_{k-1},x_n\}$ n\~{a}o \'{e} uma aresta, sen\~{a}o \[x_1\{x_1,x_k\}x_k\ldots
       x_n\{x_n,x_{k-1}\}x_{k-1}\ldots x_2\{x_2,x_1\}x_1=v\] seria um ciclo
       Hamiltoniano:
       \begin{center} \normalsize
       \begin{picture}(390,40)
        \put(20,20){\circle*{5}}
        \put(20,13){\makebox(0,0){$u=x_1$}}
        \put(20,20){\line(1,0){60}}
        \put(80,20){\circle*{5}}
        \put(80,13){\makebox(0,0){$x_2$}}
        \put(80,20){\line(1,0){25}}
        \put(120,20){\makebox(0,0){$\cdots$}}
        \put(135,20){\line(1,0){25}}
        \put(160,20){\circle*{5}}
        \put(177,13){\makebox(0,0){$x_{k-1}$}}
        \put(160,20){\line(1,0){60}}
        \put(220,20){\circle*{5}}
        \put(220,13){\makebox(0,0){$x_k$}}
        \put(220,20){\line(1,0){25}}
        \put(260,20){\makebox(0,0){$\cdots$}}
        \put(275,20){\line(1,0){25}}
        \put(300,20){\circle*{5}}
        \put(300,13){\makebox(0,0){$x_{n-1}$}}
        \put(300,20){\line(1,0){60}}
        \put(360,20){\circle*{5}}
        \put(383,13){\makebox(0,0){$x_n=v$}}
        \put(120,20){\oval(200,40)[t]}
        \put(260,20){\oval(200,40)[b]}
       \end{picture}
       \end{center}
       Portanto, para cada v\'{e}rtice $x_k$ adjacente a $u$ existe um v\'{e}rtice
       diferente n\~{a}o adjacente a $v$. Logo, $\mbox{\it grau\/}(u)+
       \mbox{\it grau\/}(v)\leq n-1$, uma contradi\c{c}\~{a}o.
\end{description}

%--------------------------------------------------------------------------------------------

\newslide{Uma condi\c{c}\~ao suficiente}

\noindent Analogamente,

\vspace*{10mm}
\noindent \begin{description}
 \item[Proposi\c{c}\~{a}o:] \
 
       Seja $G$ um grafo simples com $n\geq 3$ v\'{e}rtices tal que
       $\mbox{\it grau\/}(u)+\mbox{\it grau\/}(v)\geq n-1$ para todo par de
       v\'{e}rtices distintos n\~{a}o adjacentes $u$ e $v$. Ent\~{a}o $G$ tem caminho
       Hamiltoniano.
\end{description}

%--------------------------------------------------------------------------------------------


\begin{comment}++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
\newslide{CAMINHAMENTOS (16)}
\hypertarget{caminhamentos-16}{}

\noindent Seja um grafo simples \underline{planar} Hamiltoniano, e $C$ um ciclo
Hamiltoniano em uma imers\~{a}o de $G$ no plano. {\bf Nota\c{c}\~{a}o:}

\begin{itemize}
 \item $r_k$: n\'{u}mero de faces \underline{internas} a $C$ com exatamente $k$
       arestas.
 \item $s_k$: n\'{u}mero de faces \underline{externas} a $C$ com exatamente $k$
       arestas.
\end{itemize}

\noindent \underline{Exemplo}:

\begin{center}
\begin{picture}(230,220)
 \put(10,10){\makebox(0,0){d}}
 \put(20,20){\circle*{5}}
 \put(40,24){\vector(1,0){140}}
 \put(20,20){\line(1,0){180}}
 \put(20,20){\line(2,1){60}}
 \put(210,10){\makebox(0,0){c}}
 \put(200,20){\circle*{5}}
 \put(196,30){\vector(0,1){100}}
 \put(200,20){\line(0,1){120}}
 \put(200,20){\line(-2,1){60}}
 \put(210,140){\makebox(0,0){b}}
 \put(200,140){\circle*{5}}
 \put(190,140){\vector(-3,2){70}}
 \put(200,140){\line(-3,2){90}}
 \put(200,140){\line(-2,-1){60}}
 \put(110,210){\makebox(0,0){a}}
 \put(110,200){\circle*{5}}
 \put(114,190){\vector(0,-1){40}}
 \put(110,200){\line(-3,-2){90}}
 \put(110,200){\line(0,-1){60}}
 \put(10,140){\makebox(0,0){e}}
 \put(20,140){\circle*{5}}
 \put(24,130){\vector(0,-1){100}}
 \put(20,140){\line(0,-1){120}}
 \put(20,140){\line(2,-1){60}}
 
 \put(80,40){\makebox(0,0){j}}
 \put(80,50){\circle*{5}}
 \put(76,60){\vector(0,1){40}}
 \put(80,50){\line(1,0){60}}
 \put(140,40){\makebox(0,0){i}}
 \put(140,50){\circle*{5}}
 \put(130,46){\vector(-1,0){40}}
 \put(140,50){\line(0,1){60}}

 \put(150,100){\makebox(0,0){h}}
 \put(140,110){\circle*{5}}
 \put(144,100){\vector(0,-1){40}}
 \put(140,110){\line(-1,1){30}}
 \put(120,150){\makebox(0,0){g}}
 \put(120,136){\vector(1,-1){15}}
 \put(110,140){\circle*{5}}
 \put(110,140){\line(-1,-1){30}}
 \put(70,100){\makebox(0,0){f}}
 \put(80,110){\circle*{5}}
 \put(70,108){\vector(-2,1){40}}
 \put(80,110){\line(0,-1){60}}
\end{picture}
\end{center}

%--------------------------------------------------------------------------------------------

\newslide{CAMINHAMENTOS (17)}
\hypertarget{caminhamentos-17}{}

Para o ciclo assinalado tem-se:
\begin{itemize}
 \item $r_1=s_1=r_2=s_2=0$, como em todo ciclo, dado que o grafo \'{e} simples;
 \item $r_3=s_3=0$;
 \item $r_4=4$, $s_4=1$;
 \item $r_5=0$, $s_5=2$;
 \item $r_k=s_k=0$, para $k\geq 6$.
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{CAMINHAMENTOS (18)}
\hypertarget{caminhamentos-18}{}

\noindent \begin{description}
 \item[Proposi\c{c}\~{a}o:] \
 
       Seja $G$ um grafo simples planar Hamiltoniano com $n$ v\'{e}rtices, e $C$ um
       ciclo Hamiltoniano em $G$. Ent\~{a}o, com respeito a $C$,
       \[\sum_{k=3}^n(k-2)(r_k-s_k)=0\mbox{.}\]

 \item[Prova:] \

       {\it Diagonal\/} com rela\c{c}\~{a}o a $C$: aresta que n\~{a}o ocorre em $C$. Seja
       $d$ o n\'{u}mero de diagonais dentro de $C$; ent\~{a}o existem $d+1$ faces dentro
       de $C$ e, assim, $\sum_{k=3}^nr_k=d+1$. J\'{a} a soma dos graus das faces
       dentro de $C$ \'{e} $\sum_{k=3}^nkr_k$. Mas a soma dos graus das faces conta
       cada diagonal 2 vezes, e cada aresta de $C$ 1 vez; logo,
       $\sum_{k=3}^nkr_k= n+2d=n+2(\sum_{k=3}^nr_k -1)$ e, portanto,
       $\sum_{k=3}^n(k-2)r_k= n-2$. Similarmente, tem-se que
       $\sum_{k=3}^n(k-2)s_k= n-2$. Logo, $\sum_{k=3}^n(k-2)(r_k-s_k)=0$.
\end{description}

%--------------------------------------------------------------------------------------------

\newslide{CAMINHAMENTOS (19)}
\hypertarget{caminhamentos-19}{}

\noindent \underline{Exemplo}:

\begin{center}
\begin{picture}(400,200)
\put(10,110){\makebox(0,0){d}}
\put(20,110){\circle*{5}}
\put(20,110){\line(2,1){180}}
\put(20,110){\line(1,0){90}}
\put(20,110){\line(2,-1){180}}

\put(390,110){\makebox(0,0){b}}
\put(380,110){\circle*{5}}
\put(380,110){\line(-2,1){180}}
\put(380,110){\line(-1,0){90}}
\put(380,110){\line(-2,-1){180}}

\put(200,10){\makebox(0,0){c}}
\put(200,20){\circle*{5}}
\put(200,20){\line(-1,2){30}}
\put(200,20){\line(1,2){30}}
\put(160,70){\makebox(0,0){j}}
\put(170,80){\circle*{5}}
\put(170,80){\line(1,1){60}}
\put(240,70){\makebox(0,0){i}}
\put(230,80){\circle*{5}}
\put(230,80){\line(-1,1){60}}
\put(215,110){\makebox(0,0){k}}
\put(200,110){\circle*{5}}

\put(200,210){\makebox(0,0){a}}
\put(200,200){\circle*{5}}
\put(200,200){\line(-1,-2){30}}
\put(200,200){\line(1,-2){30}}
\put(160,150){\makebox(0,0){f}}
\put(170,140){\circle*{5}}
\put(240,150){\makebox(0,0){g}}
\put(230,140){\circle*{5}}

\put(110,100){\makebox(0,0){e}}
\put(110,110){\circle*{5}}
\put(110,110){\line(2,1){60}}
\put(110,110){\line(2,-1){60}}

\put(290,100){\makebox(0,0){h}}
\put(290,110){\circle*{5}}
\put(290,110){\line(-2,1){60}}
\put(290,110){\line(-2,-1){60}}
\end{picture}
\end{center}
Este grafo tem 9 regi\~{o}es de grau 4: $r_4+s_4=9$. Pela proposi\c{c}\~{a}o anterior,
$\sum_{k=3}^n(k-2)(r_k-s_k)=2(r_4-s_4)=0$. Contradi\c{c}\~{a}o.
\end{comment}
%++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

%--------------------------------------------------------------------------------------------

\section{O PROBLEMA DO CAIXEIRO VIAJANTE}
\hypertarget{caixeiro-viajante-1}{}

\newslide{O Problema do Caixeiro Viajante}

\vspace*{10mm}
\noindent O \textcolor{black}{problema do menor caminho fechado gerador}:
\begin{quote}
 encontrar um menor caminho fechado gerador em um grafo valorado completo.
\end{quote}

\vspace*{10mm}
\noindent Um grafo \'{e} \textcolor{black}{Euclidiano} se, e somente se, \'{e} um grafo valorado
completo tal que $d(u,v)+d(v,w)\geq d(u,w)$ para quaisquer 3 v\'{e}rtices $u$, $v$
e $w$.

%--------------------------------------------------------------------------------------------

\newslide{O Problema do Caixeiro Viajante}

\noindent \begin{description}
 \item[Proposi\c{c}\~{a}o:] \
 
       Se $G$ \'{e} um grafo \textcolor{orange}{Euclidiano} e $C$ \'{e} um \textcolor{black}{menor caminho fechado
       gerador} em $G$, ent\~{a}o existe um ciclo Hamiltoniano do mesmo comprimento
       que $C$.

 \item[Prova:] \

       Suponha que $C$ tem um v\'{e}rtice repetido, como mostra a figura:
       \begin{center}
       \begin{picture}(400,70)
        \put(20,20){\circle*{5}}
        \put(20,20){\line(1,0){60}}
        \put(80,10){\makebox(0,0){$x_1$}}
        \put(80,20){\circle*{5}}
        \put(20,20){\line(0,1){30}}
        \put(20,50){\circle*{5}}
        \put(35,50){\makebox(0,0){$\cdots$}}
        \put(50,50){\makebox(0,0){$\cdots$}}
        \put(65,50){\makebox(0,0){$\cdots$}}
        \put(80,60){\makebox(0,0){$x_k$}}
        \put(80,50){\circle*{5}}
        \put(80,20){\line(2,1){60}}
        \put(80,50){\line(2,-1){60}}
        \put(110,25){\makebox(0,0){$v$}}
        \put(110,35){\circle*{5}}
        
        \put(250,35){\makebox(0,0)[l]{$C=v x_1\cdots x_k v y_1\cdots y_nv$}}
        
        \put(200,20){\circle*{5}}
        \put(200,20){\line(-1,0){60}}
        \put(140,10){\makebox(0,0){$y_1$}}
        \put(140,20){\circle*{5}}
        \put(200,20){\line(0,1){30}}
        \put(200,50){\circle*{5}}
        \put(185,50){\makebox(0,0){$\cdots$}}
        \put(170,50){\makebox(0,0){$\cdots$}}
        \put(155,50){\makebox(0,0){$\cdots$}}
        \put(140,60){\makebox(0,0){$y_n$}}
        \put(140,50){\circle*{5}}
       \end{picture}
       \end{center}
       Ent\~ao $C'=v x_1\cdots x_k y_1\cdots y_n v$ n\~{a}o \'{e} maior que $C$. Assim, pode-se eliminar todas
       as repeti\c{c}\~{o}es de v\'{e}rtices de $C$, at\'{e} obter um ciclo Hamiltoniano de
       comprimento igual ao de $C$.
\end{description}

%--------------------------------------------------------------------------------------------

\newslide{O Problema do Caixeiro Viajante}

\noindent O \textcolor{black}{problema do caixeiro viajante}:
\begin{quote}
 encontrar um \textcolor{black}{menor ciclo Hamiltoniano} em um grafo valorado completo.
\end{quote}

\vspace*{10mm}
\noindent \textcolor{black}{N\~{a}o h\'{a} solu\c{c}\~{a}o eficiente conhecida} para o problema do
caixeiro viajante.

\vspace*{10mm}
\begin{quote}
 $\Rightarrow$ Usar \textcolor{black}{heur\'{\i}sticas}.
\end{quote}

%--------------------------------------------------------------------------------------------

\newslide{Exemplo: Algoritmo do vizinho mais pr\'{o}ximo}

\hspace*{10mm}\begin{tabbing}
 xxxx\=xxxx\= \kill
 Escolha um v\a'ertice $v$; \\
 $C := \langle v\rangle$; \\
 \textcolor{black}{enquanto} $C$ n\~{a}o cont\a'em todos os v\a'ertices \textcolor{black}{fa\c{c}a} \\
     \> seja $x$ o \a'ultimo v\a'ertice de $C$; \\
     \> seja $y$ um dos v\a'ertices mais pr\a'oximos de $x$; \\
     \> $C := C \oplus y$ \\
 \textcolor{black}{fim}; \\
 $C := C \oplus v$.
\end{tabbing}

\vspace*{5mm}
\noindent Observa\c{c}\~{o}es:
\begin{itemize}
 \item O comprimento de $C$ pode depender de $v$.
 \item Este \'{e} um exemplo de \textcolor{black}{algoritmo guloso}.
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{Exemplo: Algoritmo do vizinho mais pr\'{o}ximo}

\noindent \underline{Exemplo}:

\begin{picture}(400,160)
 \put(160,10){\makebox(0,0){$d$}}
 \put(160,20){\circle*{5}}
 \put(160,20){\line(1,0){80}}
 \put(200,17){\makebox(0,0)[t]{\normalsize 11}}
 \put(240,10){\makebox(0,0){$c$}}
 \put(240,20){\circle*{5}}
 \put(240,20){\line(0,1){80}}
 \put(243,60){\makebox(0,0)[l]{\normalsize 8}}
 \put(250,100){\makebox(0,0){$b$}}
 \put(240,100){\circle*{5}}
 \put(240,100){\line(-1,0){80}}
 \put(200,103){\makebox(0,0)[b]{\normalsize 9}}
 \put(150,100){\makebox(0,0){$e$}}
 \put(160,100){\circle*{5}}
 \put(160,100){\line(0,-1){80}}
 \put(157,60){\makebox(0,0)[r]{\normalsize 13}}
 \put(160,20){\line(1,1){80}}
 \put(208,80){\makebox(0,0)[l]{\normalsize 6}}
 \put(240,20){\line(-1,1){80}}
 \put(192,80){\makebox(0,0)[r]{\normalsize 5}}
 
 \put(240,100){\line(-1,1){40}}
 \put(228,120){\makebox(0,0)[l]{\normalsize 12}}
 \put(200,150){\makebox(0,0){$a$}}
 \put(200,140){\circle*{5}}
 \put(160,100){\line(1,1){40}}
 \put(172,120){\makebox(0,0)[r]{\normalsize 14}}
 
 \put(200,140){\line(-1,0){40}}
 \put(200,140){\line(1,0){40}}
 \put(160,80){\oval(80,120)[l]}
 \put(117,80){\makebox(0,0)[r]{\normalsize 7}}
 \put(240,80){\oval(80,120)[r]}
 \put(283,80){\makebox(0,0)[l]{\normalsize 10}}
\end{picture}

\begin{itemize}
 \item Come\c{c}ando em $a$: comprimento 40.
 \item Come\c{c}ando em $b$: comprimento 37 (menor comprimento).
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{Desempenho do algoritmo do vizinho mais pr\'{o}ximo}

\noindent \begin{description}
 \item[Proposi\c{c}\~{a}o:] \
 
       Seja $G$ um grafo Euclidiano com $n$ v\'{e}rtices. Seja $T_{\mbox{\small VMP}}(v)$ o comprimento
       obtido pelo m\'{e}todo do vizinho mais pr\'{o}ximo come\c{c}ando em $v$, e seja
       $T_0$ o comprimento de um ciclo Hamiltoniano m\'{\i}nimo. Ent\~{a}o:
       \begin{list}{(\arabic{conta})}{\usecounter{conta}}
        \item $T_{\mbox{\small VMP}}(v)/T_0\leq (\lceil \log_2 n\rceil+1)/2$.
        \item Para todo $m$, existe um grafo Euclidiano $G$ com $n\geq m$
              v\'{e}rtices tal que $T_{\mbox{\small VMP}}(v)/T_0 > (\log_2(n+1)+4/3)/3$.
       \end{list}
\end{description}

%--------------------------------------------------------------------------------------------

\newslide{Algumas observa\c{c}\~{o}es}

\vspace*{10mm}
\begin{itemize}
 \item Para um algoritmo qualquer, AQ, $T_{\mbox{\small AQ}}(v)/T_0\geq 1$.
 \item Para um algoritmo ideal, AI, $T_{\mbox{\small AI}}(v)/T_0=1$.
 \item $T_{\mbox{\small VMP}}(v)/T_0$ aumenta com $n$.
 \item Se o grafo n\~{a}o for Euclidiano, o algoritmo do vizinho mais pr\'{o}ximo pode
       ter um desempenho muito ruim.
\end{itemize}
%--------------------------------------------------------------------------------------------

\begin{comment}
\newslide{O PROBLEMA DO CAIXEIRO VIAJANTE (9)}
\hypertarget{caixeiro-viajante-9}{}       
       
       \underline{Exemplo}:
       
       \begin{picture}(400,160)
        \put(160,10){\makebox(0,0){$d$}}
        \put(160,20){\circle*{5}}
        \put(160,20){\line(1,0){80}}
        \put(200,17){\makebox(0,0)[t]{\normalsize 5}}
        \put(240,10){\makebox(0,0){$c$}}
        \put(240,20){\circle*{5}}
        \put(240,20){\line(0,1){80}}
        \put(243,60){\makebox(0,0)[l]{\normalsize 2}}
        \put(250,100){\makebox(0,0){$b$}}
        \put(240,100){\circle*{5}}
        \put(240,100){\line(-1,0){80}}
        \put(200,103){\makebox(0,0)[b]{\normalsize 1}}
        \put(150,100){\makebox(0,0){$e$}}
        \put(160,100){\circle*{5}}
        \put(160,100){\line(0,-1){80}}
        \put(157,60){\makebox(0,0)[r]{\normalsize 6}}
        \put(160,20){\line(1,1){80}}
        \put(208,80){\makebox(0,0)[l]{\normalsize $w$}}
        \put(240,20){\line(-1,1){80}}
        \put(192,80){\makebox(0,0)[r]{\normalsize 3}}
 
        \put(240,100){\line(-1,1){40}}
        \put(228,120){\makebox(0,0)[l]{\normalsize 3}}
        \put(200,150){\makebox(0,0){$a$}}
        \put(200,140){\circle*{5}}
        \put(160,100){\line(1,1){40}}
        \put(172,120){\makebox(0,0)[r]{\normalsize 4}}
 
        \put(200,140){\line(-1,0){40}}
        \put(200,140){\line(1,0){40}}
        \put(160,80){\oval(80,120)[l]}
        \put(117,80){\makebox(0,0)[r]{\normalsize $w$}}
        \put(240,80){\oval(80,120)[r]}
        \put(283,80){\makebox(0,0)[l]{\normalsize $w$}}
       \end{picture}

       Se $w>6$:

       \begin{itemize}
        \item qualquer ciclo obtido pelo algoritmo inclui alguma aresta com
              peso $w$;
        \item o ciclo Hamiltoniano m\'{\i}nimo \'{e} abcdea, com comprimento 20.
       \end{itemize}
       \item Todo algoritmo conhecido para o Problema do Caixeiro Viajante
             cont\'{e}m alguma restri\c{c}\~{a}o sobre os grafos para os quais d\~{a}o
             resultados razo\'{a}veis (vide pr\'{o}xima proposi\c{c}\~{a}o). 

\end{comment}
%--------------------------------------------------------------------------------------------

\newslide{Observa\c{c}\~oes finais}

\noindent \begin{description}
 \item[\ ] \
            Todo algoritmo conhecido para o Problema do Caixeiro Viajante
             cont\'{e}m alguma restri\c{c}\~{a}o sobre os grafos para os quais d\~{a}o
             resultados razo\'{a}veis (vide pr\'{o}xima proposi\c{c}\~{a}o). 

\vspace*{5mm}
 \item[Proposi\c{c}\~{a}o:] \
 
       Se existe um algoritmo eficiente, AE, tal que $T_{AE}(v)/T_0= \mbox{\it
       constante}$ para \underline{qualquer} grafo, ent\~{a}o existe uma solu\c{c}\~{a}o
       eficiente para o Problema do Caixeiro Viajante.
\end{description}

%--------------------------------------------------------------------------------------------

\newslide{Problemas considerados at\'{e} o momento}

\begin{itemize}
 \item Problema da Planaridade (PP): O grafo \'{e} planar?
 \item Problema do Circuito Euleriano (PCE): O grafo \'{e} Euleriano?
 \item Problema do Trajeto Euleriano (PTE): O grafo tem um trajeto Euleriano?
 \item Problema do Isomorfismo (PI): Dois grafos s\~{a}o isomorfos?
 \item Problema do Ciclo Hamiltoniano (PCiH): O grafo \'{e} Hamiltoniano?
 \item Problema do Caminho Hamiltoniano (PCaH): O grafo tem um caminho
       Hamiltoniano?
 \item Problema do Caixeiro Viajante (PCV): Qual \'{e} o menor ciclo Hamiltoniano de
       um grafo valorado completo?
 \item Problema do Menor Caminho Fechado Gerador (PMCFG): Qual \'{e} o menor
       caminho fechado gerador de um grafo valorado completo?
\end{itemize}

%--------------------------------------------------------------------------------------------

\defskiptarget{capitulo7}

\lastpage 

\end{document}