\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 Quantas arestas tem $K_n$, $K_n^c$, $K_{m,n}$ e $K_{m,n}^c$?

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

 \item 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?

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

 \item 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?

 \item Considerando todos os grafos simples de 4 vértices, não isomorfos entre si, quais deles são, ao mesmo tempo, Eulerianos e Hamiltonianos?

 \item 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)? \hfill
			 \textbf{$\Rightarrow$ continua no verso}

 \item 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$?
\end{enumerate}
\vspace{0.5mm} \hrule \vspace{0.4mm} \hrule

\vspace{3mm}
\noindent \textbf{Alguns lembretes:}
\begin{itemize}
 \item Grafo simples: aquele que não tem laços nem arestas múltiplas.
 \item $K_n$: grafo simples completo de $n$ vértices.
 \item $K_{m,n}$: grafo bipartite completo.
 \item $G^c$: o complemento do grafo $G$.
 \item Grafo conectado: aquele para o qual existe caminho de cada vértice a qualquer outro.
 \item Componente conectado: subgrafo ``maximal'' conectado.
 \item Grafo regular: aquele em que todos os vértices têm o mesmo grau.
 \item Grafo planar: aquele que pode ser desenhado sem que suas arestas se cruzem, a não ser nas extremidades.
 \item Grafo Euleriano: aquele que tem circuito Euleriano.
 \item Grafo Hamiltoniano: aquele que tem ciclo Hamiltoniano.
\end{itemize}

\end{document}
