%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Arquivo LaTeX2e para                                               %
%                                                                    %
% Exercícios de MAC328 Algoritmos em Grafos                          %
% 1o. semestre de 2007                                               %
% Y. Kohayakawa                                                      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Friday 01 Jun 2007 11:19:00am BRT yoshi@turan.ime.usp.br>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt,reqno]{amsart}

\usepackage[colorlinks,backref]{hyperref} 

%% Escrevendo em português:
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}
%----------------------------

%\usepackage{refcheck}
\usepackage{srcltx}
\usepackage{multicol}

\let\:=\colon
\let\epsilon=\varepsilon
\def\e{{\rm e}}
\def\dist{\mathop{\rm dist}\nolimits}
\def\supp{\mathop{\rm supp}\nolimits}
\def\ex{\mathop{\rm ex}\nolimits}
\def\bsigma{\bar\sigma}
\def\RR{\mathbb R}
\def\NN{\mathbb N}
\def\ZZ{\mathbb Z}
\def\({\left(}
\def\){\right)}  
\def\<{\langle}
\def\>{\rangle}
\def\llfloor{\left\lfloor}
\def\rrfloor{\right\rfloor}
\def\llceil{\left\lceil}
\def\rrceil{\right\rceil}
%\let\sim=\thicksim

\def\inR{\mathrel{\in_{\text R}}} 

\def\cA{\mathcal A}
\def\cB{\mathcal B}
\def\cC{\mathcal C}
\def\cD{\mathcal D}
\def\cF{\mathcal F}
\def\cG{\mathcal G}
\def\cH{\mathcal H}
\def\cI{\mathcal I}
\def\cL{\mathcal L}
\def\cP{\mathcal P}
\def\cR{\mathcal R}
\def\cS{\mathcal S}
\def\cT{\mathcal T}

\def\barp{{\bar p}}

\def\Bi{\mathop{{\rm Bi}}\nolimits}
\def\Var{\mathop{{\rm Var}}\nolimits}
\def\Cov{\mathop{{\rm Cov}}\nolimits}
\def\dev{\mathop{{\rm dev}}\nolimits}
\def\og{\mathop{{\rm og}}\nolimits}
\def\comp{^{\text{\rm c}}}

\def\EE{\mathop{\hbox{\hbox{${\mathbb E}$}}}\nolimits}
\def\PP{\mathop{\hbox{\raise.03ex\hbox{${\mathbb P}$}}}\nolimits}
\def\FF{\mathop{\hbox{\raise.03ex\hbox{${\mathbb F}$}}}\nolimits}

\def\RP{\mathbf{RP}}
\def\BPP{\mathbf{BPP}}

\def\bfx{\textbf{x}}
\def\bfy{\textbf{y}}

\makeatletter
\renewcommand{\labelenumi}{\theenumi.}
\makeatother

\def\datedue#1{$\{$\textsl{Data de entrega}: #1$\}$}
%\def\datedue#1{}
\def\sugestao#1{[\textit{Sugestão.} #1]}
\let\hint\sugestao
\def\observacao#1{[\textit{Observação.} #1]}

\begin{document}
\title[MAC328 Algoritmos em Grafos]{Exercícios de Algoritmos em
  Grafos\\1{\tiny o.} semestre de 2007}  
\date{Versão de \today}
\maketitle
\pagestyle{plain}
\footskip=25pt

\begin{enumerate}
\item Desenhe todos os grafos não-isomorfos com~$n$ vértices para todo~$0\leq
  n\leq4$.  (Por exemplo, para~$n=2$, você deve desenhar~$2$ grafos.)
  
\item Uma \textit{floresta} é um grafo acíclico (isto é, que não contém
  circuitos).  Uma \textit{árvore} é uma floresta conexa.  Desenhe todas as
  árvores com conjunto de vértices~$[n]=\{1,\dots,n\}$ para todo~$0\leq
  n\leq4$.  (Por exemplo, para~$n=3$, você deve desenhar~$3$ árvores.)
  
\item Seja~$g_n$ ($n\geq0$) o número total de grafos não-isomorfos com~$n$
  vértices (por exemplo, $g_2=2$).  Mostre que
  \begin{equation}
    \label{eq:g_n_ineq}
    2^{n\choose2}/n!\leq g_n\leq2^{n\choose2}.
  \end{equation}
  
\item{}[Desafio] Desenvolva um sistema computacional para determinar ou
  estimar~$g_n$ para valores grandes de~$n$. \datedue{em aberto}
  
\item (Exemplo~1.15 de ISTG) Duas arestas de um grafo~$G$ são
  \textit{adjacentes} se têm uma ponta comum.  Essa relação de adjacência
  define o \textit{grafo das arestas} de~$G$.  Se~$G'$ denota o grafo das
  arestas de~$G$, então~$V(G)=A(G)$ e cada aresta de~$G'$ é um par~$ab$ em
  que~$a$ e~$b$ são arestas adjacentes de~$G$.  Faça uma figura do grafo das
  arestas de um~$K_3$ e de um~$K_{1,3}$ (o grafo completo com~$3$ vértices e o
  grafo bipartido completo com classes de vértices de cardinalidades~$1$
  e~$3$).
  
  Faça uma figura do grafo das arestas de um~$K_4$.  Quantos vértices e
  quantas arestas tem o grafo das arestas de um~$K_n$?  Seja~$G$ o grafo das
  arestas de um~$K_5$.  Desenhe o \textit{complemento}~$G\comp=\overline G$
  de~$G$ (o grafo com conjunto de vértices~$V(G)$, com dois vértices
  distintos~$x$ e~$y$ de~$V(G)$ adjacentes neste grafo se e só se~$x$ e~$y$
  não são adjacentes em~$G$).
  
\item (E~1.17 de ISTG) Mostre que o grafo das arestas de um~$K_5$
  é isomorfo ao complemento do grafo de Petersen.

\item (Proposição~1.1 de ISTG) Prove que, em todo grafo, a soma dos graus dos
  vértices é igual ao dobro do número de arestas.  Ou seja, mostre que todo
  grafo~$(V,A)$ satisfaz a identidade~$\sum_{v\in V}g(v)=2|A|$.
  
\item (E~1.20 de ISTG) Mostre que todo grafo tem um número par de vértices de
  grau ímpar.
  
\item (E~1.21 de ISTG) Mostre que todo grafo com dois ou mais vértices tem
  pelo menos dois vértices de mesmo grau.
  
\item Mostre que um grafo é $2$-colorível se e só se ele não contém um
  circuito de comprimento ímpar.  \datedue{16/3/2007}
  
\item Descreva precisamente um algoritmo eficiente para decidir se um dado
  grafo é biparticionável.  \datedue{16/3/2007}
  
\item\label{ex:12} Gere vários grafos aleatórios com~$n$ vértices e~$m$
  arestas e estime a probabilidade de eles serem conexos.  Use os seguintes
  valores de~$m$ e~$n$ grandes:
  \begin{enumerate}
  \item[(\textit{i})] $m=\lceil(1/4)n\log n\rceil$,

  \item[(\textit{ii})] $m=\lceil(1/2)n\log n\rceil$,

  \item[(\textit{iii})] $m=\lceil n\log n\rceil$,

  \item[(\textit{iv})] $m=\lceil2n\log n\rceil$.

  \end{enumerate}
  Acima, escrevemos~$\log$ para o logaritmo natural~$\ln$.
  \datedue{23/3/2007} 
  
\item Mostre que todo grafo~$G$ com pelo menos um vértice contém um caminho de
  comprimento~$\delta(G)$.  Mostre que todo grafo~$G$ contém um circuito de
  comprimento pelo menos~$\delta(G)+1$, desde que~$\delta(G)\geq2$
  ($\delta(G)=\min_v\deg(v)$, onde o mínimo é tomado sobre todo~$v\in V(G)$
  e~$\deg(v)$ denota o grau de~$v$).  \datedue{23/3/2007}
  
\item Seja~$G$ um grafo conexo.  Considere a família~$\cF$ dos caminhos de
  comprimento máximo em~$G$.
  \begin{itemize}
  \item[(\textit{i})] Prove que quaisquer dois caminhos em~$\cF$ têm um
    vértice em comum.
  \item[(\textit{ii})] Suponha agora que os caminhos em~$\cF$ têm comprimento
    ímpar.  Prove que quaisquer dois caminhos em~$\cF$ têm pelo menos dois
    vértices em comum. 
  \end{itemize}

\item (E~1.39 de ISTG) Seja~$G$ um grafo com~$\delta(G)>(|V(G)|-2)/2$.  Mostre
  que~$G$ é conexo.
  
\item (E~1.40 de ISTG) Seja~$G$ um grafo com~$\delta(G)\geq3$.  Mostre que~$G$
  tem um circuito par.
  
\item (E~1.41 de ISTG) Mostre que todo grafo~$G$ satisfaz a desigualdade
  $|E(G)|\geq|V(G)|-c(G)$, onde~$c(G)$ é o número de componentes de~$G$.

\item Seja~$G$ um grafo conexo e~$T$ uma árvore geradora de~$G$ obtida pela
  execução de uma busca de profundidade em~$G$.  Dê um argumento preciso para
  provar que toda arestas em~$A(G)\setminus A(T)$ é da forma~$\{x,y\}$ com~$x$
  um ancestral de~$y$ em~$T$.  (Lembre que~$T$ tem uma raiz natural, a saber,
  o vértice~$r$ a partir do qual a busca em profundidade foi disparada.
  Dizemos que~$x$ é um ancestral de~$y$ em~$T$ se o único caminho de~$r$ a~$y$
  em~$T$ passa por~$x$.)  

\item Sejam~$G$ um grafo e~$v$ e~$w$ dois vértices de~$G$.  Mostre que se
  existe em~$G$ um passeio com extremos~$v$ e~$w$, então existe uma caminho
  com extremos~$v$ e~$w$ em~$G$.  

\item Desenhe o grafo com~$8$ vértices e~$10$ arestas dado por
%  \begin{multicols}{2}
  \begin{verbatim}
 0:  7  5  2
 1:  7
 2:  6  0
 3:  5  4
 4:  5  7  3  6
 5:  0  4  3
 6:  4  2
 7:  0  1  4
\end{verbatim}
    \noindent Simule a execução de \verb|dfsR(G, {0,0})| (busca em
    profundidade a partir do vértice~\verb|0|).  Determine os
    vetores~\verb|pre[]| e~\verb|st[]| após a execução desta chamada.
    Classifique todas os pares ordenados~$(a,b)$ com~$ab\in A(G)$ nos quatro
    tipos (\textit{i})~tipo árvore, (\textit{ii})~tipo pai,
    (\textit{iii})~tipo ascendente, (\textit{iv})~tipo descendente.
    \datedue{30/3/2007} 
%  \end{multicols}

\item Seja~$G$ um grafo $2$-aresta-conexo.  Prove que para quaisquer dois
  vértices distintos~$x$ e~$y$ de~$G$, existem dois caminhos~$P_1$ e~$P_2$
  de~$x$ a~$y$ que são disjuntos nas arestas (isto é, $E(P_1)\cap
  E(P_2)=\emptyset$).  \datedue{30/3/2007}

\item Faça o Exercício 18.42 do Sedgewick.

\item Faça o Exercício 18.43 do Sedgewick.  \datedue{10/4/2007}
  
\item Seja~$G=(V,E)$ um grafo.  Defina a relação~$\sim$ sobre~$E$ como segue:
  para todo~$e$ e~$f\in E$, $e\sim f$ se~$e=f$ ou existe um circuito em~$G$
  que contém ambos~$e$ e~$f$.  Prove que~$\sim$ é uma relação de equivalência
  sobre~$E(G)$.  \datedue{13/4/2007}
  
\item Escreva um algoritmo que, dado um DAG~$D$, determina o comprimento
  máximo de um caminho dirigido em~$D$.
  
\item Seja~$G$ um grafo dirigido.  O \textit{fecho transitivo}~$F=F(G)$ de~$G$
  é o grafo dirigido com~$V(F)=V(G)$ e com o arco~$(x,y)$ presente em~$E(F)$
  se e só se~$y$ é acessível a partir de~$x$ por um caminho dirigido em~$G$.
  Descreva um algoritmo que, dado um DAG~$D$ (um grafo dirigido acíclico),
  computa o fecho transitivo~$F=F(D)$ de~$D$.  Seu algoritmo deve ter
  complexidade de tempo~$O(n+M)$, onde~$n=|V(D)|$ e~$M=|E(F)|$.
  \datedue{8/5/2007}
  
\item\label{ex:27}
    Escreva um programa que recebe como entrada um grafo dirigido~$G$ e tem
  como saída os componentes fortemente conexos de~$G$.  O seu programa deve
  também ter como saída o tamanho (número de vértices) dos componentes
  fortemente conexos, ordenados de forma decrescente.  Seu programa deve ser
  eficiente, e deve receber como entrada os grafos gerados pelos programas
  \verb|g_roget_simples| e \verb|g_random|; veja {\small
  $$
  \verb|http://www.ime.usp.br/~yoshi/2007i/mac328/Exercicios/SGB/ROGET|
  $$
  e
  $$
  \verb|http://www.ime.usp.br/~yoshi/2007i/mac328/Exercicios/SGB/RANDOM|
  $$
  }
  %
  No caso de \verb|g_random|, os grafos de teste serão gerados com a opção
  \verb|-d| (para gerar grafos dirigidos).  Ainda no caso de \verb|g_random|,
  experimente os seguintes valores de~$m$ e~$n$ grandes (como sempre, $m$~é o
  número de arcos e~$n$ é o número de vértices):
  \begin{enumerate}
  \item[(\textit{i})] $m=\lfloor0.9n\rfloor$,

  \item[(\textit{ii})] $m=\lfloor0.95n\rfloor$,

  \item[(\textit{iii})] $m=n$,

  \item[(\textit{iv})] $m=\lfloor1.05n\rfloor$,

  \item[(\textit{v})] $m=\lfloor 1.1n\rfloor$,
  \end{enumerate}
  Seu programa deve admitir a opção \verb|-t| para imprimir somente o tamanho
  dos componentes fortemente conexos em ordem decrescente (esta opção é útil
  para estudar os casos em que~$n$ é grande).

  Você deve implementar os algoritmos de Kosaraju e de Tarjan.  Faça uma
  comparação empírica da eficiência dos dois algoritmos.
  \datedue{11/5/2007}
  
\item Use os programas que você escreveu no Exercício~\ref{ex:27} para estudar
  a ``estrutura de componentes (fortemente conexos)'' dos grafos dirigidos
  aleatórios dados no enunciado daquele exercício, isto é, gere grafos com os
  valores de~$m$ dados em~(\textit{i})--(\textit{v}) daquele exercício e
  valores grandes de~$n$ e procure descobrir se a ``cara'' do grafo muda
  conforme~$m$ cresce em relação a~$n$ (como dado
  em~(\textit{i})--(\textit{v})).  \datedue{27/5/2007}
  
\item Use os programas que você escreveu no Exercício~\ref{ex:27} para estudar
  para quais valores de~$m$ é provável que os grafos dirigidos aleatórios
  com~$n$ vértices ($n$~grande) e~$m$ arcos é fortemente conexo.
  Naturalmente, a resposta aqui é uma função de~$n$ (isto é, $m=m(n)$).
  \hint{Lembre do Exercício~\ref{ex:12}.}  \datedue{27/5/2007}

\item O algoritmo de Kosaraju para a determinação dos componentes fortemente
  conexos de um grafo dirigido envolve o cômputo do reverso de~$\vec G$;
  depois usamos o \textit{reverso} da ordem dada por \verb|post[]|.  Uma
  sugestão natural é usar o grafo original~$\vec G$ (\textit{sem}
  revertê-lo) e usar então a ordem dada por \verb|post[]| \textit{sem}
  revertê-la.  Esta idéia funciona?  Prove ou dê um contra-exemplo.
  \datedue{22/5/2007}

\item\label{ex:optim1} Seja~$G$ um grafo e~$c\:E(G)\to\RR$ uma função custo
  definida nas arestas de~$G$.  Seja~$T$ uma árvore geradora de~$G$.
  Para~$e\in E(T)$, sejam~$T_1^e$ e~$T_2^e$ os dois componentes de~$T-e$.
  Prove que são equivalentes:
  \begin{enumerate}
  \item[(\textit{i})] $T$~é uma árvore geradora de custo mínimo em~$G$.
  \item[(\textit{ii})] Toda aresta~$e\in E(T)$ tem peso mínimo dentre as
    arestas em $E(V(T_1^e),V(T_2^e))$.
  \end{enumerate}\datedue{1/6/2007}
  
\item Sejam~$G$ e~$c$ como no Exercício~\ref{ex:optim1}.  Seja~$T$ uma árvore
  geradora de~$G$.  Lembre que se~$e\in E(G)\setminus E(T)$, então o
  grafo~$T+e$ contém um único circuito, chamado de \textit{circuito
    fundamental de~$e$ em relação a~$T$}, freqüentemente denotado
  por~$C(e,T)$.  Prove que são equivalentes:
  \begin{enumerate}
  \item[(\textit{i})] $T$~é uma árvore geradora de custo mínimo em~$G$.
  \item[(\textit{ii})] Toda~$e\in E(G)\setminus E(T)$ tem peso máximo dentre
    as arestas em $C(e,T)$.
  \end{enumerate}\datedue{1/6/2007}
  
\item\label{ex:33} Seja~$G=(V,E)$ um grafo.  Podemos definir um grafo
  dirigido~$\vec G=(V,\vec E)$ a partir de~$G$, atribuindo para cada
  aresta~$e=\{x,y\}$ de~$G$ uma de suas duas possíveis orientações
  (formalmente, temos~$(x,y)\in\vec E$ ou~$(y,x)\in\vec E$, mas não ambos).
  Podemos chamar um tal~$\vec G$ de uma \textit{orientação} de~$G$.  Suponha
  que~$G$ tem duas árvores geradoras~$T_1$ e~$T_2$ disjuntas nas arestas, isto
  é, $T_1$~e~$T_2$ são subárvores de~$G$ com~$V(T_1)=V(T_2)=V(G)$ e
  $E(T_1)\cap E(T_2)=\emptyset$.  Mostre que~$G$ admite uma orientação~$\vec
  G$ fortemente conexa.
  
\item Vale a recíproca do Exercício~\ref{ex:33}?  Isto é, se um grafo~$G$
  admite uma orientação~$\vec G$ fortemente conexa, então há árvores~$T_1$
  e~$T_2$ como no enunciado daquele exercício?

\item\label{q:pot} Seja~$G$ um grafo dirigido e~$c\:E(G)\to\RR$ um
  função custo definida nos arcos de~$G$.  Por simplicidade, suponha que o
  custo de todo arco é não-negativo.  Fixe~$s\in V(G)$, e suponha que todo
  vértice de~$G$ é acessível a partir de~$s$.  Para todo~$x\in V(G)$,
  escrevemos~$d_c(s,x)$ para o custo mínimo dos caminhos dirigidos de~$s$
  a~$x$.  Um \textit{potencial~$p$ para~$(G,c)$} é uma função $p\:V(G)\to\RR$
  tal que
  \begin{equation}
    \label{eq:pot_prop}
    p(v)\leq p(u)+c(u,v)\text{ para todo~$(u,v)\in E(G)$}.
  \end{equation}
  Ademais, dizemos que um arco~$(u,v)$ é \textit{justo} se vale a
  \textit{igualdade} em~\eqref{eq:pot_prop}.  Suponha que um potencial~$p$
  satisfaz as seguintes duas propriedades:
  \begin{enumerate}
  \item[(\textit{a})]$p(s)=0$,
  \item[(\textit{b})]todo vértice~$x\in V(G)$ é acessível a partir de~$s$
    por um caminho que só contém arcos justos.
  \end{enumerate}
  Prove os seguintes fatos:
  \begin{enumerate}
  \item[(\textit{i})]Para todo~$x\in V(G)$, vale que $p(x)\leq d_c(s,x)$.
    \observacao{Para este item, a única hipótese necessária sobre o
      potencial~$p$ é que~$p(s)\leq0$.}
  \item[(\textit{ii})]Para todo~$x\in V(G)$, vale que $d_c(s,x)\leq p(x)$.
    \sugestao{Seja~$(P_k)$ a seguinte asserção: \textsl{se~$x$ é acessível a
        partir de~$s$ através de um caminho com~$k$ arcos, todos eles justos,
        então~$d_c(s,x)\leq p(x)$}.  Prove que~$(P_k)$ vale para todo~$k$ por
      indução em~$k$.}
  \end{enumerate}
  Conclua que~$d_c(s,x)=p(x)$ para todo vértice~$x$ de~$G$.
  \datedue{12/6/2007} 
  
\item Considere a implementação do algoritmo de Dijkstra visto em
  sala (Programa~21.1): {\small
\begin{verbatim}
#define GRAPHpfs GRAPHspt
#define P (wt[v] + t->wt)
void GRAPHpfs(Graph G, int s, int st[], double wt[])
  { int v, w;  link t;
    PQinit(); priority = wt;
    for (v = 0; v < G->V; v++)
      { st[v] = -1; wt[v] = maxWT; PQinsert(v); }
    wt[s] = 0.0; PQdec(s);
    while (!PQempty())
      if (wt[v = PQdelmin()] != maxWT)
        for (t = G->adj[v]; t != NULL; t = t->next)
          if (P < wt[w = t->v]) 
            { wt[w] = P; PQdec(w); st[w] = v; }
  }
\end{verbatim}
  } Seja~$G$ o grafo de~$5$ vértices e~$10$ arcos com custos nos arcos dado
  por {\small
\begin{verbatim}
0: 1(5) 3(10)
1: 2(2) 3(3) 4(9)
2: 0(7) 4(6)
3: 1(2) 4(1)
4: 2(4)
\end{verbatim}
  } Na notação acima, por exemplo, \verb|0: 1(5)| significa que há um arco
  de~\verb|0| para~\verb|1| de custo~\verb|5|.  
  \begin{enumerate}
  \item[(\textit{i})]Execute o Programa~21.1 no grafo~$G$ dado acima,
    com~$s=0$, ilustrando a evolução do algoritmo através de diagramas
    convenientes (uns~6 diagramas bastam).
  \item[(\textit{ii})]Determine um potencial~$p\:V(G)\to\RR$ para certificar
    que você encontrou as distâncias de~$0$ a todos os outros vértices em~$G$
    em~(\textit{i}) acima corretamente (veja a Questão~\ref{q:pot}).  Você
    deve dizer explicitamente por que sua função~$p$ é um potencial e por que
    ela de fato certifica as distâncias encontradas.
  \item[(\textit{iii})]Descreva um algoritmo de complexidade~$O(n+m)$ que
    poderia ser executado após o Programa~21.1 para verificar que de fato as
    distâncias a partir de~$s$ foram determinadas corretamente.  Por
    simplicidade, suponha que todos os vértices de~$G$ são acessíveis a partir
    de~$s$.  (Como você pode se livrar dessa hipótese?)
  \end{enumerate}
  \datedue{12/6/2007} 
  
\item Simule o método de Ford--Fulkerson na rede a seguir:
  {\small
\begin{verbatim}
0: 1(2) 2(3)
1: 3(3) 4(1)
2: 3(1) 4(1)
3: 5(2)
4: 5(3)
\end{verbatim}
  } Na notação acima, por exemplo, \verb|0: 1(2)| significa que há um arco
  de~\verb|0| para~\verb|1| com capacidade~\verb|2|.  Mostre a evolução do
  fluxo desde o fluxo nulo até o fluxo máximo.  Exiba um corte mínimo que
  certifica que seu fluxo final é de fato um fluxo máximo.
  \datedue{15/6/2007}
  
\item Escreva um programa para encontrar emparelhamentos de cardinalidade
  máxima em grafos bipartidos.  O seu programa \textit{deve ser baseado na
  redução deste problema ao problema do fluxo máximo}.  Seu programa deve
  receber como entrada os grafos gerados pelos programas \verb|g_random| e
  \verb|g_livros_simples| (note que estes programas admitem a opção
  \verb|-b|).  \datedue{22/6/2007}
  
\item\label{q:perfect_M} Use o programa \verb|g_random| para gerar grafos
  bipartidos aleatórios $G(n,n;m)$ com~$n$ vértices em cada classe da
  bipartição e~$m$ arestas e estude para quais valores de~$m=m(n)$ é provável
  que tal grafo tenha um \textit{emparelhamento perfeito} (considere valores
  grandes de~$n$) \datedue{22/6/2007}
  
\item Novamente usando o programa \verb|g_random|, estude o tamanho dos
  emparelhamentos de cardinalidade máxima em grafos aleatórios
  bipartidos~$G(n,n;m)$ para valores de~$m=m(n)$ inferiores ao valor que você
  estabeleceu no Exercício~\ref{q:perfect_M} (faça gráficos etc).  Estude os
  valores de~$m$ próximos de~$n$ com certo cuidado.  (Considere valores
  grandes de~$n$.) \datedue{22/6/2007}

\end{enumerate}

\end{document}

% Local Variables: 
% mode: latex
% eval: (Portug-mode)
% TeX-master: t
% End: 
