\documentclass[12pt,a4paper]{article}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}
\usepackage{fullpage}
\usepackage{gastex}
\usepackage[usenames]{color}

\newcounter{conta}
\begin{document}
 
\noindent Departamento de Ciência da Computação \hfill ICEx/UFMG \\
{\it Matemática Discreta} \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2013 \\
Professor: Newton José Vieira \\
\underline{Quarta Lista de Exercícios} \hfill Entrega: 25/11/2013.

\vspace*{3mm}
\noindent {\bf Introdução à Teoria dos Grafos}
 
\begin{enumerate}
 \item {\footnotesize Quantas arestas têm os grafos $K_n^c$ e $K_{m,n}^c$?}

       \textit{Solução}:

       $K_n^c$ não tem arestas. $K_{m,n}^c$ tem $C(m+n,2)-mn=C(m,2)+C(n,2)$ arestas.

 \item {\footnotesize Uma mulher deve transportar um leão, uma raposa e um coelho de uma margem a outra de um rio, em um barco que
       só cabe a mulher e mais um dos animais. Se o leão e a raposa, ou a raposa e o coelho, ficarem na margem oposta
			 em que estiver a mulher, em dado instante, o primeiro come o segundo (esse leão não gosta de coelho). Este
			 problema pode ser modelado via grafos, criando-se um vértice para cada configuração segura (aquela em que ninguém
			 come ninguém) possível, e uma aresta entre dois vértices se a configuração representada por um puder ser obtida
			 daquela representada pelo outro cruzando-se o rio. Assim feito, um caminho simples do vértice inicial (que
			 representa todos na margem A) ao vértice meta (todos na outra margem) corresponde a uma forma de cruzar o rio
			 com os ditos elementos. Construa o grafo, e mostre todas as formas de cruzar o rio com segurança para a raposa
			 e o coelho.}

       \textit{Solução}:

       Cada vértice terá a forma $x/y$, em que $x$ é ``-'' ou uma sequência de símbolos m, l, r, c. A sequência $x$
			 denota os elementos que estão na margem origem e $y$ os elementos na margem destino (m: mulher, l: leão, r: raposa,
			 c: coelho). Existirá uma aresta $\{x_1/y_1,x_2/y_2\}$, caso a situação representada por $x_2/y_2$ possa ser obtida
       a partir daquela representada por $x_1/y_1$. As arestas não são direcionadas, representando o fato de que se
			 $x_2/y_2$ pode ser obtida a partir de $x_1/y_1$, então $x_1/y_1$ pode ser obtido a partir $x_2/y_2$ (como pode ser
			 facilmente verificado). Com isto, o grafo será:
   
            \begin{center} \footnotesize
             \mbox{\setlength{\unitlength}{1mm}
              \begin{picture}(120,22)
               \gasset{Nw=11, Nh=5, Nmr=7, curvedepth=0, AHnb=0}

               \node(mlrc)(0,10){mlrc/-}
               \node(lc)(20,10){lc/mr}
               \node(mlc)(40,10){mlc/r}

               \node(c)(50,20){c/mlr}
               \node(mrc)(70,20){mrc/l}
               \node(l)(50,0){l/mrc}
               \node(mlr)(70,0){mlr/c}

               \node(r)(80,10){r/mlc}
               \node(mr)(100,10){mr/lc}
               \node(v)(120,10){-/mlrc}

               \drawedge(mlrc,lc){}
               \drawedge(lc,mlc){}
               \drawedge(mlc,c){}
               \drawedge(mlc,l){}

               \drawedge(c,mrc){}
               \drawedge(mrc,r){}

               \drawedge(l,mlr){}
               \drawedge(mlr,r){}

               \drawedge(r,mr){}
               \drawedge(mr,v){}
            \end{picture}}
					\end{center}
  
	     Existem dois caminhos mais curtos que representam formas de cruzar o rio sem perdas:
       \begin{itemize}
        \item $\mbox{mlrc/-},\mbox{lc/mr},\mbox{mlc/r},\mbox{c/mlr},\mbox{mrc/l},\mbox{r/mcl},\mbox{mr/cl},\mbox{-/mlrc}$
        \item $\mbox{mlrc/-},\mbox{lc/mr},\mbox{mlc/r},\mbox{l/mrc},\mbox{mlr/c},\mbox{r/mcl},\mbox{mr/cl},\mbox{-/mlrc}$
       \end{itemize}


 \item {\footnotesize Prove que um grafo simples com $n$ vértices não pode ser bipartite se tiver mais de $n^2/4$ arestas.
      \textit{Dica}: Suponha que pode ser bipartite. Então os vértices podem ser divididos em conjuntos de $k$ e $n-k$
			 vértices. Conte o número de arestas.}

       \textit{Solução}:

       Suponha que o grafo é bipartite. Ent\~{a}o seus v\'{e}rtices podem ser
       divididos em dois conjuntos de $k$ e $n-k$ v\'{e}rtices, de tal forma
       que vértices do mesmo conjunto não são adjacentes. Neste caso, o
       número máximo de arestas é $k\times (n-k)$ (o grafo seria
       do tipo $K_{k,n-k}$). O valor de $k$ para o qual $k\times (n-k)$  atinge o
       máximo é dado por $d(k\times (n-k))/dk=0$, ou seja, por
       $d(nk-k^2))/dk=0$, ou ainda, $n-2k=0$, o que dá $k=n/2$. Assim, o
       número máximo de arestas é $(n/2)\times (n/2)=n^2/4$! Assim, tendo
       o grafo mais de $n^2/4$ arestas, ele não pode ser bipartite.    

 \item {\footnotesize Qual é o maior número possível de arestas em um grafo com 31 vértices, se cada vértice tem grau, no máximo, igual a 3?}

       \textit{Solução}:

       Sabe-se que $\sum_{v\in V}\mbox{\it grau\/}(v)=2|E|$. Como o número de
       vértices de grau ímpar é par, para satisfazer as condiç\~oes
       do problema, basta ter $\sum_{v\in V}\mbox{\it grau\/}(v)=30\times 3+2=
       92$. Assim, tem-se que o número máximo de arestas é $|E|=92/2=46$.

 \item {\footnotesize Prove que se $G$ é um grafo com exatamente 2 vértices de grau ímpar, então ambos os vértices estão no mesmo
       componente conectado.}

       \textit{Solução}:

       Seja um grafo $G$ com exatamente 2 vértices de grau ímpar. Já
       que o número de vértices de grau ímpar de um grafo é par,
       um componente de $G$, que também é um grafo, não pode ter apenas
       um dos dois vértices de grau ímpar. Logo, ambos devem estar no
       mesmo componente.

 \item {\footnotesize Desenhe todos os grafos simples de 4 vértices não isomorfos entre si.}

       \textit{Solução}:

       Abaixo estão listados os 11 grafos existentes:
       \begin{center}
             \mbox{\setlength{\unitlength}{1mm}
              \begin{picture}(120,53)
               \gasset{Nw=1.4, Nh=1.4, Nmr=1.4, fillcolor=Gray, fillgray=0,
                       curvedepth=0, AHnb=0}

               \node(1a)(10,50){}
               \node(1b)(20,50){}
               \node(1c)(20,40){}
               \node(1d)(10,40){}
               \node(2a)(40,50){}
               \node(2b)(50,50){}
               \node(2c)(50,40){}
               \node(2d)(40,40){}
               \node(3a)(70,50){}
               \node(3b)(80,50){}
               \node(3c)(80,40){}
               \node(3d)(70,40){}
               \node(4a)(100,50){}
               \node(4b)(110,50){}
               \node(4c)(110,40){}
               \node(4d)(100,40){}

               \drawedge(2a,2b){}
               \drawedge(3a,3b){}
               \drawedge(3b,3c){}
               \drawedge(4a,4b){}
               \drawedge(4c,4d){}

               \node(5a)(10,30){}
               \node(5b)(20,30){}
               \node(5c)(20,20){}
               \node(5d)(10,20){}
               \node(6a)(40,30){}
               \node(6b)(50,30){}
               \node(6c)(50,20){}
               \node(6d)(40,20){}
               \node(7a)(70,30){}
               \node(7b)(80,30){}
               \node(7c)(80,20){}
               \node(7d)(70,20){}
               \node(8a)(100,30){}
               \node(8b)(110,30){}
               \node(8c)(110,20){}
               \node(8d)(100,20){}

               \drawedge(5a,5b){}
               \drawedge(5b,5c){}
               \drawedge(5c,5d){}
               \drawedge(6a,6b){}
               \drawedge(6b,6c){}
               \drawedge(6b,6d){}
               \drawedge(7a,7b){}
               \drawedge(7b,7c){}
               \drawedge(7c,7a){}
               \drawedge(8a,8b){}
               \drawedge(8b,8c){}
               \drawedge(8c,8d){}
               \drawedge(8d,8a){}

               \node(9a)(10,10){}
               \node(9b)(20,10){}
               \node(9c)(20,0){}
               \node(9d)(10,0){}
               \node(10a)(40,10){}
               \node(10b)(50,10){}
               \node(10c)(50,0){}
               \node(10d)(40,0){}
               \node(11a)(70,10){}
               \node(11b)(80,10){}
               \node(11c)(80,0){}
               \node(11d)(70,0){}

               \drawedge(9a,9b){}
               \drawedge(9b,9c){}
               \drawedge(9c,9a){}
               \drawedge(9c,9d){}
               \drawedge(10a,10b){}
               \drawedge(10b,10c){}
               \drawedge(10c,10d){}
               \drawedge(10d,10a){}
               \drawedge(10a,10c){}
               \drawedge(11a,11b){}
               \drawedge(11b,11c){}
               \drawedge(11c,11d){}
               \drawedge(11d,11a){}
               \drawedge(11a,11c){}
               \drawedge(11b,11d){}

            \end{picture}
           }
       \end{center}

 \item {\footnotesize Suponha que uma imersão do grafo simples $G$ no plano tenha 20 faces. Se $G$ é regular de grau 5, quantos
       vértices $G$ contém?}

       \textit{Solução}:

       Como $G$ é regular de grau 5, tem-se que $5|V|=2|E|$. A fórmula de
       Euler diz que $|V|-|E|+F=2$. Com isto, tem-se que $|V|-5|V|/2+20=2$ e,
       portanto, $|V|=12$.
 \item {\footnotesize Prove que se $G$ é um grafo planar com $k$ componentes, então qualquer imersão de $G$ satisfaz $V-E+F=k+1$.}

       \textit{Solução}:

       Sejam $H_1$, $H_2$, \ldots, $H_k$ os $k$ componentes de $G$ ($k\geq 1$).
       Para cada componente $H_i$ tem-se que $|V_{H_i}|-|E_{H_i}|+F_{H_i}=2$.
       Portanto, tem-se que:
       \[\sum_{i=1}^{k}(|V_{H_i}|-|E_{H_i}|+F_{H_i})=2k\mbox{.}\]
       Mas, $\sum_{i=1}^{k}|V_{H_i}|=|V_G|$, $\sum_{i=1}^{k}|E_{H_i}|=|E_G|$ e
       $\sum_{i=1}^{k}F_{H_i}=F_G+(k-1)$; esta última se deve ao fato de que
       a face externa é contada uma vez para cada $H_i$. Logo,
       \[|V_{G}|-|E_{G}|+F_{G}+(k-1)=2k\mbox{,}\]
       e, portanto, $|V_G|-|E_G|+F_G=k+1$.

\end{enumerate}

\vspace*{3mm}
\noindent {\bf Caminhamentos}
 
\begin{enumerate}
 \item[9.] {\footnotesize Liste todos os grafos simples de quatro vértices:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Eulerianos.
        \item Hamiltonianos.
       \end{list}}

       \textit{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Eulerianos:
            \begin{center}
             \mbox{\setlength{\unitlength}{1mm}
              \begin{picture}(120,13)
               \gasset{Nw=1.4, Nh=1.4, Nmr=1.4, fillcolor=Gray, fillgray=0,
                       curvedepth=0, AHnb=0}

               \node(1a)(10,10){}
               \node(1b)(20,10){}
               \node(1c)(20,0){}
               \node(1d)(10,0){}

               \node(7a)(40,10){}
               \node(7b)(50,10){}
               \node(7c)(50,0){}
               \node(7d)(40,0){}

               \node(8a)(70,10){}
               \node(8b)(80,10){}
               \node(8c)(80,0){}
               \node(8d)(70,0){}

               \drawedge(7a,7b){}
               \drawedge(7b,7c){}
               \drawedge(7c,7a){}

               \drawedge(8a,8b){}
               \drawedge(8b,8c){}
               \drawedge(8c,8d){}
               \drawedge(8d,8a){}

            \end{picture}
           }
       \end{center}

        \item Hamiltonianos:
            \begin{center}
             \mbox{\setlength{\unitlength}{1mm}
              \begin{picture}(120,13)
               \gasset{Nw=1.4, Nh=1.4, Nmr=1.4, fillcolor=Gray, fillgray=0,
                       curvedepth=0, AHnb=0}

               \node(8a)(10,10){}
               \node(8b)(20,10){}
               \node(8c)(20,0){}
               \node(8d)(10,0){}

               \node(10a)(40,10){}
               \node(10b)(50,10){}
               \node(10c)(50,0){}
               \node(10d)(40,0){}

               \node(11a)(70,10){}
               \node(11b)(80,10){}
               \node(11c)(80,0){}
               \node(11d)(70,0){}

               \drawedge(8a,8b){}
               \drawedge(8b,8c){}
               \drawedge(8c,8d){}
               \drawedge(8d,8a){}

               \drawedge(10a,10b){}
               \drawedge(10b,10c){}
               \drawedge(10c,10d){}
               \drawedge(10d,10a){}
               \drawedge(10a,10c){}

               \drawedge(11a,11b){}
               \drawedge(11b,11c){}
               \drawedge(11c,11d){}
               \drawedge(11d,11a){}
               \drawedge(11a,11c){}
               \drawedge(11b,11d){}

            \end{picture}
           }
       \end{center}
       \end{list}

 \item[10.] {\footnotesize Qual é o número mínimo de arestas a adicionar ao grafo de K\"onigsberg, de forma que se obtenha um grafo
       Euleriano?}

       \textit{Solução}:

       A metade do número de vértices de grau ímpar: 2.

 \item[11.] {\footnotesize Para que valores de $m$ e $n$ são $K_n$ e $K_{m,n}$ Eulerianos?}

       \textit{Solução}:

       $K_n$ é Euleriano quando $n$ é ímpar, pois, neste caso,
       todos os vértices têm grau par. $K_{m,n}$ é Euleriano quando $m$ e
       $n$ são pares.

 \item[12.] {\footnotesize Uma \textit{ponte} em um grafo é uma aresta cuja remoção desconecta o grafo.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Um grafo Euleriano pode conter uma ponte?
				\item Um grafo com trajeto Euleriano pode conter uma ponte?
       \end{list}}

       \textit{Solução}:

       Um grafo Euleriano não pode conter uma ponte, mas um grafo com trajeto
       Euleriano pode.

 \item[13.] {\footnotesize Desenhe, se possível, grafos simples com as seguintes características:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O grafo tem um trajeto Euleriano e um caminho Hamiltoniano.
        \item O grafo não tem um trajeto Euleriano, nem caminho Hamiltoniano.
       \end{list}}

       \textit{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Grafo simples com trajeto Euleriano e caminho Hamiltoniano:
        
            \begin{center}
             \mbox{\setlength{\unitlength}{1mm}
              \begin{picture}(120,6)
               \gasset{Nw=1.4, Nh=1.4, Nmr=1.4, fillcolor=Gray, fillgray=0,
                       curvedepth=0, AHnb=0}

               \node(1a)(10,3){}
               \node(1b)(20,3){}
               \drawedge(1a,1b){}

            \end{picture}
           }
       \end{center}

        \item Grafo simples sem trajeto Euleriano, nem caminho Hamiltoniano:
       
            \begin{center}
             \mbox{\setlength{\unitlength}{1mm}
              \begin{picture}(120,13)
               \gasset{Nw=1.4, Nh=1.4, Nmr=1.4, fillcolor=Gray, fillgray=0,
                       curvedepth=0, AHnb=0}

               \node(1a)(10,10){}
               \node(1b)(20,10){}
               \node(1c)(20,0){}
               \node(1d)(10,0){}
               \drawedge(1a,1b){}
               \drawedge(1c,1d){}

            \end{picture}
           }
           \end{center}
       \end{list}

 \item[14.] {\footnotesize Seja o seguinte tabuleiro, em que \begin{picture}(7,8) \put(4,2){\circle*{6}} \end{picture} representa
       um cavalo preto e \begin{picture}(7,8) \put(4,2){\circle{6}} \end{picture} representa um cavalo branco:
       \begin{center}
       \begin{picture}(110,70)
        \put(20,5){\line(1,0){60}}
        \put(20,25){\line(1,0){60}}
        \put(20,45){\line(1,0){60}}
        \put(20,65){\line(1,0){60}}
        \put(20,5){\line(0,1){60}}
        \put(40,5){\line(0,1){60}}
        \put(60,5){\line(0,1){60}}
        \put(80,5){\line(0,1){60}}
        \put(30,15){\circle{6}}
        \put(70,15){\circle{6}}
        \put(30,55){\circle*{6}}
        \put(70,55){\circle*{6}}
       \end{picture}
       \end{center}
       Lembrando que um cavalo (no jogo de xadrez) se move em L, modele o problema por meio de grafo e mostre como
			 inverter as peças, isto é, colocar os cavalos pretos onde estão os brancos, e vice-versa.}

       \textit{Solução}:

       Modelando-se cada casa $(i,j)$, para $1\leq i,j\leq 3$ como um vértice de nome $ij$, e cada movimento possível
			 do cavalo como uma aresta, tem-se o seguinte grafo:
			 \begin{center} \footnotesize
        \mbox{\setlength{\unitlength}{1mm}
          \begin{picture}(120,37)
            \gasset{Nw=6, Nh=6, Nmr=6, curvedepth=0, AHnb=0}

            \node(11)(5,35){11}
            \node(12)(20,35){12}
            \node(13)(35,35){13}

            \node(21)(5,20){21}
            \node(22)(20,20){22}
            \node(23)(35,20){23}

            \node(31)(5,5){31}
            \node(32)(20,5){32}
            \node(33)(35,5){33}

            \drawedge(11,23){}
            \drawedge(23,31){}
            \drawedge(31,12){}
            \drawedge(12,33){}
            \drawedge(33,21){}
            \drawedge(21,13){}
            \drawedge(13,32){}
            \drawedge(32,11){}
           \end{picture}}
			\end{center}
      Ao ``desenrolar'' este grafo partindo-se de 11, caminhando-se no sentido horário e desenhando-se os vértices,
			mantendo-se a disposição de 3 em cada linha, tem-se a seguinte nova disposição dos vértices e arestas do mesmo grafo:
			 \begin{center} \footnotesize
        \mbox{\setlength{\unitlength}{1mm}
          \begin{picture}(120,37)
            \gasset{Nw=6, Nh=6, Nmr=6, curvedepth=0, AHnb=0}

            \node(11)(5,35){11}
            \node(23)(20,35){23}
            \node(31)(35,35){31}

            \node(32)(5,20){32}
            \node(22)(20,20){22}
            \node(12)(35,20){12}

            \node(13)(5,5){13}
            \node(21)(20,5){21}
            \node(33)(35,5){33}

            \drawedge(11,23){}
            \drawedge(23,31){}
            \drawedge(31,12){}
            \drawedge(12,33){}
            \drawedge(33,21){}
            \drawedge(21,13){}
            \drawedge(13,32){}
            \drawedge(32,11){}
           \end{picture}}
			\end{center}
			Veja que há várias soluções possíveis, tanto os cavalos se movendo no sentido horário no grafo acima, como
			no sentido anti-horário. Evidentemente, há a restrição de que para um cavalo se mover para a posição explicitada
			pelo vértice adjacente, é necessário que não haja cavalo na mesma; se houver, este deve ser movido antes.
			Na solução seguinte, pode-se ver os 4 cavalos como se movendo ``ao mesmo tempo'' girando em sentido horário, cada
			um se movendo 4 vezes. A solução é apresentada em 4 linhas, cada linha representando o movimento, ao mesmo tempo,
			dos 4 cavalos. Cada coluna mostra o trajeto de um dos cavalos. O movimento do cavalo em $i_1j_1$ para a posição
			$i_2j_2$ é representado por $i_1j_1\rightarrow i_2j_2$. Observe que os cavalos das posições 11 e 33 trocam de
			posição, assim como os cavalos das posições 13 e 31.
			
       \begin{tabular}{llll}
        \ \ \ $11\rightarrow 23$ & $31\rightarrow 12$ & $33\rightarrow 21$ & $13\rightarrow 32$ \\
        \ \ \ $23\rightarrow 31$ & $12\rightarrow 33$ & $21\rightarrow 13$ & $32\rightarrow 11$ \\
        \ \ \ $31\rightarrow 12$ & $33\rightarrow 21$ & $13\rightarrow 32$ & $11\rightarrow 23$ \\
        \ \ \ $12\rightarrow 33$ & $21\rightarrow 13$ & $13\rightarrow 11$ & $23\rightarrow 31$
       \end{tabular}

 \item[15.] {\footnotesize \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Mostre que se $G$ é um grafo simples com $n$ vértices e pelo menos $C(n-1,2)+2$ arestas, então $G$ é 
				      Hamiltoniano.
        \item Mostre que (a) não é verdade se a condição é relaxada para ``pelo menos $C(n-1,2)+1$ arestas''.
       \end{list}}

       \textit{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O número máximo de arestas em um grafo simples de $n$
              vértices, ou seja, o número de arestas em $K_n$, é $C(n,2)$.
              Assim, o déficit máximo de arestas em $G$, com relação a
              $K_n$, é $C(n,2)-[C(n-1,2)+2]=C(n-1,2)+C(n-1,1)-C(n-1,2)-2=
              n-3$. Assim, para dois vértices $u$ e $v$ quaisquer de $G$:
              \[\mbox{\it grau\/}(u)+\mbox{\it grau\/}(v)\geq [(n-1)+(n-1)]-
                (n-3)-1\mbox{.}\]
              O primeiro termo é a soma dos graus de $u$ e $v$ em $K_n$, o
              segundo desconta o {\it máximo\/} possível de arestas, e o
              terceiro se deve ao fato de que a aresta $\{u,v\}$ é contada 2 vezes
              no primeiro termo e subtraída apenas uma vez no segundo termo.
              Fazendo-se as contas, tem-se que $\mbox{\it grau\/}(u)+
              \mbox{\it grau\/}(v)\geq n$. Assim, pela proposição 7-6 do
              livro texto, $G$ é Hamiltoniano.
              
        \item O grafo $X=(\{a,b,c\},\{\{a,b\},\{b,c\}\})$ é um contra-exemplo,
              visto que $C(n-1,2)+1=2=E$ e, no entanto, $X$ não
              é Hamiltoniano.
       \end{list}
\end{enumerate}
\end{document}

