\documentclass[11pt,a4paper]{article}

\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 

\usepackage{fullpage}
\usepackage{gastex}
\usepackage[usenames]{color}


\pagestyle{empty}
\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 Prova} \hfill 25/11/2013

\vspace*{3mm}
\noindent Cada questão vale 2 pontos.
\vspace*{2mm}
\begin{enumerate}
 \item {\footnotesize Quantas arestas tem $K_n$, $K_n^c$, $K_{m,n}$ e $K_{m,n}^c$?}

       \textit{Solução}:
 
       \begin{quote}
			  $K_n$ tem $n(n-1)/2$ arestas. \\
				$K_n^c$ tem zero arestas. \\
				$K_{m,n}$ tem $m\times n$ arestas. \\
				$K_{m,n}^c$ tem $[m(m-1)+n(n-1)]/2$ arestas.
			 \end{quote}

 \item {\footnotesize Quantas vértices tem um grafo simples regular de grau 3, se $E=3V-15$?}

       \textit{Solução}:
 
       Para um grafo simples regular de grau 3, tem-se que $3V=2E$. Logo, se $E=3V-15$, segue-se
			 que $E=2E-15$ e, portanto, $E=15$. Logo, $V=10$.

 \item {\footnotesize Um certo grafo simples tem dois componentes conectados, um deles com 9 vértices e o outro com 10 vértices.
       Supondo que ambos os componentes são grafos regulares, um de grau 4 e outro de grau 5, quantas arestas tem
			 o grafo no total?}

       \textit{Solução}:
 
       Como o número de vértices de grau ímpar em um grafo é par, o componente de 9 vértices não pode ser o grafo regular de grau 5. Logo,
			 o componente de 9 vértices tem grau 4 e  o componente de 10 vértices tem grau 5. Segue-se que o número arestas do grafo é
			 $[9\times 4/2]+[10\times 5/2]=18+25=43$.

 \item {\footnotesize Quais, dentre os três grafos a seguir, são isomorfos? Para os isomorfos, dê correspondência um para um (função
       bijetora entre os vértices). Para os não isomorfos, apresente uma justificativa mostrando que não são.

       \mbox{\setlength{\unitlength}{1mm}
        \begin{picture}(120,28)(-10,0)
         \gasset{Nw=1, Nh=1, Nmr=0.5, fillcolor=Gray, fillgray=0, AHnb=0}

         \node(x1)(10,20){}
         \node(x2)(20,20){}
         \node(x3)(30,20){}
         \node(y1)(10,5){}
         \node(y2)(20,5){}
         \node(y3)(30,5){}

         \put(10,22){\makebox(0,0){$x_1$}}
         \put(20,22){\makebox(0,0){$x_2$}}
         \put(30,22){\makebox(0,0){$x_3$}}
         \put(10,4){\makebox(0,0)[tc]{$y_1$}}
         \put(20,4){\makebox(0,0)[tc]{$y_2$}}
         \put(30,4){\makebox(0,0)[tc]{$y_3$}}

         \drawedge(x1,y1){}
         \drawedge(x1,y2){}
         \drawedge(x1,y3){}
         \drawedge(x2,y1){}
         \drawedge(x2,y2){}
         \drawedge(x2,y3){}
         \drawedge(x3,y1){}
         \drawedge(x3,y2){}
         \drawedge(x3,y3){}

         \node(a)(55,20){}
         \node(b)(65,20){}
         \node(c)(70,12.5){}
         \node(d)(65,5){}
         \node(e)(55,5){}
         \node(f)(50,12.5){}

         \put(55,22){\makebox(0,0){$a$}}
         \put(65,22.1){\makebox(0,0){$b$}}
         \put(71,12.5){\makebox(0,0)[l]{$c$}}
         \put(65,4){\makebox(0,0)[tc]{$d$}}
         \put(55,4){\makebox(0,0)[tc]{$e$}}
         \put(49,12.5){\makebox(0,0)[r]{$f$}}

         \drawedge(a,b){}
         \drawedge(a,d){}
         \drawedge(a,f){}
         \drawedge(c,b){}
         \drawedge(c,d){}
         \drawedge(c,f){}
         \drawedge(e,b){}
         \drawedge(e,d){}
         \drawedge(e,f){}

         \node(2)(95,20){}
         \node(3)(105,20){}
         \node(4)(110,12.5){}
         \node(5)(105,5){}
         \node(6)(95,5){}
         \node(1)(90,12.5){}

         \put(95,22){\makebox(0,0){$1$}}
         \put(105,22.1){\makebox(0,0){$2$}}
         \put(111,12.5){\makebox(0,0)[l]{$3$}}
         \put(105,4){\makebox(0,0)[tc]{$4$}}
         \put(95,4){\makebox(0,0)[tc]{$5$}}
         \put(89,12.5){\makebox(0,0)[r]{$6$}}

         \drawedge(1,2){}
         \drawedge(2,3){}
         \drawedge(3,4){}
         \drawedge(4,5){}
         \drawedge(5,6){}
         \drawedge(6,1){}
         \drawedge(1,4){}
         \drawedge(2,6){}
         \drawedge(3,5){}

         \put(20,-3){\makebox(0,0){$G_1$}}
         \put(60,-3){\makebox(0,0){$G_2$}}
         \put(100,-3){\makebox(0,0){$G_3$}}
        \end{picture}
       } \\
       }

       \textit{Solução}:

       $G_1$ e $G_2$ são isomorfos. Uma função bijetora $f$ é aquela tal que:
			 \begin{quote}
			  $f(x_1)=a$, $f(x_2)=c$, $f(x_3)=e$, $f(y_1)=b$, $f(y_2)=d$, $f(y_3)=f$. 
			 \end{quote}
       $G_1$ (e também $G_2$) não é isomorfo a $G_3$, pois:
			 \begin{itemize}
 			  \item $G_1$ (e também $G_2$), que é $K_{3,3}$, não é planar;
			  \item e $G_3$ é planar: no desenho a acima, a aresta $\{3,6\}$ pode ser desenhada por fora,
			        obtendo-se uma imersão no plano.
       \end{itemize}

 \item {\footnotesize Um certo grafo simples planar tem 50 faces quando imerso no plano. Se ele for regular de grau 4, quantos vértices e arestas ele tem?}

       \textit{Solução}:

       Como o grafo é regular de grau 4, segue-se que $4V=2E$ e, assim $E=2V$. Pela fórmula de Euler, $V-E+F=2$. Logo,
			 $V-2V+50=2$ e, portanto, $V=48$. Segue-se que $E=96$.

 \item {\footnotesize Considerando todos os grafos simples de 4 vértices, não isomorfos entre si, quais deles são ambos, Eulerianos e Hamiltonianos?}

       \textit{Solução}:

       Apenas $K_{2,2}$ é ambos, Euleriano e Hamiltoniano.

 \item {\footnotesize A seguir está desenhada a planta de um estabelecimento em que se mostra 7 portas
       conectando 5 ambientes, denotados por $A_1$ a $A_5$, e o exterior, denotado por $E$:

       \mbox{\setlength{\unitlength}{1mm}
        \begin{picture}(120,56)
         \gasset{Nw=6, Nh=2, Nmr=0, fillcolor=Gray, fillgray=.9}

         \put(20,0){\framebox(80,50)}
         \put(30,25){\framebox(60,15)}
         \put(30,10){\framebox(40,15)}

         \put(30,25){\line(1,0){60}}
         \put(50,10){\line(0,1){30}}
         \put(70,10){\line(0,1){30}}
         \node(p1)(40,25){}
         \node(p2)(60,25){}
         \node(p3)(80,25){}

         \node[Nw=2, Nh=6](p4)(50,32.5){}
         \node[Nw=2, Nh=6](p5)(50,17.5){}
         \node[Nw=2, Nh=6](p6)(70,32.5){}
         \node[Nw=2, Nh=6](p7)(70,17.5){}

         \put(81,34){\makebox(0,0){$A_1$}}
         \put(60,34){\makebox(0,0){$A_2$}}
         \put(39,34){\makebox(0,0){$A_3$}}
         \put(60,17.5){\makebox(0,0){$A_4$}}
         \put(39,17.5){\makebox(0,0){$A_5$}}

         \put(85,12.5){\makebox(0,0){{\normalsize $E$}}}
        \end{picture}
       } \\
			
       Determine o número mínimo de novas portas a instalar de forma que uma pessoa possa, ao
			 chegar vindo do exterior (região $E$), passar por cada porta exatamente uma vez e sair de volta para o exterior.
       Justifique modelando o problema por meio de grafo. Em que locais deve(m) ser instalada(s) a(s)
       nova(s) porta(s) (se o número mínimo de novas portas for maior que zero)?}

       \textit{Solução}:
 
       Considerando um vértice para cada ambiente e uma aresta para cada porta, o problema pode ser modelado por
			 meio do grafo:

       \mbox{\setlength{\unitlength}{1mm}
        \begin{picture}(120,30)
         \gasset{Nw=6, Nh=6, Nmr=3, AHnb=0, fillcolor=Gray, fillgray=.9}

         \node(A3)(40,25){$A_3$}
         \node(A2)(60,25){$A_2$}
         \node(A1)(80,25){$A_1$}
         \node(E)(80,5){$E$}
         \node(A4)(60,5){$A_4$}
         \node(A5)(40,5){$A_5$}

         \drawedge(A3,A2){}
         \drawedge(A2,A1){}
         \drawedge(A5,A4){}
         \drawedge(A4,E){}
         \drawedge(A3,A5){}
         \drawedge(A2,A4){}
         \drawedge(A1,E){}
        \end{picture}
       } \\	
       Para que todos os vértices de tal grafo fiquem com grau par, e portanto ele se torne um grafo Euleriano, deve-se inserir no mínimo uma
			 aresta com extremidades $A_2$ e $A_4$, o que corresponde a colocar mais uma porta entre os ambientes $A_2$ e $A_4$.
       
 \item {\footnotesize Seja $G$ um grafo de $n$ vértices em que é possível rotular cada um dos $n$ vértices com $A$ ou $B$ de forma que vértices adjacentes recebam rótulos
       diferentes. Em um caminho Hamiltoniano em $G$, quanto vértices têm o rótulo $A$ e quantos têm o rótulo $B$? E em um ciclo Hamiltoniano, quantos vértices têm o rótulo
			 $A$ e quantos o rótulo $B$? }

       \textit{Solução}:

       Se $n$ for par, um caminho Hamiltoniano tem $n/2$ vértices com rótulo $A$ e $n/2$ com rótulo $B$; se  $n$ for ímpar,
			 um caminho Hamiltoniano tem $(n-1)/2$ de um tipo e $(n+1)/2$ do outro. Por outro lado, um ciclo Hamiltoniano só
			 pode existir se $n$ for par, e, neste caso, um ciclo Hamiltoniano tem $n/2$ vértices de um tipo e $(n/2)+1$ do outro
			 (já que o vértice de ínicio é o mesmo que aparece no fim).

\end{enumerate}

\end{document}
