\documentclass[11pt,a4paper]{article}

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

\setlength{\textheight}{250mm}
\newcounter{conta}
\pagestyle{empty}
\begin{document}

\vspace*{10mm}
\noindent {\it Matem\'{a}tica Discreta}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2008 \\
Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG\\
\underline{Quarta Prova}/Solu\c{c}\~ao do professor \hfill 23/06/2008

\vspace*{1mm}
\begin{enumerate}
 \item {\footnotesize Resolva, justificando de forma bem clara:
       \begin{list}{\alph{conta})}{\usecounter{conta}}
%        \item Quantos v\'ertices tem um caminho simples de comprimento $n$?
        \item Desenhe um grafo simples com mais de um v\'ertice, $G$, e seu complemento, $G^c$, com
              o menor n\'umero de v\'ertices poss\'{\i}vel, tais que $G$ e $G^c$ tenham o mesmo n\'umero de arestas.
        \item Para que valores de $n$ $K_n$ \'e Euleriano e para que valores de $n$ $K_n$ \'e Hamiltoniano?
%        \item Em um grafo conexo com $n$ v\'ertices, qual \'e o menor n\'umero poss\'{\i}vel de arestas?
%        \item Se um grafo simples tem 60 arestas, qual \'e o n\'umero m\'{\i}nimo de v\'ertices que ele pode ter?
       \end{list}}

       \textit{Solu\c{c}\~ao\/}:

       \begin{list}{\alph{conta})}{\usecounter{conta}}
%        \item Um caminho simples de comprimento $n$ tem $n_1$ v\'ertices ($n$ arestas).
        \item O menor $n>1$ tal que $K_n$ tem um n\'umero par de arestas \'e 4 ($C(4,2)=6$ arestas). Assim,
              basta que $G$ seja um subgrafo gerador de $K_4$ com a metade das arestas; e $G^c$ ser\'a o
              subgrafo gerador de $K_4$ com a outra metade das arestas. Por exemplo:
            \begin{center}
             \mbox{\setlength{\unitlength}{1mm}
              \begin{picture}(130,13)
               \gasset{Nw=1.4, Nh=1.4, Nmr=1.4, fillcolor=Gray, fillgray=0,
                       curvedepth=0, AHnb=0}

               \put(31,5){\makebox(0,0)[r]{$G$:}}
               \node(1a)(35,10){}
               \node(1b)(45,10){}
               \node(1c)(45,0){}
               \node(1d)(35,0){}

               \put(66,5){\makebox(0,0)[r]{$G^c$:}}
               \node(2a)(70,10){}
               \node(2b)(80,10){}
               \node(2c)(80,0){}
               \node(2d)(70,0){}

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

               \drawedge(2b,2c){}
               \drawedge(2b,2d){}
               \drawedge(2c,2d){}
            \end{picture}
           }
       \end{center}
        \item $K_n$ \'e Euleriano quando $n$ \'e \'{\i}mpar, pois, neste caso, ele \'e um grafo em que todos os
              v\'ertices t\^em grau par. $K_n$ \'e Hamiltoniano sempre que $n\not=2$.
%        \item Em um grafo conexo com $n$ v\'ertices o menor n\'umero poss\'{\i}vel de arestas \'e $n-1$. 
%        \item Como $K_n$ tem $C(n,2)$ arestas e, para esse n\'umero de arestas, nenhum outro grafo simples
%              tem menos v\'ertices, o n\'umero m\'{\i}nimo de v\'ertices que um grafo simples com 60 arestas
%              pode ter \'e o menor $n$ tal que $C(n,2)\geq 60$. Como $C(11,2)=55$ e $C(12,2)=66$, o n\'umero
%              m\'{\i}nimo \'e $12$ v\'ertices.
       \end{list}

 \item {\footnotesize Sobre quantidades de v\'ertices e arestas:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Quantos v\'ertices e arestas tem um grafo simples conexo regular de grau 3,
              se $E=2V-6$?
        \item Quantas arestas tem um grafo simples com 2 componentes conexos, um de 15 v\'ertices
              e outro com 16 v\'ertices, ambos grafos regulares, um de grau 3 e outro de grau 4?
       \end{list}}

       \textit{Solu\c{c}\~ao\/}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Como o grafo \'e simples conexo regular de grau 3, $3V=2E$. Como $E=2V-6$,
              $3V=4V-12$. Logo, $V=12$ e $E=2\times 12-6=18$.
        \item O componente de 15 v\'ertices n\~ao pode ter grau 3, pois teria um n\'umero \'{\i}mpar
              de v\'ertices de grau \'{\i}mpar. Logo ele tem grau 4 e o outro tem grau 3. Assim,
              tem-se que $4\times 15+3\times 16=2E$. Logo, $E=(60+48)/2=54$.
       \end{list}
 \item {\footnotesize Em certo grupo de 19 pessoas, sabe-se que:
       \begin{itemize}
        \item todos os irm\~aos de cada pessoa participam do grupo;
        \item cada pessoa tem pelo menos um irm\~ao;
        \item 10 pessoas t\^em um n\'umero \'{\i}mpar de irm\~aos;
        \item 9 pessoas t\^em um n\'umero par de irm\~aos.
       \end{itemize}
       Se o grupo for particionado de maneira que todos os irm\~aos, e apenas
       irm\~aos, fiquem no mesmo subgrupo, quantos subgrupos ser\~ao formados:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item no m\'{\i}nimo?
        \item no m\'aximo?
       \end{list}
       D\^e tamb\'em os tamanhos dos subgrupos em cada caso.}

       \textit{Solu\c{c}\~ao\/}:

       Modelagem: a cada pessoa corresponde um v\'ertice e se duas pessoas s\~ao irm\~as, h\'a uma aresta
       incidente aos v\'ertices respectivos. Com isto, a cada subgrupo corresponde necessariamente um grafo
       completo (pois todos s\~ao irm\~aos entre si). Observe tamb\'em que, como um grafo completo \'e regular,
       v\'ertices de grau par devem pertencer a componentes diferentes daqueles que cont\^em v\'ertices de
       grau \'{\i}mpar.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Como em $K_{10}$ todos os v\'ertice t\^em
              grau \'{\i}mpar e em $K_9$ todos t\^em grau par, ser\~ao formados, no m\'{\i}nimo, 2 grupos,
              um de 10 e o outro de 9 pessoas.
        \item Os 10 v\'ertices de grau \'{\i}mpar podem formar 5 grafos $K_2$ (imposs\'{\i}vel formar mais grafos
              mantendo cada grau \'{\i}mpar). E os 9 de grau par podem formar 3 grafos $K_3$ (\'e imposs\'{\i}vel
              formar mais grafos mantendo cada grau par). Logo, ser\~ao formados no m\'aximo 8 grupos, 5 de duas
              pessoas e 3 de tr\^es pessoas.
       \end{list}

 \item {\footnotesize A seguir est\'a desenhada uma constru\c{c}\~ao com quatro salas, designadas por S1 a S4,
       interconectadas por seis portas, P1 a P6.

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

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

         \node[Nw=2, Nh=6](p5)(50,7.5){}
         \node[Nw=2, Nh=6](p6)(70,7.5){}

         \put(60,32){\makebox(0,0)[b]{\small P1}}
         \put(40,17){\makebox(0,0)[b]{\small P2}}
         \put(60,17){\makebox(0,0)[b]{\small P3}}
         \put(80,17){\makebox(0,0)[b]{\small P4}}
         \put(48,7.5){\makebox(0,0)[r]{\small P5}}
         \put(72,7.5){\makebox(0,0)[l]{\small P6}}

         \put(60,24){\makebox(0,0){S1}}
         \put(39,7.5){\makebox(0,0){S2}}
         \put(60,7.5){\makebox(0,0){S3}}
         \put(81,7.5){\makebox(0,0){S4}}
        \end{picture}
       } \\
       Determine o n\'umero m\'{\i}nimo de novas portas a instalar de forma que uma pessoa possa, ao
       chegar na constru\c{c}\~ao, passar por cada porta exatamente uma vez e sair para o exterior.
       Justifique modelando o problema por meio de grafo. Em que locais devem ser instaladas as
       novas portas (se o n\'umero m\'{\i}nimo de novas portas for maior que zero)?}

       \textit{Solu\c{c}\~ao\/}:

       Modelando o problema por meio de um grafo, obt\'em-se:
       \begin{center}
             \mbox{\setlength{\unitlength}{1mm}
              \begin{picture}(60,35)
               \gasset{Nw=1.4, Nh=1.4, Nmr=1.4, fillcolor=Gray, fillgray=0,
                       curvedepth=0, AHnb=0}

               \node(e)(30,34){}
               \put(33,34){\makebox(0,0){$e$}}
               \node(s1)(30,20){}
               \put(33,21){\makebox(0,0){$s_1$}}
               \node(s2)(15,10){}
               \put(12,10){\makebox(0,0){$s_2$}}
               \node(s3)(30,5){}
               \put(30,2){\makebox(0,0){$s_3$}}
               \node(s4)(45,10){}
               \put(48,10){\makebox(0,0){$s_4$}}

               \drawedge(e,s1){}
               \drawedge(s1,s2){}
               \drawedge(s1,s3){}
               \drawedge(s1,s4){}
               \drawedge(s2,s3){}
               \drawedge(s3,s4){}
            \end{picture}
           }
       \end{center}
       em que o v\'ertice $e$ corresponde \`a \'area externa, cada v\'ertice $s_i$ corresponde a uma sala
       S$i$ e cada aresta a uma porta. O grafo tem
       trajeto Euleriano come\c{c}ando em $e$ e terminando em $s_3$; por exemplo: $e\,s_1\,s_2\,s_3\,s_4\,s_1\,s_3$.
       Para obter um circuito Euleriano, basta colocar uma porta da sala S3 para o exterior, o que corresponde,
       no grafo a adicionar a aresta $\{e,s_3\}$, fazendo com que o grafo s\'o tenha v\'ertices de grau par.
       Com isto, um circuito Euleriano come\c{c}ando e terminando em $e$ seria $e\,s_1\,s_2\,s_3\,s_4\,s_1\,s_3\,e$,
       o que corresponde a uma pessoa:
       \begin{enumerate}
        \item entrar na sala S1 (porta P1);
        \item passar para a sala S2 (porta P2);
        \item passar para a sala S3 (porta P5);
        \item passar para a sala S4 (porta P6);
        \item passar para a sala S1 (porta P4);
        \item passar para a sala S3 (porta P3);
        \item sair para o exterior (porta nova).
       \end{enumerate}
\end{enumerate}
\end{document}
