\documentclass[12pt,a4paper]{report}

\addtolength{\topmargin}{-0.5in}
\addtolength{\textheight}{1.0in}

\newcounter{conta}
\begin{document}
 
\noindent Departamento de Ci\^{e}ncia da Computa\c{c}\~{a}o \hfill ICEx/UFMG \\
{\it Matem\'{a}tica Discreta} \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2002 \\
Professor: Newton Jos\'{e} Vieira \\
\underline{S\'etima Lista de Exerc\'{\i}cios} \hfill Entrega: 12/03/2003.

\noindent{Introdu\c{c}\~{a}o \`{a} Teoria dos Grafos}
 
\begin{enumerate}
 \item Uma mulher deve transportar um le\~{a}o, uma raposa e um coelho de uma margem
       a outra de um rio, em um barco que s\'{o} cabe a mulher e mais um dos
       animais. Se o le\~{a}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. Este problema pode ser modelado via grafos, criando-se um
       v\'{e}rtice para cada configura\c{c}\~{a}o segura (aquela em que ningu\'{e}m come
       ningu\'{e}m) poss\'{\i}vel, e uma aresta entre dois v\'{e}rtices se a configura\c{c}\~{a}o
       representada por um puder ser obtida daquela representada pelo outro
       cruzando-se o rio. Assim feito, um caminho simples do v\'{e}rtice inicial
       (que representa todos na margem A) ao v\'{e}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\c{c}a para a raposa e o coelho.
 \item Um conjunto de v\'{e}rtices de um grafo \'{e} dito {\it dominante\/}, se todo
       v\'{e}rtice que n\~{a}o esteja no conjunto \'{e} adjacente a algum v\'{e}rtice do
       conjunto. Um conjunto {\it dominante minimal\/} \'{e} um conjunto dominante
       que n\~{a}o tem nenhum subconjunto pr\'{o}prio que seja conjunto dominante.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Encontre conjuntos dominantes minimais para $K_n$ e $K_{n,n}$.
        \item Encontre conjuntos dominantes minimais de tamanhos diferentes para
              o grafo:
              \begin{center}
              \begin{picture}(160,150)
               \put(50,20){\circle*{5}}
               \put(40,10){\makebox(0,0){d}}
               \put(50,20){\line(1,0){60}}
               \put(110,20){\circle*{5}}
               \put(120,10){\makebox(0,0){c}}
               \put(110,20){\line(1,2){30}}
               
               \put(140,80){\circle*{5}}
               \put(150,80){\makebox(0,0){b}}
               \put(140,80){\line(-1,1){60}}
               
               \put(80,140){\circle*{5}}
               \put(80,150){\makebox(0,0){a}}
               \put(80,140){\line(-1,-1){60}}
               
               \put(20,80){\circle*{5}}
               \put(10,80){\makebox(0,0){e}}
               \put(20,80){\line(1,-2){30}}
               \put(20,80){\line(1,0){120}}
               \put(60,80){\circle*{5}}
               \put(50,90){\makebox(0,0){f}}
               \put(60,80){\line(1,3){20}}
               \put(100,80){\circle*{5}}
               \put(110,90){\makebox(0,0){g}}
               \put(100,80){\line(-1,3){20}}
               
               \put(80,50){\circle*{5}}
               \put(90,50){\makebox(0,0){h}}
               \put(50,20){\line(1,1){30}}
               \put(110,20){\line(-1,1){30}}
               \put(80,50){\line(-2,3){20}}
               \put(80,50){\line(2,3){20}}
              \end{picture}
              \end{center}
        \item Uma rainha {\it domina\/} uma posi\c{c}\~{a}o em um tabuleiro de xadrez se
              est\'{a} na mesma linha, coluna ou diagonal da posi\c{c}\~{a}o. Descreva um
              modelo em grafo para o problema de determinar o n\'{u}mero m\'{\i}nimo de
              rainhas necess\'{a}rio para dominar todas as posi\c{c}\~{o}es do tabuleiro.
       \end{list}
 \item Prove que um grafo simples com $n$ v\'{e}rtices n\~{a}o pode ser bipartite se
       tiver mais de $n^2/4$ v\'{e}rtices. (Sugest\~{a}o: Suponha que pode ser. Ent\~{a}o
       os v\'{e}rtices podem ser divididos em conjuntos de $k$ e $n-k$ v\'{e}rtices.
       Conte o n\'{u}mero de arestas.)
 \item Um v\'{e}rtice $v$ \'{e} dito ser uma {\it articula\c{c}\~{a}o\/} em $G$ quando sua
       remo\c{c}\~{a}o desconecta $G$. Prove que $v$ \'{e} uma articula\c{c}\~{a}o se, e somente se,
       existem v\'{e}rtices $u$ e $w$ tais que $v$ est\'{a} em todo caminho simples
       entre $u$ e $w$ em $G$.
 \item Uma {\it ponte\/} em $G$ \'{e} uma aresta cuja remo\c{c}\~{a}o desconecta $G$. Prove
       que $e$ \'{e} uma ponte em $G$ se, e somente se, existem dois v\'{e}rtices $u$ e
       $v$ tais que todos os caminhos simples entre $u$ e $v$ cont\^{e}m $e$.
 \item Qual \'{e} o maior n\'{u}mero poss\'{\i}vel de arestas em um grafo com 31 v\'{e}rtices, se
       cada v\'{e}rtice tem grau, no m\'{a}ximo, igual a 3?
 \item Qual \'{e} o maior n\'{u}mero poss\'{\i}vel de v\'{e}rtices em um grafo com 20 arestas, se
       cada v\'{e}rtice tem grau, no m\'{\i}nimo, igual a 4?
 \item Prove que sim ou que n\~{a}o:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item \'{E} poss\'{\i}vel ter um grupo de 9 pessoas, cada uma das quais conhece
              exatamente 5 das outras.
        \item Em qualquer grupo, o n\'{u}mero de pessoas n\~{a}o apertaram as m\~{a}os de um
              n\'{u}mero \'{\i}mpar de pessoas do grupo \'{e} par.
        \item O n\'{u}mero de todos os seres humanos (vivos e mortos) que se casaram
              um n\'{u}mero \'{\i}mpar de vezes \'{e} par.
        \item Em qualquer livraria, o n\'{u}mero de livros com um n\'{u}mero \'{\i}mpar de
              p\'{a}ginas \'{e} par.
       \end{list}
 \item Prove que se $G$ \'{e} um grafo com exatamente 2 v\'{e}rtices de grau \'{\i}mpar,
       ent\~{a}o ambos os v\'{e}rtices est\~{a}o no mesmo componente.
 \item Suponha que um grafo simples $G$ tem $n$ v\'{e}rtices, $n-1$ dos quais de
       grau \'{\i}mpar. Quantos v\'{e}rtices de grau \'{\i}mpar existem em $G^c$?
 \item Seja $G$ um grafo regular de grau $n$, sendo $n$ \'{\i}mpar. Prove que o
       n\'{u}mero de arestas em $G$ \'{e} divis\'{\i}vel por $n$.
 \item Prove que todo grafo em que todos os v\'{e}rtices t\^{e}m grau maior ou igual a
       2 cont\'{e}m um ciclo.
 \item Encontre todos os grafos simples de 4 v\'{e}rtices n\~{a}o isomorfos entre si.
 \item Suponha que uma imers\~{a}o do grafo simples $G$ no plano tenha 20 faces. Se
       $G$ \'{e} regular de grau 5, quantos v\'{e}rtices cont\'{e}m $G$?
 \item Prove que se $G$ \'{e} um grafo planar com $k$ componentes, ent\~{a}o qualquer
       imers\~{a}o de $G$ satisfaz $V-E+F=k+1$.
\end{enumerate}

\end{document}