\documentclass[12pt,a4paper]{article}

\usepackage[portuguese]{babel}
\usepackage{fullpage}

\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{1}^{\mbox{\underline{o}}}$ semestre de 2008 \\
Professor: Newton Jos\'{e} Vieira \\
\underline{Quarta Lista de Exerc\'{\i}cios} \hfill Entrega: 23/06/2008.

\vspace*{3mm}
\noindent {\bf Introdu\c{c}\~{a}o \`{a} Teoria dos Grafos}
 
\begin{enumerate}
 \item Quantas arestas t\^em $K_n^c$ e $K_{m,n}^c$?
 \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 Prove que um grafo simples com $n$ v\'{e}rtices n\~{a}o pode ser bipartite se
       tiver mais de $n^2/4$ arestas. (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 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 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 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 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}

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

 \item[10.] Qual \'{e} o n\'{u}mero m\'{\i}nimo de arestas a adicionar ao grafo de K\"onigsberg,
       de forma que se obtenha um grafo Euleriano?

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

 \item[12.] Um grafo Euleriano pode conter uma ponte (uma aresta cuja remo\c{c}\~ao
            desconecta o grafo)? Um grafo com trajeto Euleriano pode conter uma ponte?

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

 \item[14.] Seja o seguinte tabuleiro, em que ``\begin{picture}(7,8)
       \put(4,3){\circle*{6}} \end{picture}'' representa um cavalo preto e
       ``\begin{picture}(7,8) \put(4,3){\circle{6}} \end{picture}'' representa um
       cavalo branco:
       \begin{center}
       \begin{picture}(130,110)
        \put(20,10){\line(1,0){90}}
        \put(20,40){\line(1,0){90}}
        \put(20,70){\line(1,0){90}}
        \put(20,100){\line(1,0){90}}
        \put(20,10){\line(0,1){90}}
        \put(50,10){\line(0,1){90}}
        \put(80,10){\line(0,1){90}}
        \put(110,10){\line(0,1){90}}
        \put(35,25){\circle{6}}
        \put(95,25){\circle{6}}
        \put(35,85){\circle*{6}}
        \put(95,85){\circle*{6}}
       \end{picture}
       \end{center}
       Inverter as pe\c{c}as, isto \'{e}, colocar os cavalos pretos onde est\~{a}o os
       brancos, e vice-versa.

% \item[14.] Seja $G$ um grafo simples Hamiltoniano com $V\geq 3$ v\'{e}rtices, $E$
%       arestas, e ciclo Hamiltoniano $C$. Seja $I$ um conjunto de $k$ v\'{e}rtices
%       de $G$, n\~{a}o adjacentes entre si. Ent\~{a}o, obviamente, para cada $x\in I$,
%       $\mbox{\it grau\/}(x)-2$ arestas incidentes n\~{a}o ser\~{a}o usadas em $C$.
%       Assim, no total, $E'=\sum_{x\in I}(\mbox{\it grau\/}(x)-2)$ arestas
%       incidentes com v\'{e}rtices em $I$ n\~{a}o aparecer\~{a}o em $C$.
%       \begin{list}{(\alph{conta})}{\usecounter{conta}}
%        \item Mostre que $E-E'\geq V$.
%        \item Por que \'{e} necess\'{a}rio dizer que os v\'{e}rtices de $I$ n\~{a}o s\~{a}o
%              adjacentes entre si?
%        \item Use (a) para mostrar que os seguintes grafos n\~{a}o s\~{a}o
%              Hamiltonianos:
%       \begin{center}       
%       \begin{picture}(200,230) \normalsize
%        \put(100,10){\makebox(0,0){a}}
%        \put(100,20){\circle*{5}}
%        \put(100,20){\line(0,1){20}}
%        \put(107,35){\makebox(0,0){b}}
%        \put(100,40){\circle*{5}}
%        \put(100,20){\line(-1,1){60}}
%        \put(100,20){\line(1,1){60}}
%        \put(100,40){\line(-1,1){50}}
%        \put(100,40){\line(1,1){50}}
%        \put(30,80){\makebox(0,0){c}}
%        \put(40,80){\circle*{5}}
%        \put(50,80){\makebox(0,0){d}}
%        \put(50,90){\circle*{5}}
%        \put(40,80){\line(1,1){10}}
%        \put(170,80){\makebox(0,0){e}}
%        \put(160,80){\circle*{5}}
%        \put(150,80){\makebox(0,0){f}}
%        \put(150,90){\circle*{5}}
%        \put(160,80){\line(-1,1){10}}
%        
%        \put(40,80){\line(0,1){70}}
%        \put(50,90){\line(0,1){50}}
%        \put(30,150){\makebox(0,0){g}}
%        \put(40,150){\circle*{5}}
%        \put(45,135){\makebox(0,0){h}}
%        \put(50,140){\circle*{5}}
%        \put(40,150){\line(1,-1){10}}
%        
%        \put(150,90){\line(0,1){50}}
%        \put(160,80){\line(0,1){70}}
%        \put(155,135){\makebox(0,0){i}}
%        \put(150,140){\circle*{5}}
%        \put(170,150){\makebox(0,0){j}}
%        \put(160,150){\circle*{5}}
%        \put(160,150){\line(-1,-1){10}}
%        
%        \put(40,150){\line(1,1){60}}
%        \put(50,140){\line(1,1){50}}
%        \put(160,150){\line(-1,1){60}}
%        \put(150,140){\line(-1,1){50}}
%        \put(100,220){\makebox(0,0){k}}
%        \put(100,210){\circle*{5}}
%        \put(107,195){\makebox(0,0){l}}
%        \put(100,190){\circle*{5}}
%        \put(100,190){\line(0,1){20}}
%       
%        \put(50,90){\line(1,0){100}}
%        \put(50,90){\line(1,2){50}}
%        \put(150,90){\line(-1,2){50}}
%        \put(100,80){\makebox(0,0){m}}
%        \put(100,90){\circle*{5}}
%        \put(68,145){\makebox(0,0){n}}
%        \put(75,140){\circle*{5}}
%        \put(132,145){\makebox(0,0){o}}
%        \put(125,140){\circle*{5}}
%        
%        \put(100,90){\line(0,1){25}}
%        \put(75,140){\line(1,-1){25}}
%        \put(125,140){\line(-1,-1){25}}
%        \put(100,125){\makebox(0,0){p}}
%        \put(100,115){\circle*{5}}
%       \end{picture}
%       \end{center}
%\begin{center}
%\begin{picture}(400,200) \normalsize
%\put(10,110){\makebox(0,0){d}}
%\put(20,110){\circle*{5}}
%\put(20,110){\line(2,1){180}}
%\put(20,110){\line(1,0){90}}
%\put(20,110){\line(2,-1){180}}
%
%\put(390,110){\makebox(0,0){b}}
%\put(380,110){\circle*{5}}
%\put(380,110){\line(-2,1){180}}
%\put(380,110){\line(-1,0){90}}
%\put(380,110){\line(-2,-1){180}}
%
%\put(200,10){\makebox(0,0){c}}
%\put(200,20){\circle*{5}}
%\put(200,20){\line(-1,2){30}}
%\put(200,20){\line(1,2){30}}
%\put(160,70){\makebox(0,0){j}}
%\put(170,80){\circle*{5}}
%\put(170,80){\line(1,1){60}}
%\put(240,70){\makebox(0,0){i}}
%\put(230,80){\circle*{5}}
%\put(230,80){\line(-1,1){60}}
%\put(215,110){\makebox(0,0){k}}
%\put(200,110){\circle*{5}}
%
%\put(200,210){\makebox(0,0){a}}
%\put(200,200){\circle*{5}}
%\put(200,200){\line(-1,-2){30}}
%\put(200,200){\line(1,-2){30}}
%\put(160,150){\makebox(0,0){f}}
%\put(170,140){\circle*{5}}
%\put(240,150){\makebox(0,0){g}}
%\put(230,140){\circle*{5}}
%
%\put(110,100){\makebox(0,0){e}}
%\put(110,110){\circle*{5}}
%\put(110,110){\line(2,1){60}}
%\put(110,110){\line(2,-1){60}}
%
%\put(290,100){\makebox(0,0){h}}
%\put(290,110){\circle*{5}}
%\put(290,110){\line(-2,1){60}}
%\put(290,110){\line(-2,-1){60}}
%\end{picture}
%\end{center}
%       \end{list}
 \item[15.] \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Mostre que se $G$ \'{e} um grafo simples com $n$ v\'{e}rtices e pelo menos
              $C(n-1,2)+2$ arestas, ent\~{a}o $G$ \'{e} Hamiltoniano.
        \item Mostre que (a) n\~{a}o \'{e} verdade se a condi\c{c}\~{a}o \'{e} relaxada para ``pelo
              menos $C(n-1,2)+1$ arestas''.
       \end{list}
\end{enumerate}

%\vspace*{3mm}
%\noindent {\bf \'{A}rvores}
 
%\begin{enumerate}
% \item[16.] Quantos v\'{e}rtices tem uma \'{a}rvore enraizada $m$-\'{a}ria completa de altura $h$?

% \item[17.] Uma {\it floresta\/} \'{e} um grafo cujos componentes s\~{a}o \'{a}rvores.
%       \begin{list}{(\alph{conta})}{\usecounter{conta}}
%        \item Quantas arestas h\'{a} em uma floresta com $n$ v\'{e}rtices e $k$
%              componentes?
%        \item Qual \'{e} o n\'{u}mero m\'{a}ximo de v\'{e}rtices em um grafo com 10 arestas e 3
%              componentes?
%       \end{list}

% \item[18.] Seja $T$ uma \'{a}rvore estritamente $m$-\'{a}ria enraizada. Prove:
%       \begin{list}{(\alph{conta})}{\usecounter{conta}}
%        \item Se $T$ tem $k$ v\'{e}rtices internos, ent\~{a}o tem $(m-1)k+1$ folhas.
%        \item Se $T$ tem $k$ folhas, ent\~{a}o tem $(k-1)/(m-1)$ v\'{e}rtices internos
%              e $(mk-1)/(m-1)$ v\'{e}rtices no total.
%        \item Se $T$ tem $n$ v\'{e}rtices no total, ent\~{a}o tem $(n-1)/m$ v\'{e}rtices
%              internos e $\frac{(m-1)n+1}{m}$ folhas.
%       \end{list}
% \item[19.] Mostre que um grafo conexo \'{e} uma \'{a}rvore se, e somente se, tem menos
%       arestas do que v\'{e}rtices.
% \item[20.] Sejam $n$ moedas, onde $n$ \'{e} pot\^{e}ncia de 3. As moedas t\^{e}m exatamente o
%       mesmo peso, exceto uma, que \'{e} mais leve que as outras. Tem-se uma balan\c{c}a
%       de pratos, em que se pode comparar os pesos de 2 cole\c{c}\~{o}es de moedas
%       quaisquer. Usando \'{a}rvores tern\'{a}rias (3-\'{a}rias), descreva um procedimento
%       para encontrar a moeda defeituosa, que use $log_3n$ pesadas para
%       encontrar a moeda. O que acontece se o n\'{u}mero de moedas n\~{a}o \'{e} pot\^{e}ncia
%       de 3?
%\end{enumerate}

\end{document}
\endinput
\end
 

 




