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

\setbackgroundcolor{white}
\settextcolor{skyblue}
\setslidetitlecolor{black}
\setbordercolor{darkblue}

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

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

\hypertarget{inicio}{}
\title{Matemática Discreta \\ Capítulo 8}
\author{Newton José Vieira}
\lhead{Matemática Discreta}
\rhead{Capítulo 8}
\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{arvores-gds-1}{Árvores e Grafos Direcionados}
\item \hyperlink{aplicacoes-1}{Algumas Aplicações de Árvores}
\item \hyperlink{grafos-direcionados-1}{Grafos Direcionados}
\item \hyperlink{caminhamentos-1}{Caminhamentos}
\item \hyperlink{duas-aplicacoes-1}{Duas Aplicações}
\end{itemize}
\centralbar{13cm}
%\begin{itemize}
%\item \hyperlink{comandos}{Comandos Especiais}
%\end{itemize}
\end{twoblocks}

\pagenumbering{arabic}

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

\newslide{ÁRVORES E GRAFOS DIRECIONADOS (1)}
\hypertarget{arvores-gds-1}{}
\setskiplink{capitulo8}

\noindent \underline{\bf \'{A}RVORES E GRAFOS DIRECIONADOS}

\vspace*{10mm}
\noindent {\bf \'{A}rvores}

\vspace*{10mm}
\noindent Uma {\bf \'{a}rvore} \'{e} um grafo conexo ac\'{\i}clico.

\vspace*{5mm}
\noindent \underline{Exemplo}: as 3 \'{a}rvores n\~{a}o isomorfas de 5 v\'{e}rtices:

\begin{center}
\begin{picture}(420,105)
 \put(20,50){\circle*{5}}
 \put(20,35){\makebox(0,0)[b]{a}}
 \put(50,50){\circle*{5}}
 \put(50,35){\makebox(0,0)[b]{b}}
 \put(80,50){\circle*{5}}
 \put(80,35){\makebox(0,0)[b]{c}}
 \put(110,50){\circle*{5}}
 \put(110,35){\makebox(0,0)[b]{d}}
 \put(140,50){\circle*{5}}
 \put(140,35){\makebox(0,0)[b]{e}}
 \put(20,50){\line(1,0){120}}
 
 \put(200,50){\circle*{5}}
 \put(200,35){\makebox(0,0)[b]{a}}
 \put(230,50){\circle*{5}}
 \put(230,35){\makebox(0,0)[b]{b}}
 \put(230,80){\circle*{5}}
 \put(230,85){\makebox(0,0)[b]{e}}
 \put(260,50){\circle*{5}}
 \put(260,35){\makebox(0,0)[b]{c}}
 \put(290,50){\circle*{5}}
 \put(290,35){\makebox(0,0)[b]{d}}
 \put(200,50){\line(1,0){90}}
 \put(230,50){\line(0,1){30}}
 
 \put(350,50){\circle*{5}}
 \put(350,35){\makebox(0,0)[b]{a}}
 \put(380,50){\circle*{5}}
 \put(390,35){\makebox(0,0)[b]{b}}
 \put(410,50){\circle*{5}}
 \put(410,35){\makebox(0,0)[b]{c}}
 \put(380,20){\circle*{5}}
 \put(380,15){\makebox(0,0)[t]{d}}
 \put(380,80){\circle*{5}}
 \put(380,85){\makebox(0,0)[b]{e}}
 \put(350,50){\line(1,0){60}}
 \put(380,20){\line(0,1){60}}
\end{picture}
\end{center}

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

\newslide{ÁRVORES E GRAFOS DIRECIONADOS (2)}
\hypertarget{arvores-gds-2}{}

\noindent \begin{description}
 \item[Proposi\c{c}\~{a}o:] \
 
       As seguintes afirmativas s\~{a}o equivalentes, para um grafo $G$:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $G$ \'{e} uma \'{a}rvore.
        \item $G$ n\~{a}o tem la\c{c}os, e quaisquer 2 v\'{e}rtices distintos de $G$ s\~{a}o
              unidos por exatamente 1 caminho simples.
        \item $G$ \'{e} conexo e $V_G=E_G+1$.
        \item $G$ \'{e} ac\'{\i}clico e $V_G=E_G+1$.
        \item $G$ \'{e} ac\'{\i}clico, e se quaisquer 2 v\'{e}rtices de $G$ forem unidos por
              uma aresta, ent\~{a}o o grafo resultante ter\'{a} exatamente 1 ciclo.
       \end{list}
       
 \item[Prova:] \
 
       Basta mostrar que (a) $\Rightarrow$ (b) $\Rightarrow$ (c) $\Rightarrow$
       (d) $\Rightarrow$ (e) $\Rightarrow$ (a).
\end{description}

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

\newslide{ÁRVORES E GRAFOS DIRECIONADOS (3)}
\hypertarget{arvores-gds-3}{}

\noindent \begin{description}
 \item[Proposi\c{c}\~{a}o:] \
 
       Uma \'{a}rvore $G$ com 2 ou mais v\'{e}rtices tem pelo menos 2 v\'{e}rtices de
       grau 1.

 \item[Prova:] \
 
       Tome o maior (ou um dos maiores) caminho simples em $G$. Como $G$ \'{e}
       ac\'{\i}clico, as extremidades deste caminho t\^{e}m grau 1.
\end{description}

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

\newslide{ÁRVORES E GRAFOS DIRECIONADOS (4)}
\hypertarget{arvores-gds-4}{}

\noindent Uma {\bf \'{a}rvore geradora} ({\it spanning tree\/}) para um grafo $G$ \'{e}
um subgrafo gerador de $G$ que \'{e} uma \'{a}rvore.

\vspace*{10mm}
\noindent \begin{description}
 \item[Proposi\c{c}\~{a}o:] \
 
       $G$ \'{e} conexo se, e somente se, tem \'{a}rvore geradora.

 \item[Prova:] \
 
       Se $G$ tem \'{a}rvore geradora, ent\~{a}o obviamente \'{e} conexo. Por indu\c{c}\~{a}o sobre
       o n\'{u}mero de arestas, mostra-se que qualquer grafo conexo tem \'{a}rvore
       geradora.
\end{description}

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

\newslide{ÁRVORES E GRAFOS DIRECIONADOS (5)}
\hypertarget{arvores-gds-5}{}

\noindent \underline{Algoritmo para contruir \'{a}rvore geradora para um grafo
conexo $G$}:

\vspace*{5mm}
\begin{tabbing}
xxxx\=xxxx\= \kill
Escolha um v\a'ertice $v$ de $\mbox{\bf V}_G$, e fa\c{c}a $\mbox{\bf V}_A
 \leftarrow \{v\}$; \\
$\mbox{\bf E}_A \leftarrow \{\}$; \\
{\bf enquanto} $\mbox{\bf V}_G - \mbox{\bf V}_A \not=\{\}$ {\bf fa\c{c}a} \\
   \> escolha uma aresta $\{x,y\} \in \mbox{\bf E}_G$, com $x\in\mbox{\bf V}_A$ e
      $y\not\in\mbox{\bf V}_A$; \\
   \> $\mbox{\bf V}_A \leftarrow \mbox{\bf V}_A \cup \{y\}$; \\
   \> $\mbox{\bf E}_A \leftarrow \mbox{\bf E}_A \cup \{x,y\}$ \\
{\bf fim}
\end{tabbing}

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

\newslide{ÁRVORES E GRAFOS DIRECIONADOS (6)}
\hypertarget{arvores-gds-6}{}

\noindent Tal algoritmo pode ser usado (por um outro) para determinar:

\begin{itemize}
 \item se $G$ \'{e} conexo.
 \item o n\'{u}mero de componentes de $G$.
 \item se $G$ \'{e} c\'{\i}clico.
 \item o n\'{u}mero de ciclos de $G$.
\end{itemize}

\vspace*{10mm}
\noindent O {\bf peso} de um grafo valorado \'{e} a soma dos pesos das arestas do
grafo

\vspace*{10mm}
\noindent Uma {\bf \'{a}rvore geradora m\'{\i}nima} \'{e} uma \'{a}rvore geradora de peso m\'{\i}nimo.

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

\newslide{ÁRVORES E GRAFOS DIRECIONADOS (7)}
\hypertarget{arvores-gds-7}{}

\noindent Algoritmo para contruir uma \underline{\'{a}rvore geradora m\'{\i}nima} para um
grafo conexo $G$:

\vspace*{5mm}
\begin{tabbing}
xxxx\=xxxx\= \kill
Escolha um v\a'ertice $v$ de $\mbox{\bf V}_G$, e fa\c{c}a $\mbox{\bf V}_A
 \leftarrow \{v\}$; \\
$\mbox{\bf E}_A \leftarrow \{\}$; \\
{\bf enquanto} $\mbox{\bf V}_G - \mbox{\bf V}_A \not=\{\}$ {\bf fa\c{c}a} \\
   \> escolha uma aresta \underline{de menor peso} $\{x,y\} \in \mbox{\bf E}_G$,
      \\
   \> \>   com $x\in\mbox{\bf V}_A$ e $y\not\in\mbox{\bf V}_A$; \\
   \> $\mbox{\bf V}_A \leftarrow \mbox{\bf V}_A \cup \{y\}$; \\
   \> $\mbox{\bf E}_A \leftarrow \mbox{\bf E}_A \cup \{x,y\}$ \\
{\bf fim}
\end{tabbing}

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

\newslide{ÁRVORES E GRAFOS DIRECIONADOS (8)}
\hypertarget{arvores-gds-8}{}

\noindent \underline{Exemplo}:

\begin{center}
\begin{picture}(130,150)
 \put(50,10){\makebox(0,0){e}}
 \put(50,20){\circle*{5}}
 \put(50,20){\line(-1,1){30}}
 \put(30,35){\makebox(0,0)[r]{\normalsize 12}} 
 \put(50,20){\line(1,1){30}}
 \put(70,35){\makebox(0,0)[l]{\normalsize 3}} 
 
 \put(10,50){\makebox(0,0){f}}
 \put(20,50){\circle*{5}}
 \put(20,50){\line(1,0){90}}
 \put(50,53){\makebox(0,0)[b]{\normalsize 5}} 
 \put(95,53){\makebox(0,0)[b]{\normalsize 1}} 
 \put(85,40){\makebox(0,0){d}}
 \put(80,50){\circle*{5}}
 \put(120,50){\makebox(0,0){c}}
 \put(110,50){\circle*{5}}
 \put(110,50){\line(0,1){60}}
 \put(113,80){\makebox(0,0)[l]{\normalsize 1}} 
 
 \put(110,120){\makebox(0,0){b}}
 \put(110,110){\circle*{5}}
 \put(110,110){\line(-1,0){90}}
 \put(65,113){\makebox(0,0)[b]{\normalsize 1}} 
 \put(110,110){\line(-1,-2){30}}
 \put(90,80){\makebox(0,0)[r]{\normalsize 1}} 
 
 \put(20,120){\makebox(0,0){a}}
 \put(20,110){\circle*{5}}
 \put(20,110){\line(0,-1){60}}
 \put(17,80){\makebox(0,0)[r]{\normalsize 12}} 
\end{picture}
\end{center}

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

\newslide{ÁRVORES E GRAFOS DIRECIONADOS (9)}
\hypertarget{arvores-gds-9}{}

\noindent Uma {\bf \'{a}rvore enraizada} \'{e} uma \'{a}rvore com um v\'{e}rtice especificado
como {\bf raiz}.

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

\vspace*{5mm}
\noindent Seja $P_v$ o caminho simples da raiz at\'{e} o v\'{e}rtice $v$. Ent\~{a}o:

\begin{itemize}
 \item {\bf n\'{\i}vel} de $v$: n\'{u}mero de arestas de $P_v$.
 \item {\bf altura} da \'{a}rvore: o maior n\'{\i}vel.
 \item {\bf ancestral} de $v$: v\'{e}rtice $w$ de $P_v$, diferente de $v$; neste
       caso, $v$ \'{e} {\bf descendente} de $w$.
 \item {\bf ancestral imediato} ({\bf pai}) de $v$: ancestral de $v$,
       adjacente a $v$; neste caso, $v$ \'{e} {\bf descendente imediato}
       ({\bf filho}) de $w$.
       
%--------------------------------------------------------------------------------------------

\newslide{ÁRVORES E GRAFOS DIRECIONADOS (10)}
\hypertarget{arvores-gds-10}{}
       
 \item {\bf folha}: v\'{e}rtice sem filhos.
 \item {\bf v\'{e}rtice interno}: o que n\~{a}o \'{e} folha.
 \item \'{a}rvore $m$-{\bf \'{a}ria}: o n\'{u}mero m\'{a}ximo de filhos \'{e} $m$.
 \item \'{a}rvore {\bf estritamente} $m$-{\bf \'{a}ria} ({\it full\/}): cada v\'{e}rtice
       interno tem exatamente $m$ filhos.
 \item \'{a}rvore {\bf completa}: as folhas t\^{e}m o mesmo n\'{\i}vel.
 \item {\bf sub\'{a}rvore} de uma \'{a}rvore enraizada: aquela constitu\'{\i}da de um
       v\'{e}rtice e todos os seus descendentes.
\end{itemize}

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

\newslide{ÁRVORES E GRAFOS DIRECIONADOS (11)}
\hypertarget{arvores-gds-11}{}

\noindent \begin{description}
 \item[Proposi\c{c}\~{a}o:] \
 
       Uma \'{a}rvore estritamente $m$-\'{a}ria com $k$ v\'{e}rtices internos tem
       $mk+1$ v\'{e}rtices.

 \item[Prova:] \
 
       Existem $mk$ v\'{e}rtices filhos, mais a raiz.
\end{description}

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

\newslide{ÁRVORES E GRAFOS DIRECIONADOS (12)}
\hypertarget{arvores-gds-12}{}

\noindent \begin{description}
 \item[Proposi\c{c}\~{a}o:] \
 
       Uma \'{a}rvore $m$-\'{a}ria de altura $h$ tem, no m\'{a}ximo, $m^h$ folhas
       (convencionando-se que $0^0=1$).

 \item[Prova:] \
 
       Por indu\c{c}\~{a}o sobre a altura da \'{a}rvore.
\end{description}

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

\newslide{ÁRVORES E GRAFOS DIRECIONADOS (13)}
\hypertarget{arvores-gds-13}{}

\noindent \begin{description}
 \item[Corol\'{a}rio:] \
 
       Uma \'{a}rvore $m$-\'{a}ria com $k$ folhas tem altura, no m\'{\i}nimo, $\log_mk$.

 \item[Prova:] \
 
       Se a altura fosse menor que $log_mk$, o n\'{u}mero de folhas seria menor
       do que $m^{\log_mk}=k$.
\end{description}

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

\newslide{ALGUMAS APLICAÇÕES DE ÁRVORES (1)}
\hypertarget{aplicacoes-1}{}

\noindent {\bf Algumas Aplica\c{c}\~{o}es de \'{A}rvores}

\vspace*{5mm}
\begin{itemize}
 \item Tem-se um certo n\'{u}mero de unidades de comunica\c{c}\~{a}o, e deseja-se
       construir uma rede conectando todas elas. Sabe-se o custo de construir
       uma conex\~{a}o entre quaisquer pares de unidades. O problema \'{e} construir uma
       rede o mais barata poss\'{\i}vel.
       
       \underline{Soluc\~{a}o}: \'{a}rvore geradora m\'{\i}nima para o grafo valorado
       completo que representa a rede.
       
%--------------------------------------------------------------------------------------------

\newslide{ALGUMAS APLICAÇÕES DE ÁRVORES (2)}
\hypertarget{aplicacoes-2}{}
       
 \item {\bf O problema do caixeiro viajante}: determinar um menor ciclo
       Hamiltoniano em um grafo valorado completo. Sabe-se que {\it pesquisa
       exaustiva\/} \'{e} ineficiente, e que a aproxima\c{c}\~{a}o obtida pelo {\it
       algoritmo do vizinho mais pr\'{o}ximo\/} se deteriora com o crescimento do
       grafo. Um algoritmo melhor, usando \'{a}rvore geradora m\'{\i}nima (AGM):
       
       \begin{enumerate}
        \item Encontre uma AGM $A$ para o grafo $G$;
        \item converta $A$ para um grafo Euleriano $H$, duplicando cada aresta
              de $A$;
        \item encontre um circuito Euleriano para $H$;
        \item converta este circuito Euleriano para um ciclo Hamiltoniano para
              $G$, ``pegando atalhos'', quando necess\'{a}rio.
       \end{enumerate}
       
%--------------------------------------------------------------------------------------------

\newslide{ALGUMAS APLICAÇÕES DE ÁRVORES (3)}
\hypertarget{aplicacoes-3}{}

       \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}
              %--------------------------------------------------------------------------------------------

\newslide{ALGUMAS APLICAÇÕES DE ÁRVORES (4)}
\hypertarget{aplicacoes-4}{}

       \begin{description}
        \item[Proposi\c{c}\~{a}o:] \
        
              Seja $G$ um grafo Euclidiano valorado completo. Seja $P_0$ o
              tamanho de um ciclo Hamiltoniano m\'{\i}nimo, e $P_{HA}$ o tamanho de
              um ciclo obtido pela heur\'{\i}stica da \'{a}rvore geradora m\'{\i}nima. Ent\~{a}o
              $P_{HA}/P_0<2$.
       \end{description}

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

\newslide{ALGUMAS APLICAÇÕES DE ÁRVORES (5)}
\hypertarget{aplicacoes-5}{}       
       
 \item Um algoritmo que ordena n\'{u}meros distintos por compara\c{c}\~{o}es pode ser
       representado por uma \'{a}rvore estritamente bin\'{a}ria, denominada {\it \'{a}rvore
       de decis\~{a}o\/}.

       \underline{Exemplo}: ordenando 3 n\'{u}meros:
       
       \begin{center}
       \begin{picture}(400,200)
        \put(200,180){\oval(70,20)}
        \put(200,180){\makebox(0,0){$n_1<n_2$}}
        
        \put(175,170){\line(-3,-1){90}}
        \put(85,130){\oval(70,20)}
        \put(85,130){\makebox(0,0){$n_2<n_3$}}
        
        \put(70,120){\line(-2,-1){60}}
        \put(-25,80){\framebox{$n_1,n_2,n_3$}}
        
        \put(100,120){\line(2,-1){60}}
        \put(160,80){\oval(70,20)}
        \put(160,80){\makebox(0,0){$n_1<n_3$}}
        
        \put(140,70){\line(-1,-1){30}}
        \put(75,30){\framebox{$n_1,n_3,n_2$}}
        
        \put(180,70){\line(1,-1){30}}
        \put(175,30){\framebox{$n_3,n_1,n_2$}}
        
        \put(225,170){\line(3,-1){90}}
        \put(315,130){\oval(70,20)}
        \put(315,130){\makebox(0,0){$n_1<n_3$}}
        
        \put(300,120){\line(-2,-1){60}}
        \put(205,80){\framebox{$n_2,n_1,n_3$}}
        
        \put(330,120){\line(2,-1){60}}
        \put(390,80){\oval(70,20)}
        \put(390,80){\makebox(0,0){$n_2<n_3$}}
        
        \put(370,70){\line(-1,-1){30}}
        \put(305,30){\framebox{$n_2,n_3,n_1$}}
        
        \put(410,70){\line(1,-1){30}}
        \put(405,30){\framebox{$n_3,n_2,n_1$}}
       \end{picture}
       \end{center}
       
%--------------------------------------------------------------------------------------------

\newslide{ALGUMAS APLICAÇÕES DE ÁRVORES (6)}
\hypertarget{aplicacoes-6}{}       
       
       \begin{description}
        \item[Proposi\c{c}\~{a}o:] \
        
              Qualquer \'{a}rvore de decis\~{a}o que ordena $n$ n\'{u}meros distintos tem
              altura no m\'{\i}nimo $\log_2 n!$.
              
        \item[Prova:] \
         
              O resultado do ordenamento pode ser qualquer uma das $n!$
              permuta\c{c}\~{o}es poss\'{\i}veis. Logo, a \'{a}rvore tem $n!$ folhas e,
              portanto, altura no m\'{\i}nimo $\log_2 n!$.
       \end{description}

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

\newslide{ALGUMAS APLICAÇÕES DE ÁRVORES (7)}
\hypertarget{aplicacoes-7}{}
       
       \begin{description}
        \item[Corol\'{a}rio:] \
        
              Qualquer algoritmo que ordena $n$ n\'{u}meros distintos por
              compara\c{c}\~{o}es requer, no m\'{\i}nimo, $\frac{1}{4}nlog_2n$ compara\c{c}\~{o}es
              (no pior caso) para $n\geq 4$.

              
        \item[Prova:] \
         
              Para $n\geq 1$, $n!\geq (n/2)^{n/2}$ e, portanto, tem-se
              tamb\'{e}m que $\log_2 n!\geq (n/2)log_2(n/2)$. Mas,
              $(n/2)log_2(n/2)\geq (n/4)log_2(n)$ para $n\geq 4$.
       \end{description}
\end{itemize}

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

\newslide{GRAFOS DIRECIONADOS (1)}
\hypertarget{grafos-direcionados-1}{}

\noindent {\bf Grafos Direcionados}

\vspace*{10mm}
\noindent Um {\bf grafo direcionado} (d\'{\i}grafo) \'{e} um grafo cujas arestas
(direcionadas) s\~{a}o pares \underline{ordenados}.

\vspace*{5mm}
\begin{itemize}
 \item Uma aresta $(v,w)$ \'{e} dita ter a {\bf dire\c{c}\~{a}o de} $v$ {\bf para} $w$, e \'{e}
       representada geometricamente por uma {\bf seta}. A aresta {\bf sai de}
       $v$ e {\bf entra em} $w$.
 \item Os v\'{e}rtices de uma aresta s\~{a}o ditos {\bf adjacentes}, e uma aresta \'{e} {\bf
       incidente} aos v\'{e}rtices que cont\'{e}m.
 \item Grafo direcionado {\bf completo}: aquele obtido de algum $K_n$,
       direcionando-se as arestas.
       
%--------------------------------------------------------------------------------------------

\newslide{GRAFOS DIRECIONADOS (2)}
\hypertarget{grafos-direcionados-2}{}
       
 \item {\bf Grau de entrada} de um v\'{e}rtice $v$, $\mbox{\it gent\/}(v)$: n\'{u}mero
       de arestas que entram em $v$.
 \item {\bf Grau de sa\'{\i}da} de um v\'{e}rtice $v$, $\mbox{\it gsai\/}(v)$: n\'{u}mero de
       arestas que saem de $v$.
 \item {\bf Grau} de um v\'{e}rtice $v$, $\mbox{\it grau\/}(v)=\mbox{\it gent\/}(v)
        +\mbox{\it gsai\/}(v)$.
 \item {\it Grafo subjacente} de um grafo direcionado: aquele obtido
       re\-mo\-ven\-do-se as dire\c{c}\~{o}es das arestas.
 \item Grafo direcionado {\bf planar}: aquele cujo grafo subjacente \'{e} planar.
\end{itemize}

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

\newslide{GRAFOS DIRECIONADOS (3)}
\hypertarget{grafos-direcionados-3}{}

\noindent \underline{Exemplo}:

\begin{center}
\begin{picture}(140,130)
 \put(40,80){\circle*{5}}
 \put(50,87){\makebox(0,0){a}}
 \put(30,80){\oval(20,10)}
 \put(35,85){\vector(-1,0){10}}
 
 \put(120,80){\circle*{5}}
 \put(130,85){\makebox(0,0){b}}
 \put(80,80){\oval(80,40)}
 \put(70,100){\vector(1,0){10}}
 \put(40,80){\line(1,0){80}}
 \put(70,80){\vector(1,0){10}}
 \put(90,60){\vector(-1,0){10}}
 
 \put(80,80){\oval(80,80)[b]}
 \put(100,40){\circle*{5}}
 \put(100,32){\makebox(0,0){c}}
 \put(90,40){\vector(-1,0){10}}
 \put(120,70){\vector(0,-1){10}}
 
 \put(80,50){\circle*{5}}
 \put(90,50){\makebox(0,0){d}}
\end{picture}
\end{center}
\begin{itemize}
 \item $\mbox{\it gent\/}(a)=\mbox{\it gsai\/}(a)=3$
 \item $\mbox{\it gent\/}(b)=\mbox{\it gsai\/}(b)=2$
 \item $\mbox{\it gent\/}(c)=\mbox{\it gsai\/}(c)=1$
 \item $\mbox{\it gent\/}(d)=\mbox{\it gsai\/}(d)=0$
 \item Tal grafo \'{e} planar, mas n\~{a}o \'{e} completo.
\end{itemize}

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

\newslide{GRAFOS DIRECIONADOS (4)}
\hypertarget{grafos-direcionados-4}{}

\noindent Um {\bf caminho direcionado de} $x_1$ {\bf a} $x_2$ \'{e} uma sequ\^{e}ncia
de v\'{e}rtices e arestas
\[x_1 (x_1, x_2) x_2 (x_2, x_3) x_3 \ldots x_{n-1} (x_{n-1}, x_n) x_n\]
(abr.: $x_1 x_2 x_3 \ldots x_{n-1} x_n$).

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

\newslide{GRAFOS DIRECIONADOS (5)}
\hypertarget{grafos-direcionados-5}{}

\noindent Os seguintes termos t\^{e}m defini\c{c}\~{o}es an\'{a}logas aos correspondentes
relativos a grafos n\~{a}o direcionados:

\begin{itemize}
 \item {\bf extremidades} de um caminho direcionado;
 \item {\bf caminho direcionado fechado};
 \item {\bf caminho direcionado gerador};
 \item {\bf caminho direcionado simples };
 \item {\bf trajeto direcionado};
 \item {\bf circuito direcionado};
 \item {\bf ciclo direcionado};
 \item {\bf circuito/trajeto direcionado Euleriano};
 \item {\bf ciclo/caminho direcionado Hamiltoniano}.
\end{itemize}

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

\newslide{GRAFOS DIRECIONADOS (6)}
\hypertarget{grafos-direcionados-6}{}

\noindent \underline{Exemplo}:

\begin{center}
\begin{picture}(380,100)
 \put(20,40){\circle*{5}}
 \put(10,30){\makebox(0,0){d}}
 \put(20,40){\line(0,1){40}}
 \put(20,40){\vector(0,1){20}}
 \put(20,80){\circle*{5}}
 \put(10,90){\makebox(0,0){a}}
 \put(20,80){\line(1,0){40}}
 \put(20,80){\vector(1,0){20}}
 \put(60,80){\circle*{5}}
 \put(70,90){\makebox(0,0){b}}
 \put(60,80){\line(0,-1){40}}
 \put(60,80){\vector(0,-1){20}}
 \put(60,40){\circle*{5}}
 \put(70,30){\makebox(0,0){c}}
 \put(60,40){\line(-1,0){40}}
 \put(60,40){\vector(-1,0){20}}
 \put(40,10){\makebox(0,0){$G$}}
 
 \put(120,40){\circle*{5}}
 \put(110,30){\makebox(0,0){d}}
 \put(120,40){\line(0,1){40}}
 \put(120,40){\vector(0,1){20}}
 \put(120,80){\circle*{5}}
 \put(110,90){\makebox(0,0){a}}
 \put(120,80){\line(1,0){40}}
 \put(120,80){\vector(1,0){20}}
 \put(120,80){\line(1,-1){40}}
 \put(120,80){\vector(1,-1){20}}
 \put(160,80){\circle*{5}}
 \put(170,90){\makebox(0,0){b}}
 \put(160,80){\line(0,-1){40}}
 \put(160,80){\vector(0,-1){20}}
 \put(160,40){\circle*{5}}
 \put(170,30){\makebox(0,0){c}}
 \put(160,40){\line(-1,0){40}}
 \put(160,40){\vector(-1,0){20}}
 \put(140,10){\makebox(0,0){$H$}}
 
 \put(220,40){\circle*{5}}
 \put(210,30){\makebox(0,0){d}}
 \put(220,40){\line(0,1){40}}
 \put(220,40){\vector(0,1){20}}
 \put(220,80){\circle*{5}}
 \put(210,90){\makebox(0,0){a}}
 \put(220,80){\line(1,-1){20}}
 \put(220,80){\vector(1,-1){10}}
 \put(260,80){\circle*{5}}
 \put(270,90){\makebox(0,0){b}}
 \put(260,80){\line(-1,-1){20}}
 \put(260,80){\vector(-1,-1){10}}
 \put(260,40){\circle*{5}}
 \put(270,30){\makebox(0,0){c}}
 \put(260,40){\line(0,1){40}}
 \put(260,40){\vector(0,1){20}}
 \put(240,60){\circle*{5}}
 \put(240,70){\makebox(0,0){e}}
 \put(240,60){\line(-1,-1){20}}
 \put(240,60){\vector(-1,-1){10}}
 \put(240,60){\line(1,-1){20}}
 \put(240,60){\vector(1,-1){10}}
 \put(240,10){\makebox(0,0){$I$}}
 
 \put(320,40){\circle*{5}}
 \put(310,30){\makebox(0,0){d}}
 \put(320,80){\circle*{5}}
 \put(310,90){\makebox(0,0){a}}
 \put(320,80){\line(1,-1){20}}
 \put(320,80){\vector(1,-1){10}}
 \put(360,80){\circle*{5}}
 \put(370,90){\makebox(0,0){b}}
 \put(360,80){\line(-1,-1){20}}
 \put(360,80){\vector(-1,-1){10}}
 \put(360,40){\circle*{5}}
 \put(370,30){\makebox(0,0){c}}
 \put(360,40){\line(0,1){40}}
 \put(360,40){\vector(0,1){20}}
 \put(340,60){\circle*{5}}
 \put(340,70){\makebox(0,0){e}}
 \put(340,60){\line(-1,-1){20}}
 \put(340,60){\vector(-1,-1){10}}
 \put(340,60){\line(1,-1){20}}
 \put(340,60){\vector(1,-1){10}}
 \put(340,10){\makebox(0,0){$J$}}
\end{picture}
\end{center}
\begin{tabular}{c|cccc}
  &  Euleriano & Hamiltoniano & traj. Euleriano & cam. Hamiltoniano \\
 \hline
  $G$  &    sim     &    sim       &       n\~{a}o         &      sim \\
  $H$  &    n\~{a}o     &    sim       &       sim         &      sim \\
  $I$  &    sim     &    n\~{a}o       &       n\~{a}o         &      n\~{a}o \\
  $I$  &    n\~{a}o     &    n\~{a}o       &       sim         &      n\~{a}o \\
\end{tabular}

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

\newslide{GRAFOS DIRECIONADOS (7)}
\hypertarget{grafos-direcionados-7}{}

\begin{itemize}
 \item Grafo direcionado {\bf fortemente conexo}: existe caminho direcionado de
       $u$ a $v$, para quaisquer v\'{e}rtices $u$ e $v$.
 \item Grafo direcionado {\bf fracamente conexo}: o grafo subjacente \'{e} conexo.
\end{itemize}

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

\begin{center}
\begin{picture}(380,100)
 \put(20,40){\circle*{5}}
 \put(10,30){\makebox(0,0){d}}
 \put(20,40){\line(0,1){40}}
 \put(20,40){\vector(0,1){20}}
 \put(20,80){\circle*{5}}
 \put(10,90){\makebox(0,0){a}}
 \put(20,80){\line(1,0){40}}
 \put(20,80){\vector(1,0){20}}
 \put(60,80){\circle*{5}}
 \put(70,90){\makebox(0,0){b}}
 \put(60,80){\line(0,-1){40}}
 \put(60,80){\vector(0,-1){20}}
 \put(60,40){\circle*{5}}
 \put(70,30){\makebox(0,0){c}}
 \put(60,40){\line(-1,0){40}}
 \put(60,40){\vector(-1,0){20}}
 \put(40,10){\makebox(0,0){$G$}}
 
 \put(120,40){\circle*{5}}
 \put(110,30){\makebox(0,0){d}}
 \put(120,40){\line(0,1){40}}
 \put(120,40){\vector(0,1){20}}
 \put(120,80){\circle*{5}}
 \put(110,90){\makebox(0,0){a}}
 \put(120,80){\line(1,0){40}}
 \put(120,80){\vector(1,0){20}}
 \put(120,80){\line(1,-1){40}}
 \put(120,80){\vector(1,-1){20}}
 \put(160,80){\circle*{5}}
 \put(170,90){\makebox(0,0){b}}
 \put(160,80){\line(0,-1){40}}
 \put(160,80){\vector(0,-1){20}}
 \put(160,40){\circle*{5}}
 \put(170,30){\makebox(0,0){c}}
 \put(160,40){\line(-1,0){40}}
 \put(160,40){\vector(-1,0){20}}
 \put(140,10){\makebox(0,0){$H$}}
 
 \put(220,40){\circle*{5}}
 \put(210,30){\makebox(0,0){d}}
 \put(220,40){\line(0,1){40}}
 \put(220,40){\vector(0,1){20}}
 \put(220,80){\circle*{5}}
 \put(210,90){\makebox(0,0){a}}
 \put(220,80){\line(1,-1){20}}
 \put(220,80){\vector(1,-1){10}}
 \put(260,80){\circle*{5}}
 \put(270,90){\makebox(0,0){b}}
 \put(260,80){\line(-1,-1){20}}
 \put(260,80){\vector(-1,-1){10}}
 \put(260,40){\circle*{5}}
 \put(270,30){\makebox(0,0){c}}
 \put(260,40){\line(0,1){40}}
 \put(260,40){\vector(0,1){20}}
 \put(240,60){\circle*{5}}
 \put(240,70){\makebox(0,0){e}}
 \put(240,60){\line(-1,-1){20}}
 \put(240,60){\vector(-1,-1){10}}
 \put(240,60){\line(1,-1){20}}
 \put(240,60){\vector(1,-1){10}}
 \put(240,10){\makebox(0,0){$I$}}
 
 \put(320,40){\circle*{5}}
 \put(310,30){\makebox(0,0){d}}
 \put(320,80){\circle*{5}}
 \put(310,90){\makebox(0,0){a}}
 \put(320,80){\line(1,-1){20}}
 \put(320,80){\vector(1,-1){10}}
 \put(360,80){\circle*{5}}
 \put(370,90){\makebox(0,0){b}}
 \put(360,80){\line(-1,-1){20}}
 \put(360,80){\vector(-1,-1){10}}
 \put(360,40){\circle*{5}}
 \put(370,30){\makebox(0,0){c}}
 \put(360,40){\line(0,1){40}}
 \put(360,40){\vector(0,1){20}}
 \put(340,60){\circle*{5}}
 \put(340,70){\makebox(0,0){e}}
 \put(340,60){\line(-1,-1){20}}
 \put(340,60){\vector(-1,-1){10}}
 \put(340,60){\line(1,-1){20}}
 \put(340,60){\vector(1,-1){10}}
 \put(340,10){\makebox(0,0){$J$}}
\end{picture}
\end{center}
\begin{itemize}
 \item $G$, $H$ e $I$ s\~{a}o fortemente conexos;
 \item $J$ n\~{a}o \'{e} fortemente conexo, mas \'{e} fracamente conexo.
\end{itemize}

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

\newslide{GRAFOS DIRECIONADOS (8)}
\hypertarget{grafos-direcionados-8}{}

\noindent Dois grafos direcionados $G$ e $H$ s\~{a}o {\bf isomorfos}, $G\cong H$,
se e somente se:

\begin{itemize}
 \item existe uma correspond\^{e}ncia um-para-um entre os v\'{e}rtices de $G$ e $H$, tal
       que:
 \item o n\'{u}mero de arestas de $u$ para $v$ em $G$ \'{e} id\^{e}ntico ao n\'{u}mero de
       arestas do v\'{e}rtice correspondente a $u$ para o v\'{e}rtice correspondente a
       $v$ em $H$, para quaisquer v\'{e}rtices $u$ e $v$.
\end{itemize}

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

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

\noindent {\bf Caminhamentos}

\vspace*{10mm}
\begin{description}
 \item[Proposi\c{c}\~{a}o:] \
 
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Um grafo direcionado fracamente conexo \'{e} Euleriano se, e somente
              se, $\mbox{\it gent\/}(v)=\mbox{\it gsai\/}(v)$ para todo $v$.
        \item Um grafo direcionado fracamente conexo tem trajeto direcionado
              Euleriano se, e somente se, $\mbox{\it gent\/}(v)=\mbox{\it
              gsai\/}(v)$ para todo $v$, exceto dois; para um deles o grau de
              entrada \'{e} 1 a mais que o grau de sa\'{\i}da, e para o outro o grau de
              sa\'{\i}da \'{e} 1 a mais que o grau de entrada.
        \item Se $G$ \'{e} um grafo direcionado fracamente conexo tal que
              $\sum_{v\in \mbox{\bf V}}|\mbox{\it gsai\/}(v)-\mbox{\it
              gent\/}(v)|=2k$, ent\~{a}o as arestas podem ser particionadas por $k$
              trajetos direcionados.
       \end{list}
\end{description}

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

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

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

\vspace*{10mm}

\noindent Usando o fato de que um ciclo Hamiltoniano cont\'{e}m {\it exatamente
       duas\/} das arestas incidentes com cada v\'{e}rtice, {\it uma entrando e
       outra saindo\/}:

\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(0,1){60}}
 \put(20,20){\vector(0,1){30}}
 \put(80,10){\makebox(0,0){e}}
 \put(80,20){\circle*{5}}
 \put(80,20){\line(-1,0){60}}
 \put(80,20){\vector(-1,0){30}}
 \put(80,20){\line(1,0){60}}
 \put(80,20){\vector(1,0){30}}
 \put(150,10){\makebox(0,0){d}}
 \put(140,20){\circle*{5}}
 \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(0,-1){60}}
 \put(140,80){\vector(0,-1){30}}
 \put(80,90){\makebox(0,0){b}}
 \put(80,80){\circle*{5}}
 \put(80,80){\line(1,0){60}}
 \put(80,80){\vector(1,0){30}}
 \put(80,80){\line(0,-1){60}}
 \put(80,80){\vector(0,-1){30}}
 \put(10,90){\makebox(0,0){a}}
 \put(20,80){\circle*{5}}
 \put(20,80){\line(1,0){60}}
 \put(20,80){\vector(1,0){30}}
 \put(20,80){\line(1,-1){30}}
 \put(20,80){\vector(1,-1){15}}
 \put(60,60){\makebox(0,0){g}}
 \put(50,50){\circle*{5}}
 \put(50,50){\line(1,-1){30}}
 \put(50,50){\vector(1,-1){15}}
 \put(68,35){\line(-1,1){30}}
\end{picture}

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

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

\begin{description}
 \item[Proposi\c{c}\~{a}o:] \
        
       Todo grafo direcionado completo tem caminho direcionado Hamiltoniano.
              
 \item[Prova:] \
        
       Por indu\c{c}\~{a}o sobre o n\'{u}mero de v\'{e}rtices.
\end{description}

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

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

\vspace*{10mm}
\noindent {\bf Grupo sumidouro:} $\mbox{\bf V'}\subset\mbox{\bf V}$ tal que
qualquer aresta que contenha v\'{e}rtices $v\in\mbox{\bf V'}$ e
$w\in\mbox{\bf V}-\mbox{\bf V'}$, {\it sai\/} de $w$ e {\it entra\/} em $v$.

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

\begin{center}
\begin{picture}(280,100)
 \put(20,40){\circle*{5}}
 \put(10,30){\makebox(0,0){d}}
 \put(20,40){\line(0,1){40}}
 \put(20,40){\vector(0,1){20}}
 \put(20,80){\circle*{5}}
 \put(10,90){\makebox(0,0){a}}
 \put(20,80){\line(1,0){40}}
 \put(20,80){\vector(1,0){20}}
 \put(60,80){\circle*{5}}
 \put(70,90){\makebox(0,0){b}}
 \put(60,80){\line(0,-1){40}}
 \put(60,80){\vector(0,-1){20}}
 \put(60,40){\circle*{5}}
 \put(70,30){\makebox(0,0){c}}
 \put(60,40){\line(-1,0){40}}
 \put(60,40){\vector(-1,0){20}}
 \put(40,10){\makebox(0,0){$G$}}
 
 \put(220,40){\circle*{5}}
 \put(210,30){\makebox(0,0){c}}
 \put(220,80){\circle*{5}}
 \put(210,90){\makebox(0,0){d}}
 \put(220,80){\line(1,0){40}}
 \put(220,80){\vector(1,0){20}}
 \put(220,80){\line(0,-1){40}}
 \put(220,80){\vector(0,-1){20}}
 \put(260,80){\circle*{5}}
 \put(270,90){\makebox(0,0){a}}
 \put(260,40){\circle*{5}}
 \put(270,30){\makebox(0,0){b}}
 \put(260,40){\line(-1,0){40}}
 \put(260,40){\vector(-1,0){20}}
 \put(260,40){\line(0,1){40}}
 \put(260,40){\vector(0,1){20}}
 \put(240,10){\makebox(0,0){$H$}}
\end{picture}
\end{center}

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

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

\noindent Defini\c{c}\~{o}es auxiliares adicionais:

\vspace*{10mm}
\begin{itemize}
 \item {\bf Circuito direcionado simples:} circuito direcionado no qual
       $x_1=x_n$ \'{e} o \'{u}nico v\'{e}rtice repetido. ($x_1$ \'{e} circuito direcionado
       simples, e n\~{a}o \'{e} ciclo direcionado.)

 \item {\bf Circuito direcionado Hamiltoniano:} circuito direcionado simples
       gerador.
\end{itemize}

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

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

\begin{description}
 \item[Proposi\c{c}\~{a}o:] \
 
       Qualquer grafo direcionado completo sem grupos sumidouros tem circuito
       direcionado Hamiltoniano. (Portanto, qualquer grafo direcionado completo
       com pelo menos 3 v\'{e}rtices, e sem grupos sumidouros, \'{e} Hamiltoniano.)
       
 \item[Prova:] \
 
       Indu\c{c}\~{a}o sobre n\'{u}mero de v\'{e}rtices.
\end{description}

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

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

\noindent \underline{Exemplo de constru\c{c}\~{a}o de circuito direcionado Hamiltoniano}:

\vspace*{5mm}
\noindent Seja o grafo (sem grupo sumidouro):
\begin{center}
\begin{picture}(80,80)
 \put(20,20){\circle*{5}}
 \put(10,10){\makebox(0,0){d}}
 \put(20,20){\line(0,1){40}}
 \put(20,20){\vector(0,1){20}}
 \put(20,20){\line(1,0){40}}
 \put(20,20){\vector(1,0){20}}
 \put(20,60){\circle*{5}}
 \put(10,70){\makebox(0,0){a}}
 \put(20,60){\line(1,0){40}}
 \put(20,60){\vector(1,0){20}}
 \put(60,60){\circle*{5}}
 \put(70,70){\makebox(0,0){b}}
 \put(60,60){\line(0,-1){40}}
 \put(60,60){\vector(0,-1){20}}
 \put(60,60){\line(-1,-1){40}}
 \put(60,60){\vector(-1,-1){30}}
 \put(60,20){\circle*{5}}
 \put(70,10){\makebox(0,0){c}}
 \put(60,20){\line(-1,1){40}}
 \put(60,20){\vector(-1,1){30}}
\end{picture}
\end{center}

\begin{enumerate}
 \item Escolhendo um v\'{e}rtice (ele \'{e} um circuito direcionado simples):
       \begin{center}
       \begin{picture}(30,30)
        \put(20,20){\circle*{5}}
        \put(10,10){\makebox(0,0){d}}
       \end{picture}
       \end{center}
       
%--------------------------------------------------------------------------------------------

\newslide{CAMINHAMENTOS (8)}
\hypertarget{caminhamentos-8}{}          
       
 \item (Caso 2) Particionando os v\'{e}rtices restantes: uns ``entrando'' no ciclo,
       outros ``saindo'':
       \begin{center}
       \begin{picture}(80,120)
        \put(20,20){\circle*{5}}
        \put(10,10){\makebox(0,0){a}}
        \put(60,20){\circle*{5}}
        \put(70,10){\makebox(0,0){c}}
        \put(40,60){\circle*{5}}
        \put(50,60){\makebox(0,0){d}}
        \put(40,60){\line(-1,-2){20}}
        \put(40,60){\vector(-1,-2){10}}
        \put(40,60){\line(1,-2){20}}
        \put(40,60){\vector(1,-2){10}}
        \put(40,100){\circle*{5}}
        \put(40,110){\makebox(0,0){b}}
        \put(40,100){\line(0,-1){40}}
        \put(40,100){\vector(0,-1){20}}
       \end{picture}
       \end{center}
       Como $\{a,c\}$ n\~{a}o \'{e} grupo sumidouro, h\'{a} aresta $(a,b)$ ou $(c,b)$. No
       caso, $(a,b)$, o que d\'{a} o ciclo:      
       \begin{center}
       \begin{picture}(80,120)
        \put(20,20){\circle*{5}}
        \put(10,10){\makebox(0,0){a}}
        \put(20,20){\line(1,4){20}}
        \put(20,20){\vector(1,4){10}}
        \put(40,60){\circle*{5}}
        \put(50,60){\makebox(0,0){d}}
        \put(40,60){\line(-1,-2){20}}
        \put(40,60){\vector(-1,-2){10}}
        \put(40,100){\circle*{5}}
        \put(40,110){\makebox(0,0){b}}
        \put(40,100){\line(0,-1){40}}
        \put(40,100){\vector(0,-1){20}}
       \end{picture}
       \end{center}   
       
%--------------------------------------------------------------------------------------------

\newslide{CAMINHAMENTOS (9)}
\hypertarget{caminhamentos-9}{}                
       
 \item (Caso 1) Inclus\~{a}o simples de v\'{e}rtice fora do ciclo; no caso, $c$, pois
       existem as arestas $(d,c)$, $(c,a)$ e $(d,a)$:
       \begin{center}
       \begin{picture}(80,120)
        \put(20,20){\circle*{5}}
        \put(10,10){\makebox(0,0){a}}
        \put(20,20){\line(1,4){20}}
        \put(20,20){\vector(1,4){10}}
        \put(40,60){\circle*{5}}
        \put(50,60){\makebox(0,0){d}}
        \put(40,60){\line(1,-2){20}}
        \put(40,60){\vector(1,-2){10}}
        \put(40,100){\circle*{5}}
        \put(40,110){\makebox(0,0){b}}
        \put(40,100){\line(0,-1){40}}
        \put(40,100){\vector(0,-1){20}}
        \put(60,20){\circle*{5}}
        \put(70,10){\makebox(0,0){c}}
        \put(60,20){\line(-1,0){40}}
        \put(60,20){\vector(-1,0){20}}
       \end{picture}
       \end{center}
\end{enumerate}

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

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

\noindent \underline{Outro exemplo}:

\begin{center}
\begin{picture}(120,140)
 \put(60,100){\circle*{5}}
 \put(60,110){\makebox(0,0){a}}
 \put(60,100){\line(-1,-4){20}}
 \put(60,100){\vector(-1,-4){10}}
 \put(60,100){\line(1,-4){20}}
 \put(60,100){\vector(1,-4){10}}
 
 \put(100,60){\circle*{5}}
 \put(110,60){\makebox(0,0){b}}
 \put(100,60){\line(-1,1){40}}
 \put(100,60){\vector(-1,1){20}}
 \put(100,60){\line(-1,0){80}}
 \put(100,60){\vector(-1,0){40}}
 \put(100,60){\line(-3,-2){60}}
 \put(100,60){\vector(-3,-2){30}}
 
 \put(80,20){\circle*{5}}
 \put(90,10){\makebox(0,0){c}}
 \put(80,20){\line(1,2){20}}
 \put(80,20){\vector(1,2){10}}
 
 \put(40,20){\circle*{5}}
 \put(30,10){\makebox(0,0){d}}
 \put(40,20){\line(1,0){40}}
 \put(40,20){\vector(1,0){20}}
 \put(40,20){\line(-1,2){20}}
 \put(40,20){\vector(-1,2){10}}
 
 \put(20,60){\circle*{5}}
 \put(10,60){\makebox(0,0){e}}
 \put(20,60){\line(1,1){40}}
 \put(20,60){\vector(1,1){20}}
\end{picture}
\end{center}

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

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

\begin{description}
 \item[Proposi\c{c}\~{a}o:] \
 
       Seja $G$ um grafo direcionado com $n$ v\'{e}rtices. Se $G$ \'{e} completo e se
       $\mbox{\it gsai\/}(u)+\mbox{\it gent\/}(v)\geq n-1$, para todo par de
       v\'{e}rtices distintos $u$ e $v$, ent\~{a}o $G$ tem circuito direcionado
       Hamiltoniano.
       
 \item[Prova:] \
 
       Basta mostrar que $G$ n\~{a}o tem grupos sumidouros. Suponha que $G$ tem um
       grupo sumidouro {\bf V'} de $k$ v\'{e}rtices. Sejam $u\in \mbox{\bf V'}$ e
       $v\in \mbox{\bf V}-\mbox{\bf V'}$. Ent\~{a}o, $\mbox{\it gsai\/}(u)\leq k-1$
       e $\mbox{\it gent\/}(v)\leq n-k-1$ e, portanto,
       $\mbox{\it gsai\/}(u)+\mbox{\it gent\/}(v)\leq n-2$.
\end{description}

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

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

\noindent A seguinte proposi\c{c}\~{a}o implica as 3 anteriores:

\begin{description}
 \item[Proposi\c{c}\~{a}o:] \
 
       Seja $G$ um grafo direcionado fortemente conexo com $n>1$ v\'{e}rtices. Se
       $\mbox{\it grau\/}(u)+\mbox{\it grau\/}(v)\geq 2n-1$, para todo par de
       v\'{e}rtices distintos n\~{a}o adjacentes $u$ e $v$, ent\~{a}o $G$ \'{e} Hamiltoniano.
       
\end{description}

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

\newslide{DUAS APLICAÇÕES (1)}
\hypertarget{duas-aplicacoes-1}{}

\begin{itemize}
 \item \underline{O paradoxo do jornalista esportivo}:
 
       Um jornalista esportivo ``prova'' que um time $A$, que est\'{a} em primeiro
       lugar no campeonato, \'{e} pior do que um time $Z$, que est\'{a} muito mal
       colocado, da seguinte maneira: $Z$ venceu $C$, $C$ venceu $F$, $F$
       venceu $G$, e $G$ venceu $A$. Supondo que n\~{a}o h\'{a} empates, como modelar
       tal situa\c{c}\~{a}o por meio de grafos? Em particular, em que situa\c{c}\~{o}es
       \underline{sempre} existe uma ``prova'' do tipo acima? 

       \vspace*{10mm}

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

\newslide{DUAS APLICAÇÕES (2)}
\hypertarget{duas-aplicacoes-2}{}

\item \underline{O problema das ruas de m\~{a}o \'{u}nica}:
 
       Uma cidade necessita impor o m\'{a}ximo poss\'{\i}vel de m\~{a}os \'{u}nicas em suas ruas.
       Como modelar este problema por meio de grafos?
 
\end{itemize}

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

\defskiptarget{capitulo8}

\lastpage 

\end{document}