\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{blue}
\setslidetitlecolor{red}
\setbordercolor{darkblue}

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

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

\title{Introdução à Teoria dos Grafos \\ Baseado em Townsend (1987), Cap. 6}
\author{Newton José Vieira}
\lhead{Matemática Discreta}
\rhead{Capítulo 6}
\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{introducao-1}{Introdução à Teoria dos Grafos}
\item \hyperlink{lema-aperto-maos-1}{O Lema do Aperto de Mãos}
\item \hyperlink{isomorfismo-1}{Isomorfismo}
\item \hyperlink{planaridade-1}{Planaridade}
\end{itemize}
%\centralbar{13cm}
%\begin{itemize}
%\item \hyperlink{comandos}{Comandos Especiais}
%\end{itemize}
%\end{twoblocks}

\pagenumbering{arabic}

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

\section{INTRODUÇÃO À TEORIA DOS GRAFOS}
\hypertarget{introducao-1}{}
\setskiplink{capitulo6}

\newslide{Um exemplo}

\begin{list}{(\arabic{conta})}{\usecounter{conta}}
 \item Um engenheiro eletricista necessita construir um chip no qual 3
       jun\c{c}\~{o}es devem ser ligadas a 3 outras. Pergunta: isto pode ser feito sem
       que as liga\c{c}\~{o}es se cruzem?
       
       \vspace*{1cm}
       \begin{center}
       \begin{picture}(370,110)
        \put(10,20){\circle*{5}}
        \put(10,80){\circle*{5}}
        \put(10,20){\line(0,1){60}}
        
        \put(70,20){\circle*{5}}
        \put(70,80){\circle*{5}}
        \put(70,20){\line(0,1){60}}
        
        \put(130,20){\circle*{5}}
        \put(130,80){\circle*{5}}
        \put(130,20){\line(0,1){60}}

        \put(10,20){\line(1,1){60}}
        \put(70,20){\line(1,1){60}}
        
        \put(10,80){\line(1,-1){60}}
        \put(70,80){\line(1,-1){60}}
        
        \put(10,20){\line(2,1){120}}
        \put(10,80){\line(2,-1){120}}
        
        \put(150,40){\line(1,0){60}}
        \put(150,60){\line(1,0){60}}
        \put(220,50){\line(-1,1){20}}
        \put(220,50){\line(-1,-1){20}}
        \put(185,50){\makebox(0,0){grafo}}
        
        \put(240,20){\circle*{5}}
        \put(240,10){\makebox(0,0){$y_1$}}
        \put(240,80){\circle*{5}}
        \put(240,90){\makebox(0,0){$x_1$}}
        \put(240,20){\line(0,1){60}}
        
        \put(300,20){\circle*{5}}
        \put(300,10){\makebox(0,0){$y_2$}}
        \put(300,80){\circle*{5}}
        \put(300,90){\makebox(0,0){$x_2$}}
        \put(300,20){\line(0,1){60}}
        
        \put(360,20){\circle*{5}}
        \put(360,10){\makebox(0,0){$y_3$}}
        \put(360,80){\circle*{5}}
        \put(360,90){\makebox(0,0){$x_3$}}
        \put(360,20){\line(0,1){60}}

        \put(240,20){\line(1,1){60}}
        \put(300,20){\line(1,1){60}}
        
        \put(240,80){\line(1,-1){60}}
        \put(300,80){\line(1,-1){60}}
        
        \put(240,20){\line(2,1){120}}
        \put(240,80){\line(2,-1){120}}
       \end{picture}
       \end{center}

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

\newslide{Mais um exemplo}

 \item \textcolor{red}{O problema das Sete Pontes de K\"onigsberg:} \\Na cidade de Caliningrado existiam 7 pontes sobre o
       rio Preg\'olia. Tais pontes ligavam 2 ilhas uma com a outra e com as margens do rio, conforme mostrado na figura
			 abaixo. Pergunta: \'{e} poss\'{\i}vel percorrer a cidade, come\c{c}ando e terminando no mesmo lugar, e cruzando
			 cada ponte exatamente uma vez?
          
       \vspace*{1cm}
   
       \begin{center}
       \begin{picture}(370,110)
        \put(0,75){\line(1,0){40}}
        \put(45,75){\line(1,0){60}}
        \put(40,77){\line(0,-1){14}}
        \put(43,48){\circle{16}}
        \put(43,48){\makebox(0,0){b}}
        \put(45,77){\line(0,-1){14}}

        \put(10,65){\line(1,0){30}}
        \put(45,65){\line(1,0){30}}
        \put(75,65){\line(0,-1){15}}
        \put(73,50){\line(1,0){14}}
        \put(73,45){\line(1,0){14}}
        \put(75,45){\line(0,-1){15}}
        
        \put(10,65){\line(0,-1){35}}
        
        \put(80,10){\circle{16}}
        \put(80,10){\makebox(0,0){a}}
        \put(80,85){\circle{16}}
        \put(80,85){\makebox(0,0){c}}

        \put(10,30){\line(1,0){30}}
        \put(45,30){\line(1,0){30}}
        
        \put(0,20){\line(1,0){40}}
        \put(45,20){\line(1,0){60}}
        \put(40,18){\line(0,1){14}}
        \put(45,18){\line(0,1){14}}

        \put(85,65){\line(0,-1){15}}
        \put(85,45){\line(0,-1){15}}
        \put(85,65){\line(1,0){20}}
        \put(105,77){\line(0,-1){14}}
        \put(110,77){\line(0,-1){14}}
        \put(85,30){\line(1,0){20}}
        \put(105,32){\line(0,-1){14}}
        \put(110,32){\line(0,-1){14}}
        \put(110,75){\line(1,0){20}}
        \put(110,65){\line(1,0){20}}
        \put(130,77){\line(0,-1){14}}
        \put(135,77){\line(0,-1){14}}
        \put(135,75){\line(1,0){30}}
        \put(110,20){\line(1,0){20}}
        \put(110,30){\line(1,0){20}}
        \put(130,32){\line(0,-1){14}}
        \put(135,32){\line(0,-1){14}}
        \put(135,20){\line(1,0){30}}
        
        \put(135,30){\line(1,0){20}}
        \put(135,65){\line(1,0){20}}
        \put(155,65){\line(0,-1){35}}

        \put(120,48){\circle{16}}
        \put(120,48){\makebox(0,0){d}}

        \put(170,40){\line(1,0){60}}
        \put(170,60){\line(1,0){60}}
        \put(240,50){\line(-1,1){20}}
        \put(240,50){\line(-1,-1){20}}
        \put(205,50){\makebox(0,0){grafo}}

        \put(250,50){\makebox(0,0){b}}
        \put(340,0){\makebox(0,0){a}}
        \put(340,100){\makebox(0,0){c}}
        \put(355,50){\makebox(0,0){d}}
        \put(260,50){\circle*{5}}
        \put(340,50){\circle*{5}}
        \put(340,90){\circle*{5}}
        \put(340,10){\circle*{5}}
        \put(340,70){\oval(10,40)}
        \put(340,30){\oval(10,40)}
        \put(260,50){\line(1,0){80}}
        \put(260,50){\line(2,1){80}}
        \put(260,50){\line(2,-1){80}}
       \end{picture}
       \end{center}

Euler (1736): origem da \textcolor{red}{teoria dos grafos}.
%--------------------------------------------------------------------------------------------

\newslide{Mais um exemplo}

 \item O Sindicato dos Pescadores monitora popula\c{c}\~{o}es de peixes no Golfo do
       M\'{e}xico. Todo dia s\~{a}o escolhidos alguns pontos do golfo e enviadas
       algumas pessoas de barco para colher amostras de peixes e de correntes.
       Pergunta: qual \'{e} a menor rota que o barco pode tomar, de forma que passe
       por todos os pontos?
      
       \vspace*{1cm}

       \begin{center}
       \begin{picture}(370,100)
        \put(20,80){\circle*{5}}
        \put(10,90){\makebox(0,0){e}}
        \put(120,80){\circle*{5}}
        \put(120,90){\makebox(0,0){a}}
        \put(70,60){\circle*{5}}
        \put(70,70){\makebox(0,0){b}}
        \put(50,30){\circle*{5}}
        \put(40,40){\makebox(0,0){d}}
        \put(100,10){\circle*{5}}
        \put(110,10){\makebox(0,0){c}}

        \put(150,40){\line(1,0){60}}
        \put(150,60){\line(1,0){60}}
        \put(220,50){\line(-1,1){20}}
        \put(220,50){\line(-1,-1){20}}
        \put(185,50){\makebox(0,0){grafo}}

        \put(300,80){\circle*{5}}
        \put(300,90){\makebox(0,0){a}}
        \put(270,50){\circle*{5}}
        \put(270,50){\line(1,1){30}}
        \put(275,65){\makebox(0,0){\footnotesize 400}}
        \put(260,50){\makebox(0,0){e}}
        \put(330,50){\circle*{5}}
        \put(330,50){\line(-1,1){30}}
        \put(325,65){\makebox(0,0){\footnotesize 350}}
        \put(340,50){\makebox(0,0){b}}
        \put(270,50){\line(1,0){60}}
        \put(300,55){\makebox(0,0){\footnotesize 100}}
        
        \put(270,20){\circle*{5}}
        \put(270,10){\makebox(0,0){d}}
        \put(270,20){\line(0,1){30}}
        \put(260,35){\makebox(0,0){\footnotesize 100}}
        \put(270,20){\line(2,1){60}}
        \put(320,38){\makebox(0,0){\footnotesize 170}}
        \put(270,20){\line(1,0){60}}
        \put(300,15){\makebox(0,0){\footnotesize 100}}

        \put(330,20){\circle*{5}}
        \put(330,10){\makebox(0,0){c}}
        \put(330,20){\line(0,1){30}}
        \put(340,35){\makebox(0,0){\footnotesize 100}}
        \put(330,20){\line(-2,1){60}}
        \put(280,38){\makebox(0,0){\footnotesize 170}}
        
        \put(300,50){\oval(120,60)}
        \put(230,70){\makebox(0,0){\footnotesize 450}}
        \put(370,70){\makebox(0,0){\footnotesize 400}}
       \end{picture}
       \end{center}
\end{list}

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

\newslide{Grafo não direcionado}

\noindent Um \textcolor{black}{grafo n\~{a}o direcionado} \'{e} uma estrutura
$(V, E)$, em que:

\begin{itemize}
 \item $V$: conjunto finito de \textcolor{black}{v\'{e}rtices};
 \item $E$: multi-conjunto finito de \textcolor{black}{arestas}, sendo cada aresta um
       multiconjunto de 2 v\'{e}rtices de $V$.
\end{itemize}

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

\newslide{Terminologia}

\begin{itemize}
 \item \textcolor{black}{la\c{c}o}: aresta da forma $\{v,v\}$.
 \item \textcolor{black}{v\'{e}rtices adjacentes}: v\'{e}rtices de uma mesma aresta.
 \item \textcolor{black}{aresta incidente} ao v\'{e}rtice $v$: aresta que cont\'{e}m $v$.
 \item \textcolor{black}{extremidade} de uma aresta: v\'{e}rtice da aresta.
 \item \textcolor{black}{grafo nulo}: aquele para o qual $\mbox{\bf V}=\emptyset$.
\end{itemize}

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

\newslide{Representa\c{c}\~{a}o geom\'{e}trica de um grafo}

\begin{itemize}
 \item v\'{e}rtice: representado por um c\'{\i}rculo (ou ponto).
 \item aresta: representada por uma linha ligando os c\'{\i}rculos representativos
       dos v\'{e}rtices.
\end{itemize}

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

\begin{itemize}
 \item $G= (\mbox{\bf V}, \mbox{\bf E})$, onde:
       \begin{itemize}
        \item $\mbox{\bf V}= \{a,b,c\}$
        \item $\mbox{\bf E}= \{\{a,a\},\{a,b\},\{a,b\},\{a,c\},\{b,c\}\}$
       \end{itemize}
 \item Uma representa\c{c}\~{a}o geom\'{e}trica:
 
       \begin{center}
       \begin{picture}(95,90)
        \put(20,70){\circle*{5}}
        \put(20,80){\makebox(0,0){b}}
        \put(20,30){\circle*{5}}
        \put(5,30){\makebox(0,0){a}}
        \put(20,50){\oval(20,40)}
        \put(20,20){\oval(20,20)}
        \put(80,50){\circle*{5}}
        \put(80,50){\line(-3,1){60}}
        \put(90,50){\makebox(0,0){c}}
        \put(80,50){\line(-3,-1){60}}
       \end{picture}
       \end{center}
\end{itemize}

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

\newslide{Alguns tipos de grafos}

\noindent Um \textcolor{black}{grafo simples} \'{e} um grafo sem la\c{c}os e sem arestas m\'{u}ltiplas.

\vspace*{8mm}
\noindent Um \textcolor{black}{grafo direcionado} \'{e} um grafo cujas arestas s\~{a}o direcionadas
(ou seja, {\bf E} \'{e} um multi-conjunto de pares ordenados).

\vspace*{8mm}
\noindent Um \textcolor{black}{grafo valorado} \'{e} um grafo em que cada aresta tem um valor
associado.

\vspace*{8mm}
\noindent Um grafo \'{e} \textcolor{black}{imers\'{\i}vel} em uma superf\'{\i}cie $S$, se puder ser
       representado geometricamente em $S$ de forma que arestas se cruzem
       apenas nas extremidades.

\vspace*{8mm}
\noindent Um \textcolor{black}{grafo planar} \'{e} um grafo que \'{e} imers\'{\i}vel no plano.

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

\newslide{Defini\c{c}\~{o}es relativas a ``caminhamentos''}

\vspace*{5mm}
\begin{itemize}
 \item \textcolor{black}{Caminho} (\textcolor{orange}{walk}): sequ\^{e}ncia de v\'{e}rtices e arestas ($n\geq 1$)
     \[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\mbox{.}\]
       (No caso de arestas m\'{u}ltiplas, deve-se indicar qual delas est\'{a} sendo
       usada.)
       \begin{itemize}       
        \item Nota\c{c}\~{a}o abreviada: $x_1 x_2 x_3\ldots x_{n-1} x_n$.
        \item $x_1$ e $x_n$: \textcolor{black}{extremidades} do caminho.
        \item \textcolor{black}{Comprimento} do caminho: n\'{u}mero de arestas do mesmo (isto \'{e},
              $n-1$).
       \end{itemize}
 \item \textcolor{black}{Caminho fechado}: caminho em que $x_1=x_n$.
 \item \textcolor{black}{Caminho gerador} (\textcolor{orange}{spanning}): caminho que cont\'{e}m todos os
       v\'{e}rtices do grafo.
       
%--------------------------------------------------------------------------------------------

\newslide{Defini\c{c}\~{o}es relativas a ``caminhamentos''}
       
 \item \textcolor{black}{Caminho simples} (\textcolor{orange}{path}): caminho sem v\'{e}rtices repetidos.
 \item \textcolor{black}{Trajeto} (\textcolor{orange}{trail}): caminho sem arestas repetidas.
 \item \textcolor{black}{Circuito}: trajeto fechado.
 \item \textcolor{black}{Ciclo}: circuito com pelo menos uma aresta, no qual o \'{u}nico v\'{e}rtice
       repetido \'{e} $x_1=x_n$.
       \begin{itemize}       
        \item $n$-ciclo: ciclo de tamanho $n$.
        \item $1$-ciclo: la\c{c}o.
        \item $2$-ciclo: par de arestas m\'{u}ltiplas.
        \item $3$-ciclo: chamado \textcolor{black}{tri\^{a}ngulo}.
        \item $4$-ciclo: chamado \textcolor{black}{quadril\'{a}tero}, e assim por diante...
       \end{itemize}
\end{itemize}

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

\newslide{Um exemplo}

\begin{center}
\begin{picture}(200,160)
 \put(20,140){\circle*{5}}
 \put(10,150){\makebox(0,0){f}}
 \put(20,140){\line(1,0){80}}
 \put(100,140){\circle*{5}}
 \put(110,150){\makebox(0,0){g}}
 \put(20,80){\line(0,1){60}}
 \put(100,80){\line(0,1){60}}
 \put(20,80){\circle*{5}}
 \put(10,70){\makebox(0,0){e}}
 \put(20,80){\line(1,0){80}}
 \put(100,80){\circle*{5}}
 \put(110,90){\makebox(0,0){a}}
 
 \put(100,80){\line(1,0){80}}
 \put(180,80){\circle*{5}}
 \put(190,90){\makebox(0,0){b}}
 \put(100,20){\line(0,1){60}}
 \put(180,20){\line(0,1){60}}
 \put(100,20){\circle*{5}}
 \put(90,10){\makebox(0,0){d}}
 \put(100,20){\line(1,0){80}}
 \put(180,20){\circle*{5}}
 \put(190,10){\makebox(0,0){c}}
\end{picture}
\end{center}

\begin{itemize}
 \item $a\{a,b\}b\{b,c\}c\{c,d\}d$: caminho de tamanho 3; abr.:
       $a b c d$.
 \item $a b c b$: caminho que n\~{a}o \'{e} simples, nem \'{e} trajeto.
 \item $a b c d a e$: trajeto que n\~{a}o \'{e} caminho simples.
 \item $a b c$: caminho simples.
 \item $a b a$: caminho fechado que n\~{a}o \'{e} circuito.
 \item $a b c d a e f g a$: circuito que n\~{a}o \'{e} ciclo.
 \item $a b c d a$: 4-ciclo (quadril\'{a}tero).
\end{itemize}

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

\newslide{Grafos Eulerianos e Hamiltonianos}

\noindent Um \textcolor{black}{circuito Euleriano} \'{e} um circuito que inclui cada aresta
exatamente uma vez.

\vspace*{10mm}
\noindent Um \textcolor{black}{grafo Euleriano} \'{e} um grafo que cont\'{e}m um circuito Euleriano.

\vspace*{10mm}
\noindent Um \textcolor{black}{ciclo Hamiltoniano} \'{e} um ciclo gerador.

\vspace*{10mm}
\noindent Um \textcolor{black}{grafo Hamiltoniano} \'{e} um grafo que cont\'{e}m um ciclo
Hamiltoniano.

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

\newslide{Exemplos}

Os conceitos de \textcolor{black}{grafo Euleriano} e \textcolor{black}{grafo Hamiltoniano} s\~ao independentes:

\vspace*{5mm}
\begin{center}
\begin{picture}(300,185) \normalsize
 \put(20,165){\circle*{5}}
 \put(15,170){\makebox(0,0){a}}
 \put(20,165){\line(1,0){60}}
 \put(80,165){\circle*{5}}
 \put(86,171){\makebox(0,0){b}}
 \put(20,125){\circle*{5}}
 \put(14,120){\makebox(0,0){d}}
 \put(20,125){\line(1,0){60}}
 \put(80,125){\circle*{5}}
 \put(85,120){\makebox(0,0){c}}
 \put(20,125){\line(0,1){40}}
 \put(80,125){\line(0,1){40}}
 
 \put(50,100){\makebox(0,0){Euleriano, Hamiltoniano}}
 
 \put(220,165){\circle*{5}}
 \put(215,170){\makebox(0,0){a}}
 \put(220,165){\line(1,0){60}}
 \put(280,165){\circle*{5}}
 \put(286,171){\makebox(0,0){b}}
 \put(220,125){\circle*{5}}
 \put(214,120){\makebox(0,0){d}}
 \put(220,125){\line(1,0){60}}
 \put(280,125){\circle*{5}}
 \put(285,120){\makebox(0,0){c}}
 \put(220,125){\line(0,1){40}}
 \put(280,125){\line(0,1){40}}
 \put(280,125){\line(-3,2){60}}
 
 \put(250,100){\makebox(0,0){n\~{a}o Euleriano, Hamiltoniano}}
 
 \put(20,65){\circle*{5}}
 \put(15,70){\makebox(0,0){a}}
 \put(80,65){\circle*{5}}
 \put(85,70){\makebox(0,0){c}}
 \put(20,25){\circle*{5}}
 \put(15,20){\makebox(0,0){e}}
 \put(80,25){\circle*{5}}
 \put(85,20){\makebox(0,0){d}}
 \put(20,25){\line(0,1){40}}
 \put(80,25){\line(0,1){40}}
 \put(20,25){\line(3,2){60}}
 \put(80,25){\line(-3,2){60}}
 \put(50,45){\circle*{5}}
 \put(50,54){\makebox(0,0){b}}
 
 \put(50,0){\makebox(0,0){Euleriano, n\~{a}o Hamiltoniano}}
 
 \put(250,65){\circle*{5}}
 \put(250,72){\makebox(0,0){a}}
 \put(250,25){\line(0,1){40}}
 \put(250,25){\circle*{5}}
 \put(250,18){\makebox(0,0){b}}
 
 \put(250,0){\makebox(0,0){n\~{a}o Euleriano, n\~{a}o Hamiltoniano}}
\end{picture}
\end{center}

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

\newslide{Tipos de grafos importantes}

\noindent \textcolor{black}{Grafo completo} com $n$ v\'{e}rtices (\textcolor{black}{$K_n$}): grafo simples em que
cada v\'{e}rtice \'{e} adjacente a todos os outros. Tem, portanto, $C(n,2)$ arestas.

\vspace*{10mm}
\noindent \textcolor{black}{Grafo bipartido}: grafo cujos v\'{e}rtices podem ser particionados em
dois conjuntos, de forma que as extremidades de qualquer aresta n\~{a}o estejam no
mesmo conjunto.

\vspace*{10mm}
\noindent \textcolor{black}{Grafo bipartido completo}(\textcolor{black}{$K_{m,n}$}): grafo bipartido em que cada
v\'{e}rtice de um dos conjuntos \'{e} adjacente a todo v\'{e}rtice do outro conjunto. Tem, portanto, $m\times n$ arestas.

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

\newslide{Exemplos}

\begin{center}
\begin{picture}(360,200)
 \put(20,180){\circle*{5}}
 \put(10,190){\makebox(0,0){a}}
 \put(20,180){\line(1,-2){20}}
 \put(60,180){\circle*{5}}
 \put(60,190){\makebox(0,0){b}}
 \put(60,180){\line(1,-2){20}}
 \put(40,140){\circle*{5}}
 \put(40,130){\makebox(0,0){d}}
 \put(40,140){\line(1,2){20}}
 \put(80,140){\circle*{5}}
 \put(90,130){\makebox(0,0){c}}
 
 \put(50,110){\makebox(0,0){\normalsize bipartido, n\~{a}o completo}}
 
 \put(180,180){\circle*{5}}
 \put(190,180){\makebox(0,0){e}}
 \put(180,140){\circle*{5}}
 \put(190,140){\makebox(0,0){f}}
 
 \put(180,110){\makebox(0,0){\normalsize bipartido, n\~{a}o completo}}
 
 \put(320,180){\circle*{5}}
 \put(320,180){\line(-1,-2){20}}
 \put(320,180){\line(1,-2){20}}
 \put(320,190){\makebox(0,0){g}}
 \put(300,140){\circle*{5}}
 \put(300,140){\line(1,0){40}}
 \put(290,130){\makebox(0,0){i}}
 \put(340,140){\circle*{5}}
 \put(350,130){\makebox(0,0){h}}
 
 \put(320,110){\makebox(0,0){\normalsize n\~{a}o bipartido, completo}}
 
 \put(90,80){\circle*{5}}
 \put(90,90){\makebox(0,0){$x_1$}}
 \put(90,80){\line(-1,-1){40}}
 \put(90,80){\line(1,-1){40}}
 \put(90,80){\line(0,-1){40}}
 \put(50,40){\circle*{5}}
 \put(40,30){\makebox(0,0){$y_1$}}
 \put(90,40){\circle*{5}}
 \put(90,30){\makebox(0,0){$y_2$}}
 \put(130,40){\circle*{5}}
 \put(140,30){\makebox(0,0){$y_3$}}
 
 \put(90,10){\makebox(0,0){\normalsize $K_{1,3}$}}
 
 \put(240,80){\circle*{5}} 
 \put(230,90){\makebox(0,0){$x_1$}}
 \put(240,80){\line(1,0){60}}
 \put(300,80){\circle*{5}} 
 \put(310,90){\makebox(0,0){$x_2$}}
 \put(240,40){\line(0,1){40}}
 \put(300,40){\line(0,1){40}}
 \put(240,40){\line(3,2){60}}
 \put(300,40){\line(-3,2){60}}
 \put(240,40){\circle*{5}} 
 \put(230,30){\makebox(0,0){$x_4$}}
 \put(240,40){\line(1,0){60}}
 \put(300,40){\circle*{5}} 
 \put(310,30){\makebox(0,0){$x_3$}}
 
 \put(270,10){\makebox(0,0){\normalsize $K_4$}}
\end{picture}
\end{center}

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

\newslide{Reformula\c{c}\~{a}o dos 3 problemas}

\vspace*{10mm}
\begin{itemize}
 \item $K_{3,3}$ \'{e} planar?

\vspace*{10mm}
 \item O grafo das pontes de K\"onigsberg \'{e} Euleriano?

\vspace*{10mm}
 \item Para o grafo valorado completo representando os pontos do golfo do
       M\'{e}xico, qual \'{e} o ciclo Hamiltoniano de menor tamanho?
\end{itemize}

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

\newslide{Mais algumas defini\c{c}\~{o}es}

\vspace*{5mm}
\begin{itemize}
 \item $G$ \'{e} \textcolor{black}{subgrafo} de $H$, $G\subseteq H$, se todos os v\'{e}rtices e
       arestas de $G$ s\~{a}o v\'{e}rtices e arestas de $H$.
 \item Um subgrafo \textcolor{black}{gerador} (\textcolor{orange}{spanning}) \'{e} um subgrafo que cont\'{e}m
       todos os vértices do grafo.
\end{itemize}

\noindent \underline{Exemplos}:

\begin{center}
\begin{picture}(380,90)
 \put(20,70){\circle*{5}}
 \put(20,70){\line(1,0){30}}
 \put(10,80){\makebox(0,0){a}}
 \put(50,70){\circle*{5}}
 \put(50,70){\line(0,-1){30}}
 \put(60,80){\makebox(0,0){b}}
 \put(20,40){\circle*{5}}
 \put(20,40){\line(1,0){30}}
 \put(10,30){\makebox(0,0){d}}
 \put(50,40){\circle*{5}}
 \put(20,40){\line(0,1){30}}
 \put(60,30){\makebox(0,0){c}}
 
 \put(35,10){\makebox(0,0){$G$}}
 
 \put(140,70){\circle*{5}}
 \put(140,70){\line(0,-1){30}}
 \put(140,80){\makebox(0,0){a}}
 \put(140,40){\circle*{5}}
 \put(140,30){\makebox(0,0){d}}
 
 \put(140,10){\makebox(0,0){$H$}}
 
 \put(235,70){\circle*{5}}
 \put(235,70){\line(-1,-2){15}}
 \put(235,70){\line(1,-2){15}}
 \put(235,80){\makebox(0,0){a}}
 \put(220,40){\circle*{5}}
 \put(210,30){\makebox(0,0){d}}
 \put(250,40){\circle*{5}}
 \put(260,30){\makebox(0,0){c}}
 
 \put(235,10){\makebox(0,0){$I$}}
 
 \put(330,70){\circle*{5}}
 \put(330,70){\line(1,0){30}}
 \put(320,80){\makebox(0,0){a}}
 \put(360,70){\circle*{5}}
 \put(370,80){\makebox(0,0){b}}
 \put(330,40){\circle*{5}}
 \put(330,40){\line(1,0){30}}
 \put(320,30){\makebox(0,0){d}}
 \put(360,40){\circle*{5}}
 \put(330,40){\line(0,1){30}}
 \put(370,30){\makebox(0,0){c}}
 
 \put(295,10){\makebox(0,0){$J$}}
\end{picture}
\end{center}
\begin{itemize}
 \item $G\subseteq G$, $H\subseteq G$, $J\subseteq G$, $H\subseteq I$,
       $H\subseteq J$;
 \item $J$ \'{e} um subgrafo gerador para $G$.
\end{itemize}

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

\newslide{Grafo conectado (conexo)}

\noindent Um grafo \'{e} \textcolor{black}{conectado} se existe caminho entre quaisquer dois
v\'{e}rtices do mesmo. Caso contr\'{a}rio, \'{e} \textcolor{black}{desconectado}.

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

\begin{center}
\begin{picture}(380,90)
 \put(20,70){\circle*{5}}
 \put(20,70){\line(1,0){30}}
 \put(10,80){\makebox(0,0){a}}
 \put(50,70){\circle*{5}}
 \put(50,70){\line(0,-1){30}}
 \put(60,80){\makebox(0,0){b}}
 \put(20,40){\circle*{5}}
 \put(20,40){\line(1,0){30}}
 \put(10,30){\makebox(0,0){d}}
 \put(50,40){\circle*{5}}
 \put(20,40){\line(0,1){30}}
 \put(60,30){\makebox(0,0){c}}
 
 \put(35,10){\makebox(0,0){$G$}}
 
 \put(140,70){\circle*{5}}
 \put(140,70){\line(0,-1){30}}
 \put(140,80){\makebox(0,0){a}}
 \put(140,40){\circle*{5}}
 \put(140,30){\makebox(0,0){d}}
 
 \put(140,10){\makebox(0,0){$H$}}
 
 \put(235,70){\circle*{5}}
 \put(235,70){\line(-1,-2){15}}
 \put(235,70){\line(1,-2){15}}
 \put(235,80){\makebox(0,0){a}}
 \put(220,40){\circle*{5}}
 \put(210,30){\makebox(0,0){d}}
 \put(250,40){\circle*{5}}
 \put(260,30){\makebox(0,0){c}}
 \put(235,40){\circle*{5}}
 \put(235,30){\makebox(0,0){b}}
 
 \put(235,10){\makebox(0,0){$I$}}
 
 \put(330,70){\circle*{5}}
 \put(330,70){\line(1,0){30}}
 \put(345,55){\circle*{5}}
 \put(351,61){\makebox(0,0){e}}
 \put(320,80){\makebox(0,0){a}}
 \put(360,70){\circle*{5}}
 \put(360,70){\line(0,-1){30}}
 \put(370,80){\makebox(0,0){b}}
 \put(330,40){\circle*{5}}
 \put(330,40){\line(1,0){30}}
 \put(320,30){\makebox(0,0){d}}
 \put(360,40){\circle*{5}}
 \put(330,40){\line(0,1){30}}
 \put(370,30){\makebox(0,0){c}}
 
 \put(295,10){\makebox(0,0){$J$}}
\end{picture}
\end{center}
\begin{itemize}
 \item $G$: conectado, Euleriano, Hamiltoniano.
 \item $H$: conectado, n\~{a}o Euleriano, n\~{a}o Hamiltoniano;
 \item $I$: desconectado, n\~{a}o Euleriano, n\~{a}o Hamiltoniano;
 \item $J$: desconectado, Euleriano, n\~{a}o Hamiltoniano.
\end{itemize}

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

\newslide{Componente conectado, complemento}

\noindent Um \textcolor{black}{componente} (\textcolor{black}{conectado}) de um grafo \'{e} um subgrafo conectado
``maximal''. Ou seja, $H$ \'{e} um componente de $G$ se, e somente se,

\begin{itemize}
 \item $H$ \'{e} um subgrafo conectado de $G$; e
 \item nenhum outro subgrafo conectado de $G$ cont\'{e}m $H$.
\end{itemize}

\vspace*{10mm}
\noindent O \textcolor{black}{complemento} de um grafo simples $G=(\mbox{\bf V},\mbox{\bf E})$ \'{e} o grafo simples
\[G^{c}=(\mbox{\bf V}, \mbox{\bf E}')\mbox{,}\]
onde $\{v,w\}\in E'$ se, e somente se, $\{v,w\}\not\in E$. (Quantas arestas
tem o complemento de um grafo simples?)

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

\newslide{Um exemplo}

\begin{center}
\begin{picture}(270,90)
 \put(20,70){\circle*{5}}
 \put(20,70){\line(1,0){30}}
 \put(10,80){\makebox(0,0){a}}
 \put(50,70){\circle*{5}}
 \put(50,70){\line(0,-1){30}}
 \put(60,80){\makebox(0,0){b}}
 \put(20,40){\circle*{5}}
 \put(20,40){\line(1,0){30}}
 \put(10,30){\makebox(0,0){d}}
 \put(50,40){\circle*{5}}
 \put(20,40){\line(0,1){30}}
 \put(60,30){\makebox(0,0){c}}
 
 \put(35,10){\makebox(0,0){$G$}}
 
 \put(220,70){\circle*{5}}
 \put(210,80){\makebox(0,0){a}}
 \put(250,70){\circle*{5}}
 \put(250,70){\line(0,-1){30}}
 \put(260,80){\makebox(0,0){b}}
 \put(220,40){\circle*{5}}
 \put(210,30){\makebox(0,0){c}}
 \put(250,40){\circle*{5}}
 \put(220,40){\line(0,1){30}}
 \put(260,30){\makebox(0,0){d}}
 
 \put(235,10){\makebox(0,0){$G^c$}}
\end{picture}
\end{center}
\begin{itemize}
 \item $G$ \'{e} conectado (tem 1 componente)
 \item $G^c$ \'{e} desconectado, e tem 2 componentes.
\end{itemize}

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

\newslide{Subdivisão}


\noindent {\textcolor{black}{Subdivis\~{a}o de uma aresta} $\{v,w\}$ de $G$: substitui\c{c}\~{a}o de
$\{v,w\}$ por duas arestas $\{v,z\}$ e $\{z,w\}$, sendo $z$ um novo v\'{e}rtice adicionado a $G$.

\vspace*{10mm}
\noindent Um grafo $G_2$ \'{e} um \textcolor{black}{grafo subdivis\~{a}o} de $G_1$ quando $G_2$
\'e obtido de $G_1$ pela subdivis\~ao das arestas de $G_1$.

\vspace*{1cm}
Exemplo:
\begin{quote}
 qual é o grafo subdivis\~{a}o do grafo das pontes de K\"onigsberg? 
\end{quote}
%--------------------------------------------------------------------------------------------

\section{O LEMA DO APERTO DE MÃOS}
\hypertarget{lema-aperto-maos-1}{}

\newslide{Defini\c{c}\~{o}es preliminares}

\begin{itemize}
 \item O \textcolor{black}{grau} de um v\'{e}rtice $v$, \textcolor{black}{grau$(v)$}, \'{e} o n\'{u}mero de arestas
       incidentes a $v$, com cada la\c{c}o contado 2 vezes.
 \item V\'{e}rtice \textcolor{black}{isolado}: v\'{e}rtice de grau 0;
 \item \textcolor{black}{Extremidade} de um grafo: v\'{e}rtice de grau 1;
 \item \textcolor{black}{Grafo regular} de grau $n$: grafo cujos v\'{e}rtices têm grau $n$.
\end{itemize}

\noindent \underline{Exemplos}:

\begin{center}
\begin{picture}(110,50)
 \put(50,10){\makebox(0,0){b}}
 \put(60,20){\circle*{5}}
 \put(60,20){\line(1,0){30}}
 \put(60,20){\line(0,1){30}}
 \put(100,10){\makebox(0,0){c}}
 \put(90,20){\circle*{5}}
 \put(50,45){\makebox(0,0){a}}
 \put(60,50){\circle*{5}}
 \put(60,60){\circle{20}}
 \put(100,45){\makebox(0,0){d}}
 \put(90,50){\circle*{5}}
 \put(10,35){\makebox(0,0){$G$:}}
\end{picture}
\end{center}
\begin{itemize}
 \item Em $G$: grau$(a)=3$,  grau$(b)=2$, grau$(c)=1$ ($c$ \'{e} extremidade de $G$), grau$(d)=0$ ($d$ \'{e} isolado);
 \item $K_n$ \'e regular de grau $n-1$ e $K_{n,n}$ \'e regular de grau $n$;
 \item $K_{m,n}$ n\~{a}o \'{e} regular, se $m\not= n$.
\end{itemize}

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

\newslide{O LEMA DO APERTO DE MÃOS}
\hypertarget{lema-aperto-maos-3}{}

\noindent \begin{description}
 \item[\textcolor{black}{Lema do aperto de m\~{a}os}] \
 
       Em um grafo, a soma dos graus dos v\'{e}rtices \'{e} o dobro do n\'{u}mero de
       arestas.
       
 \item[\textcolor{black}{Prova}] \
 
       Cada aresta contribui com 2 unidades para a soma (inclusive os la\c{c}os),
       por defini\c{c}\~{a}o.
\end{description}

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

\vspace*{5mm}
\noindent Quantas arestas tem o grafo abaixo?

\begin{center}
\begin{picture}(220,100)
 \put(20,10){\makebox(0,0){h}}
 \put(20,20){\circle*{5}}
 \put(20,20){\line(0,1){60}}
 \put(20,20){\line(1,1){60}}
 \put(20,20){\line(2,1){120}}

 \put(80,10){\makebox(0,0){g}}
 \put(80,20){\circle*{5}}
 \put(80,20){\line(0,1){60}}
 \put(80,20){\line(-1,1){60}}
 \put(80,20){\line(1,1){60}}
 \put(80,20){\line(2,1){120}}
 
 \put(140,10){\makebox(0,0){f}}
 \put(140,20){\circle*{5}}
 \put(140,20){\line(0,1){60}}
 \put(140,20){\line(-2,1){120}}
 \put(140,20){\line(1,1){60}}
 
 \put(200,10){\makebox(0,0){e}}
 \put(200,20){\circle*{5}}
 \put(200,20){\line(0,1){60}}
 \put(200,20){\line(-1,1){60}}
 
 \put(20,90){\makebox(0,0){a}}
 \put(20,80){\circle*{5}}
 \put(80,90){\makebox(0,0){b}}
 \put(80,80){\circle*{5}}
 \put(140,90){\makebox(0,0){c}}
 \put(140,80){\circle*{5}}
 \put(200,90){\makebox(0,0){d}}
 \put(200,80){\circle*{5}}
\end{picture}
\end{center}

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

\newslide{Um corolário}

\noindent \begin{description}
 \item[\textcolor{black}{Corol\'{a}rio}] \
 
       Em um grafo, o n\'{u}mero de v\'{e}rtices de grau \'{\i}mpar \'{e} par.
       
 \item[\textcolor{black}{Prova}] \
 
       Uma soma de n\'{u}meros naturais \'{e} par se, e somente se, \'{e} par a quantidade
       de n\'{u}meros \'{\i}mpares. Pelo lema do aperto de m\~{a}os, a soma dos graus \'{e} par;
       logo, o n\'{u}mero de v\'{e}rtices de grau \'{\i}mpar \'{e} par.
\end{description}

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

\newslide{Outro corolário}

\noindent \begin{description}
 \item[\textcolor{black}{Corol\'{a}rio}] \
 
       Em um grupo, o n\'{u}mero de pessoas que apertaram as m\~{a}os de um n\'{u}mero \'{\i}mpar
       de pessoas do grupo \'{e} par.
       
 \item[\textcolor{black}{Prova}] \
 
       Modelagem: cada pessoa, um v\'{e}rtice; cada aperto de m\~{a}os, uma aresta
       (ligando os v\'{e}rtices correspondentes \`{a}s pessoas que apertaram as m\~{a}os).
       Com isto, o grau de um v\'{e}rtice \'{e} o n\'{u}mero de pessoas cujas m\~{a}os a pessoa
       representada pelo v\'{e}rtice apertou; e o corol\'{a}rio segue do anterior.
\end{description}

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

\newslide{Sequência de graus de um grafo}

\noindent Uma \textcolor{black}{sequ\^{e}ncia de graus} \'{e} uma sequ\^{e}ncia de n\'{u}meros naturais em
ordem decrescente.

\vspace*{5mm}
\noindent Uma sequ\^{e}ncia de graus $g_1, g_2, \ldots, g_n$ \'{e} \textcolor{black}{gr\'{a}fica} se
existe um grafo simples com $n$ v\'{e}rtices $v_1, v_2, \ldots, v_n$ tais que o
grau de $v_i$ \'{e} $g_i$.

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

\begin{itemize}
 \item $2,1,1$: sequ\^{e}ncia de graus gr\'{a}fica;
 \item $2,2,2$: sequ\^{e}ncia de graus gr\'{a}fica;
 \item $3,3,3$: sequ\^{e}ncia de graus n\~{a}o gr\'{a}fica (pelo lema do aperto de m\~{a}os);
 \item $3,3,0$: sequ\^{e}ncia de graus n\~{a}o gr\'{a}fica.
\end{itemize}

\vspace*{5mm}
\noindent A \textcolor{black}{sequ\^{e}ncia de graus de um grafo} (n\~ao necessariamente simples) $G$ \'{e} a sequ\^{e}ncia dos graus dos
v\'{e}rtices de $G$, em ordem decrescente.

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

\section{ISOMORFISMO}
\hypertarget{isomorfismo-1}{}

\noindent {\bf Isomorfismo}

\vspace*{10mm}
\noindent \textcolor{black}{As propriedades essenciais de grafos s\~{a}o \underline{estruturais}}:
\begin{quote}
 não dependem dos nomes dos vértices.
\end{quote}

\vspace*{10mm}
\noindent Dois grafos $G$ e $H$ s\~{a}o \textcolor{black}{isomorfos}, $G\cong H$, se e somente
se:
\vspace*{5mm}
\begin{itemize}
 \item existe uma correspond\^{e}ncia um-para-um entre os v\'{e}rtices de $G$ e $H$, tal
       que:

\vspace*{5mm}
 \item o n\'{u}mero de arestas entre dois v\'{e}rtices de $G$ \'{e} id\^{e}ntico ao n\'{u}mero de
       arestas entre os v\'{e}rtices correspondentes de $H$.
\end{itemize}

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

\newslide{Exemplo}

\vspace*{10mm}
\noindent Os 4 grafos simples de 3 v\'{e}rtices, n\~{a}o isomorfos:

\vspace*{20mm}
\begin{center}
\begin{picture}(390,100)
 \put(20,70){\circle*{5}}
 \put(10,80){\makebox(0,0){a}}
 \put(70,70){\circle*{5}}
 \put(80,80){\makebox(0,0){b}}
 \put(45,20){\circle*{5}}
 \put(45,10){\makebox(0,0){c}}
 
 \put(120,70){\circle*{5}}
 \put(110,80){\makebox(0,0){d}}
 \put(120,70){\line(1,0){50}}
 \put(170,70){\circle*{5}}
 \put(180,80){\makebox(0,0){e}}
 \put(145,20){\circle*{5}}
 \put(145,10){\makebox(0,0){f}}
 
 \put(220,70){\circle*{5}}
 \put(210,80){\makebox(0,0){g}}
 \put(220,70){\line(1,0){50}}
 \put(270,70){\circle*{5}}
 \put(280,80){\makebox(0,0){h}}
 \put(245,20){\circle*{5}}
 \put(245,20){\line(-1,2){25}}
 \put(245,10){\makebox(0,0){i}}
 
 \put(320,70){\circle*{5}}
 \put(310,80){\makebox(0,0){j}}
 \put(320,70){\line(1,0){50}}
 \put(370,70){\circle*{5}}
 \put(380,80){\makebox(0,0){k}}
 \put(345,20){\circle*{5}}
 \put(345,20){\line(-1,2){25}}
 \put(345,20){\line(1,2){25}}
 \put(345,10){\makebox(0,0){l}}
\end{picture}
\end{center}

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

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

\vspace*{5mm}
\begin{itemize}
 \item 2 grafos simples s\~{a}o isomorfos se, e somente se, seus complementos s\~{a}o
       isomorfos.

\vspace*{10mm}
 \item A rela\c{c}\~{a}o ``\'{e} isomorfo a'' \'{e} rela\c{c}\~{a}o de equival\^{e}ncia:
       \begin{itemize}
			  \item reflexiva
				\item sim\'etrica
				\item transitiva
			 \end{itemize}
\end{itemize}

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

\newslide{Exemplo}

\noindent $G$, $H$ e $I$ s\~{a}o isomorfos a $K_{3,3}$. Logo, eles s\~{a}o isomorfos entre si.

\vspace*{5mm}
\begin{center}
\begin{picture}(400,150)
 \put(20,50){\circle*{5}}
 \put(20,40){\makebox(0,0){$y_1$}}
 \put(20,110){\circle*{5}}
 \put(20,120){\makebox(0,0){$x_1$}}
 \put(20,50){\line(0,1){60}}
        
 \put(80,50){\circle*{5}}
 \put(80,40){\makebox(0,0){$y_2$}}
 \put(80,110){\circle*{5}}
 \put(80,120){\makebox(0,0){$x_2$}}
 \put(80,50){\line(0,1){60}}
        
 \put(140,50){\circle*{5}}
 \put(140,40){\makebox(0,0){$y_3$}}
 \put(140,110){\circle*{5}}
 \put(140,120){\makebox(0,0){$x_3$}}
 \put(140,50){\line(0,1){60}}

 \put(80,20){\makebox(0,0){$K_{3,3}$}}

 \put(20,50){\line(1,1){60}}
 \put(80,50){\line(1,1){60}}
        
 \put(20,110){\line(1,-1){60}}
 \put(80,110){\line(1,-1){60}}
        
 \put(20,50){\line(2,1){120}}
 \put(20,110){\line(2,-1){120}}
 
 \put(280,110){\circle*{5}}
 \put(270,118){\makebox(0,0){a}}
 \put(280,110){\line(1,0){60}}
 \put(340,110){\circle*{5}}
 \put(350,120){\makebox(0,0){b}}
 \put(250,80){\circle*{5}}
 \put(250,80){\line(1,1){30}}
 \put(250,80){\line(1,-1){30}}
 \put(240,80){\makebox(0,0){f}}
 \put(370,80){\circle*{5}}
 \put(370,80){\line(-1,1){30}}
 \put(370,80){\line(-1,-1){30}}
 \put(380,80){\makebox(0,0){c}}
 \put(280,50){\circle*{5}}
 \put(270,40){\makebox(0,0){e}}
 \put(280,50){\line(1,0){60}}
 \put(340,50){\circle*{5}}
 \put(350,42){\makebox(0,0){d}}
 \put(250,80){\line(1,0){120}}
 \put(280,50){\line(1,1){60}}
 \put(340,50){\line(-1,1){60}}
 
 \put(310,20){\makebox(0,0){$G$}}
\end{picture}

\begin{picture}(400,140)
 \put(20,50){\circle*{5}}
 \put(20,40){\makebox(0,0){$u$}}
 \put(20,110){\circle*{5}}
 \put(20,120){\makebox(0,0){$r$}}
 \put(20,50){\line(0,1){60}}
        
 \put(140,50){\circle*{5}}
 \put(140,40){\makebox(0,0){$t$}}
 \put(140,110){\circle*{5}}
 \put(140,120){\makebox(0,0){$s$}}
 \put(140,50){\line(0,1){60}}

 \put(20,50){\line(1,0){120}}
 \put(20,110){\line(1,0){120}}
        
 \put(60,80){\circle*{5}}
 \put(50,80){\makebox(0,0){$v$}}
 \put(100,80){\circle*{5}}
 \put(112,80){\makebox(0,0){$w$}}
 \put(60,80){\line(1,0){40}}
 \put(60,80){\line(-4,-3){40}}
 \put(100,80){\line(4,-3){40}}
 \put(100,80){\line(-2,1){40}}
 \put(60,80){\line(2,1){40}}
 \put(60,100){\line(-4,1){40}}
 \put(100,100){\line(4,1){40}}
% \put(60,80){\oval(80,30)[tr]}
% \put(60,110){\oval(80,30)[bl]}
% \put(100,80){\oval(80,30)[lt]}
% \put(100,110){\oval(80,30)[br]}

 \put(80,20){\makebox(0,0){$H$}}
 
 \put(250,50){\circle*{5}}
 \put(240,41){\makebox(0,0){3}}
 \put(370,50){\circle*{5}}
 \put(380,41){\makebox(0,0){2}}
 \put(310,50){\circle*{5}}
 \put(310,41){\makebox(0,0){6}}
 \put(310,70){\circle*{5}}
 \put(310,61){\makebox(0,0){5}}
 \put(310,90){\circle*{5}}
 \put(300,90){\makebox(0,0){4}}
 \put(310,110){\circle*{5}}
 \put(310,120){\makebox(0,0){1}}
 \put(250,50){\line(1,0){120}}
 \put(250,50){\line(3,1){60}}
 \put(250,50){\line(1,1){60}}
 \put(370,50){\line(-3,1){60}}
 \put(370,50){\line(-1,1){60}}
 \put(310,110){\line(0,-1){40}}
 \put(310,70){\oval(30,40)[r]}
 
 \put(310,20){\makebox(0,0){$I$}}
\end{picture}
\end{center}

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

\newslide{Como determinar se dois grafos s\~{a}o isomorfos?}

\vspace*{5mm}
\begin{itemize}
 \item Verificar todas as $n!$ correspond\^{e}ncias ($n$: n\'{u}mero de v\'{e}rtices):
       intrat\'{a}vel.
			
			 \begin{quote}
			  $2^n<n!<2^{n^2}$: logo, o n\'umero de correspond\^encias \'e \textcolor{black}{exponencial} com
				 rela\c c\~ao ao n\'umero de v\'ertices.
			 \end{quote}

\vspace*{10mm}
 \item N\~{a}o existe (at\'{e} o momento) t\'{e}cnica eficiente. Logo:			
			 \begin{quote}
        usar bom senso e \textcolor{black}{heur\'{\i}sticas}.
			 \end{quote}
\end{itemize}

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

\newslide{Como determinar se dois grafos s\~{a}o isomorfos?}

\noindent Para mostrar que dois grafos \textcolor{black}{n\~{a}o} s\~{a}o isomorfos:

\vspace*{5mm}
\begin{itemize}
 \item Comparar n\'{u}mero de v\'{e}rtices, n\'{u}mero de arestas, as sequ\^{e}ncias de graus
       dos grafos.
\vspace*{5mm}
 \item Comparar n\'{u}meros de componentes.
\vspace*{5mm}
 \item Verificar alguns subgrafos simples.
\vspace*{5mm}
 \item Comparar complementos.
\vspace*{5mm}
 \item Etc...
\end{itemize}

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

\newslide{Um exemplo}

\begin{center}
\begin{picture}(400,140)
 \put(20,50){\circle*{5}}
 \put(20,40){\makebox(0,0){$f$}}
 \put(20,110){\circle*{5}}
 \put(20,120){\makebox(0,0){$a$}}
 \put(20,50){\line(0,1){60}}
        
 \put(140,50){\circle*{5}}
 \put(140,40){\makebox(0,0){$d$}}
 \put(140,110){\circle*{5}}
 \put(140,120){\makebox(0,0){$c$}}
 \put(140,50){\line(0,1){60}}

 \put(20,50){\line(2,1){120}}
 \put(20,110){\line(2,-1){120}}
 \put(80,80){\circle*{5}}
 \put(80,90){\makebox(0,0){$b$}}
 \put(110,80){\circle*{5}}
 \put(120,80){\makebox(0,0){$e$}}
 
 \put(80,20){\makebox(0,0){$G$}}

 \put(250,50){\circle*{5}}
 \put(250,40){\makebox(0,0){$6$}}
 \put(250,50){\line(1,0){30}}
 \put(280,50){\circle*{5}}
 \put(280,40){\makebox(0,0){$5$}}
 \put(280,50){\line(1,1){30}}
 \put(310,80){\circle*{5}}
 \put(320,70){\makebox(0,0){$4$}}
 \put(310,80){\line(1,0){30}}
 \put(340,80){\circle*{5}}
 \put(350,70){\makebox(0,0){$3$}}
 \put(340,80){\line(0,1){30}}
 \put(340,110){\circle*{5}}
 \put(350,120){\makebox(0,0){$2$}}
 \put(340,110){\line(-1,0){30}}
 \put(310,110){\circle*{5}}
 \put(300,120){\makebox(0,0){$1$}}
 \put(310,110){\line(0,-1){30}}
 
 \put(295,20){\makebox(0,0){$H$}}
\end{picture}
\end{center}

\noindent Raz\~{o}es pelas quais $G$ e $H$ n\~{a}o s\~{a}o isomorfos entre si:

\begin{itemize}
 \item $H$ \'{e} conectado e $G$ n\~{a}o \'{e}.
 \item $G$ cont\'{e}m um tri\^{a}ngulo e $H$ n\~{a}o cont\'{e}m.
 \item $G$ cont\'{e}m um v\'{e}rtice de grau 4 e $H$ n\~{a}o cont\'{e}m.
 \item $G$ tem 2 componentes e $H$ n\~{a}o tem.
 \item $G^c$ tem um v\'{e}rtice de grau 5 e $H^c$ n\~{a}o tem.
 \item Etc....
\end{itemize}

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

\newslide{Isomorfismo é difícil}

\vspace*{5mm}
\noindent Como encontrar uma correspond\^{e}ncia um-para-um, que demonstre que dois
grafos s\~{a}o isomorfos?

\vspace*{10mm}
\begin{itemize}
 \item N\~{a}o existe t\'{e}cnica eficiente.
\vspace*{5mm}
 \item Grafos de tamanho moderado: usar bom senso.
\end{itemize}

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

\newslide{Um exemplo}

\noindent Dois grafos com número idêntico de v\'{e}rtices, arestas e sequ\^{e}ncia de graus, \textcolor{black}{n\~{a}o} isomorfos:

\begin{center}
\begin{picture}(400,140)
 \put(20,50){\circle*{5}}
 \put(20,40){\makebox(0,0){$x_6$}}
 \put(20,110){\circle*{5}}
 \put(20,120){\makebox(0,0){$x_1$}}
 \put(20,50){\line(0,1){60}}
        
 \put(80,50){\circle*{5}}
 \put(80,40){\makebox(0,0){$x_5$}}
 \put(80,110){\circle*{5}}
 \put(80,120){\makebox(0,0){$x_2$}}
 \put(80,50){\line(0,1){60}}
        
 \put(140,50){\circle*{5}}
 \put(140,40){\makebox(0,0){$x_4$}}
 \put(140,110){\circle*{5}}
 \put(140,120){\makebox(0,0){$x_3$}}
 \put(140,50){\line(0,1){60}}

 \put(80,20){\makebox(0,0){$K_{3,3}$}}

 \put(20,50){\line(1,1){60}}
 \put(80,50){\line(1,1){60}}
        
 \put(20,110){\line(1,-1){60}}
 \put(80,110){\line(1,-1){60}}
        
 \put(20,50){\line(2,1){120}}
 \put(20,110){\line(2,-1){120}}

 \put(250,50){\circle*{5}}
 \put(240,41){\makebox(0,0){c}}
 \put(370,50){\circle*{5}}
 \put(380,41){\makebox(0,0){b}}
 \put(310,90){\circle*{5}}
 \put(310,120){\makebox(0,0){a}}
 
 \put(340,60){\circle*{5}}
 \put(300,91){\makebox(0,0){d}}
 \put(310,110){\circle*{5}}
 \put(342,68){\makebox(0,0){e}}
 \put(280,60){\circle*{5}}
 \put(277,70){\makebox(0,0){f}}
 
 \put(250,50){\line(1,0){120}}
 \put(250,50){\line(1,1){60}}
 \put(370,50){\line(-1,1){60}}
 \put(250,50){\line(3,1){30}}
 \put(280,60){\line(1,0){60}}
 \put(370,50){\line(-3,1){30}}
 \put(310,110){\line(0,-1){20}}
 
 \put(310,90){\line(-1,-1){30}} 
 \put(310,90){\line(1,-1){30}} 

 \put(310,20){\makebox(0,0){$K$}}
\end{picture}
\end{center}

\noindent $K_{3,3}$ e $K$ n\~{a}o s\~{a}o isomorfos:
\begin{quote}
 $K$ cont\'{e}m um tri\^{a}ngulo, e $K_{3,3}$ n\~{a}o cont\'{e}m. \\
 \\ Outra raz\~ao: K \'e planar, $K_{3,3}$ n\~{a}o \'e...
\end{quote}
%--------------------------------------------------------------------------------------------

\section{PLANARIDADE}
\hypertarget{planaridade-1}{}

\newslide{Planaridade}

\vspace*{5mm}
\noindent Um grafo \'{e} \textcolor{black}{planar} se, e somente se, pode ser imerso no plano.

\vspace*{10mm}
\noindent Basta considerar \underline{grafos simples}, pois:
\begin{itemize}
 \item Um grafo $G$ \'{e} planar se, e somente se, o grafo simples obtido
       \begin{itemize}
        \item removendo-se todos os la\c{c}os de $G$, e
        \item substituindo-se cada aresta m\'{u}ltipla de $G$ por uma aresta,
       \end{itemize}
       \'{e} planar.
 \item Um grafo \'{e} planar se, e somente se, sua subdivis\~ao \'e planar.
\end{itemize}

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

\newslide{Determinar planaridade de grafos}

\noindent \textcolor{black}{Existem t\'{e}cnicas eficientes para determinar se um grafo simples
\'{e} planar.}

\vspace*{10mm}
A seguir, algumas t\'{e}cnicas mais f\'{a}ceis para seres humanos.

\vspace*{10mm}
\noindent Em qualquer imers\~{a}o, ciclos devem ser tra\c{c}ados como ``c\'{\i}rculos'':

\vspace*{5mm}
\begin{itemize}
 \item tra\c{c}ar primeiro \textcolor{black}{ciclos longos}, depois tentar tra\c car o resto.
\end{itemize}

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

\newslide{Um exemplo}

\noindent \begin{description}
 \item[Proposi\c{c}\~{a}o:] \
 
       \textcolor{black}{$K_{3,3}$ n\~{a}o \'{e} planar}.
       
 \item[Prova:] (M\'etodo dos ciclos longos)

\vspace*{5mm}
       Em qualquer imers\~{a}o, deve-se tra\c{c}ar o ciclo:
       \begin{center}
       \begin{picture}(160,110)
        \put(20,60){\circle*{5}}
        \put(10,60){\makebox(0,0){$y_3$}}
        \put(20,60){\line(1,1){30}}
        \put(20,60){\line(1,-1){30}}
        \put(50,90){\circle*{5}}
        \put(50,100){\makebox(0,0){$x_1$}}
        \put(50,30){\circle*{5}}
        \put(50,20){\makebox(0,0){$x_3$}}
        \put(50,30){\line(1,0){60}}
        \put(50,90){\line(1,0){60}}
        
        \put(110,30){\circle*{5}}
        \put(110,20){\makebox(0,0){$y_2$}}
        \put(110,90){\circle*{5}}
        \put(110,100){\makebox(0,0){$y_1$}}
        \put(110,30){\line(1,1){30}}
        \put(110,90){\line(1,-1){30}}
        \put(140,60){\circle*{5}}
        \put(140,70){\makebox(0,0){$x_2$}}
       \end{picture}
       \end{center}
       
%--------------------------------------------------------------------------------------------

\newslide{Continuação do exemplo}

       As 3 arestas restantes s\~{a}o: $\{x_1,y_2\}$, $\{x_2,y_3\}$ e $\{x_3,y_1\}$.
       Dois casos:
       \begin{itemize}
        \item $\{x_1,y_2\}$ \underline{dentro} do ciclo.
        
              Ent\~{a}o $\{x_2,y_3\}$ deve ser tra\c{c}ado fora:
       \begin{center}
       \begin{picture}(150,110)
        \put(20,60){\circle*{5}}
        \put(10,60){\makebox(0,0){$y_3$}}
        \put(20,60){\line(1,1){30}}
        \put(20,60){\line(1,-1){30}}
        \put(50,90){\circle*{5}}
        \put(50,100){\makebox(0,0){$x_1$}}
        \put(50,30){\circle*{5}}
        \put(50,20){\makebox(0,0){$x_3$}}
        \put(50,30){\line(1,0){60}}
        \put(50,90){\line(1,0){60}}

        \put(50,90){\line(1,-1){60}}
        \put(20,60){\line(0,-1){25}}
        \put(140,60){\line(0,-1){25}}
        \put(80,35){\oval(120,50)[b]}
        
        \put(110,30){\circle*{5}}
        \put(110,20){\makebox(0,0){$y_2$}}
        \put(110,90){\circle*{5}}
        \put(110,100){\makebox(0,0){$y_1$}}
        \put(110,30){\line(1,1){30}}
        \put(110,90){\line(1,-1){30}}
        \put(140,60){\circle*{5}}
        \put(140,70){\makebox(0,0){$x_2$}}
       \end{picture}
       \end{center}
              N\~{a}o h\'{a} como tra\c{c}ar $\{x_3,y_1\}$.
        \item $\{x_1,y_2\}$ \underline{fora} do ciclo: an\'{a}logo.
       \end{itemize}

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

\newslide{Outro exemplo}

 \item[Proposi\c{c}\~{a}o:] \
 
       \textcolor{black}{$K_5$ n\~{a}o \'{e} planar.}
       
 \item[Prova:] \

       Em qualquer imers\~{a}o, deve-se tra\c{c}ar o ciclo:
       \begin{center}
       \begin{picture}(100,110)
        \put(20,60){\circle*{5}}
        \put(10,60){\makebox(0,0){$x_5$}}
        \put(20,60){\line(1,1){30}}
        \put(20,60){\line(1,-1){30}}
        \put(50,90){\circle*{5}}
        \put(50,100){\makebox(0,0){$x_1$}}
        \put(50,30){\circle*{5}}
        \put(50,20){\makebox(0,0){$x_4$}}
        \put(80,60){\circle*{5}}
        \put(95,60){\makebox(0,0){$x_2$}}
        \put(80,60){\line(-1,1){30}}
        \put(80,60){\line(-1,-1){30}}
       \end{picture}
       \end{center}
       
%--------------------------------------------------------------------------------------------

\newslide{Continuação do exemplo}

       Faltam o v\'{e}rtice $x_3$ e as arestas $\{x_1,x_3\}$, $\{x_2,x_3\}$,
       $\{x_3,x_4\}$, $\{x_3,x_5\}$, $\{x_1,x_4\}$ e $\{x_2,x_5\}$.
       Dois casos:
       \begin{itemize}
        \item $\{x_2,x_5\}$ \underline{dentro} do ciclo.
        
              Ent\~{a}o $\{x_1,x_4\}$ deve ser tra\c{c}ado fora:
       \begin{center}
       \begin{picture}(100,110)
        \put(20,60){\circle*{5}}
        \put(10,60){\makebox(0,0){$x_5$}}
        \put(20,60){\line(1,0){60}}
        \put(50,60){\oval(115,60)[r]}
        \put(20,60){\line(1,1){30}}
        \put(20,60){\line(1,-1){30}}
        \put(50,90){\circle*{5}}
        \put(50,100){\makebox(0,0){$x_1$}}
        \put(50,30){\circle*{5}}
        \put(50,20){\makebox(0,0){$x_4$}}
        \put(80,60){\circle*{5}}
        \put(95,60){\makebox(0,0){$x_2$}}
        \put(80,60){\line(-1,1){30}}
        \put(80,60){\line(-1,-1){30}}
       \end{picture}
       \end{center}
              N\~{a}o h\'{a} como colocar $x_3$.
        \item $\{x_2,x_5\}$ \underline{fora} do ciclo: an\'{a}logo.
       \end{itemize} 
\end{description}

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

\newslide{Exemplo}

\begin{center}
 \begin{picture}(220,100)
  \put(20,20){\circle*{5}}
  \put(20,10){\makebox(0,0){$h$}}
  \put(20,80){\circle*{5}}
  \put(20,90){\makebox(0,0){$a$}}
  \put(20,20){\line(0,1){60}}
  \put(20,20){\line(1,1){60}}
  \put(20,20){\line(3,1){180}}
  
  \put(80,20){\circle*{5}}
  \put(80,10){\makebox(0,0){$g$}}
  \put(80,80){\circle*{5}}
  \put(80,90){\makebox(0,0){$b$}}
  \put(80,20){\line(-1,1){60}}
  \put(80,20){\line(0,1){60}}
  \put(80,20){\line(1,1){60}}
  
  \put(140,20){\circle*{5}}
  \put(140,10){\makebox(0,0){$f$}}
  \put(140,80){\circle*{5}}
  \put(140,90){\makebox(0,0){$c$}}
  \put(140,20){\line(-1,1){60}}
  \put(140,20){\line(0,1){60}}
  \put(140,20){\line(1,1){60}}
  
  \put(200,20){\circle*{5}}
  \put(200,10){\makebox(0,0){$e$}}
  \put(200,80){\circle*{5}}
  \put(200,90){\makebox(0,0){$d$}}
  \put(200,20){\line(-3,1){180}}
  \put(200,20){\line(-1,1){60}}
  \put(200,20){\line(0,1){60}}
 \end{picture}
\end{center}

Tra\c{c}ando o maior ciclo, e inserindo as arestas restantes:
\begin{center}
 \begin{picture}(130,140)
  \put(50,110){\circle*{5}}
  \put(50,120){\makebox(0,0){$h$}}
  \put(50,110){\line(1,0){30}}
  \put(80,110){\circle*{5}}
  \put(80,120){\makebox(0,0){$b$}}
  \put(80,110){\line(1,-1){30}}
  \put(110,80){\circle*{5}}
  \put(120,80){\makebox(0,0){$g$}}
  \put(110,80){\line(0,-1){30}}
  \put(110,50){\circle*{5}}
  \put(120,50){\makebox(0,0){$c$}}
  \put(110,50){\line(-1,-1){30}}
  \put(80,20){\circle*{5}}
  \put(80,10){\makebox(0,0){$f$}}
  \put(80,20){\line(-1,0){30}}
  \put(50,20){\circle*{5}}
  \put(50,10){\makebox(0,0){$d$}}
  \put(50,20){\line(-1,1){30}}
  \put(20,50){\circle*{5}}
  \put(10,50){\makebox(0,0){$e$}}
  \put(20,50){\line(0,1){30}}
  \put(20,80){\circle*{5}}
  \put(10,80){\makebox(0,0){$a$}}
  \put(20,80){\line(1,1){30}}
  
  \put(20,80){\line(1,0){90}}
  \put(20,50){\line(1,0){90}}
  \put(50,65){\oval(110,90)[l]}
  \put(80,65){\oval(110,90)[r]}
 \end{picture}
\end{center}

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

\newslide{Homorfismo de grafos}

\noindent Dois grafos, $G$ e $H$, s\~{a}o \textcolor{black}{homomorfos} se, e somente se, existe
um grafo $I$ tal que:
\begin{itemize}
 \item $G$ \'e isomorfo a algum grafo obtido de $I$ por meio de uma sequ\^encia de subdivis\~oes de (zero ou mais)
       arestas de $I$.
 \item $H$ \'e isomorfo a algum grafo obtido de $I$ por meio de uma sequ\^encia de subdivis\~oes de (zero ou mais)
       arestas de $I$.
\end{itemize}

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

\begin{center}
\begin{picture}(380,90)
 \put(10,70){\makebox(0,0){a}}
 \put(20,60){\circle*{5}}
 \put(20,60){\line(1,0){40}}
 \put(70,70){\makebox(0,0){b}}
 \put(60,60){\circle*{5}}
 \put(60,60){\line(0,-1){40}}
 \put(70,10){\makebox(0,0){c}}
 \put(60,20){\circle*{5}}
 \put(60,20){\line(-1,0){40}}
 \put(10,10){\makebox(0,0){d}}
 \put(20,20){\circle*{5}}
 \put(20,20){\line(0,1){40}}
 
 \put(40,0){\makebox(0,0){$G$}}
 
 \put(150,70){\makebox(0,0){a}}
 \put(150,60){\circle*{5}}
 \put(150,60){\line(1,-2){20}}
 \put(150,60){\line(-1,-2){20}}
 \put(120,10){\makebox(0,0){c}}
 \put(130,20){\circle*{5}}
 \put(130,20){\line(1,0){40}}
 \put(180,10){\makebox(0,0){b}}
 \put(170,20){\circle*{5}}
 
 \put(150,0){\makebox(0,0){$H$}}

 \put(250,70){\makebox(0,0){a}}
 \put(250,60){\circle*{5}}
 \put(250,60){\line(0,-1){40}}
 \put(240,40){\makebox(0,0){b}}
 \put(250,40){\circle*{5}}
 \put(250,10){\makebox(0,0){c}}
 \put(250,20){\circle*{5}}

 \put(250,0){\makebox(0,0){$I$}}

 \put(310,70){\makebox(0,0){a}}
 \put(3150,60){\circle*{5}}
 \put(310,60){\line(0,-1){40}}
 \put(300,40){\makebox(0,0){b}}
 \put(310,40){\circle*{5}}
 \put(310,40){\line(1,0){20}}
 \put(340,40){\makebox(0,0){d}}
 \put(330,40){\circle*{5}}
 \put(310,10){\makebox(0,0){c}}
 \put(310,20){\circle*{5}}
 
 \put(320,0){\makebox(0,0){$J$}}
\end{picture}
\end{center}

\begin{itemize}
 \item $G$ e $H$ s\~{a}o homomorfos;
 \item $I$ e $J$ n\~{a}o s\~{a}o homomorfos.
\end{itemize}

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

\newslide{Um teorema importante}


\noindent \begin{description}
 \item[Teorema de Kuratowski:] \
 
       Um grafo \textcolor{black}{n\~{a}o \'{e}} planar se, e somente se, tem um subgrafo homomorfo a
       $K_{3,3}$ ou $K_3$.
       
 \item[Prova:] \
 
       Veja [Liu, 1968], por exemplo.
\end{description}

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

\newslide{Outro teorema}

\vspace*{10mm}
\noindent \begin{description}
 \item[F\'{o}rmula de Euler:] \
 
       Seja $G$ um grafo \textcolor{orange}{conectado} \textcolor{black}{planar} com $V$ v\'{e}rtices e $E$ arestas. Seja
       $F$ o n\'{u}mero de faces (regi\~{o}es) em que o plano \'{e} dividido em uma \textcolor{orange}{imers\~{a}o}
       de $G$ no plano. Ent\~{a}o $V-E+F=2$.
       
 \item[Prova:] \
 
       Por indu\c{c}\~{a}o sobre $N(E)$.\\
			(No passo indutivo, considera-se 2 casos: grafos com e sem ciclos.)
\end{description}

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

\newslide{Um corolário}

\noindent \begin{description}
 \item[Corol\'{a}rio:] \
 
       Seja $G$ um grafo \textcolor{orange}{simples} \textcolor{black}{planar} com $V$ v\'{e}rtices e $E$ arestas,
       $E>1$. Ent\~{a}o $E\leq 3V-6$.
       
 \item[Prova:] \
 
       Segue do fato de que $3F\leq 2E$, e da f\'{o}rmula de Euler.
\end{description}

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

\defskiptarget{capitulo6}

\lastpage 

\end{document}