%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Arquivo LaTeX2e para                                               %
%                                                                    %
% Exercícios de MAC328 Algoritmos em Grafos                          %
% 1o. semestre de 2004                                               %
% Y. Kohayakawa                                                      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Tuesday 10 May 2005 09:56:50am BRT yoshi@erdos.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}

\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\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 2004}  
\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.)
  \datedue{9/3/2004}
  
\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}
  \datedue{9/3/2004}

\item{}[Desafio] Desenvolva um sistema computacional para determinar ou
  estimar~$g_n$ para valores grandes de~$n$. \datedue{em aberto}
  
\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}
  \datedue{12/3/2004}

\item Determine o vertebrado correspondente à função
  \begin{equation}
    \label{eq:uma_f}
    f=\(\begin{matrix}
      0\ 1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ a\ b\ c\ d\ e\ f\\
      0\ b\ f\ e\ c\ 3\ d\ 4\ 8\ 4\ 7\ 4\ 2\ e\ e\ 9
    \end{matrix}\)
  \end{equation}
  \datedue{16/3/2004}
  
\item Prove que todo grafo~$G$ com~$6$ vértices contém um clique com~$3$
  vértices ou um conjunto independente com~$3$ vértices; isto é,
  $\omega(G)\geq3$ ou~$\alpha(G)\geq3$.  Mostre que esta asserção é falsa para
  grafos com~$5$ vértices; isto é, existem grafos~$H$ com~$5$ vértices para os
  quais temos~$\omega(H)<3$ e~$\alpha(H)<3$.  \datedue{19/3/2004}
  
\item Estude as implementações para o tipo abstrato de dados \texttt{Graph}
  dadas nos programas~17.3 e~17.6.  Implemente a função \texttt{GRAPHremoveE}
  para a implementação com listas ligadas. \datedue{23/03/2004}

\item Para cada inteiro~$n>0$, seja~$P_n$ a probabilidade de o grafo aleatório
  com~$n$ vértices e~$m$ arestas ser conexo, onde
  \begin{equation}
    \label{eq:conn_thresh}
    m=\llfloor{1\over2}n\log n\rrfloor,
  \end{equation}
  onde escrevemos~$\log n$ para~$\log_en$.  (Aqui, consideramos todos
  os~${{n\choose2}\choose m}$ grafos $n$~vértices e $m$~arestas
  equiprováveis.)  Estime~$P_n$ para~$n$ grande através de experimentos
  computacionais.  \observacao{Sabe-se que~$\lim_{n\to\infty}P_n$ existe.
    Neste exercício, queremos estimar este limite.}  \datedue{26/3/2004 (O
    Panda estará de pé em breve para você entregar sua solução, que deve
    consistir de seu(s) programa(s) e um pequeno relatório com suas
    conclusões.)}
  
\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~$E(G)\setminus E(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$.)  \datedue{30/3/2004}
  
\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{2/4/2004}
  
\item Escreva um programa que, dado um grafo~$G$ como entrada, determina os
  componentes conexos de~$G$, os vértices de corte de~$G$, e os blocos de~$G$.
  Para descrever os componentes e os blocos de~$G$, o seu programa pode
  simplesmente imprimir o conjunto de vértices presentes nestes componentes e
  blocos.  O seu programa deve ter complexidade de tempo~$O(n+m)$, onde, como
  de usual, $n$~é o número de vértices em~$G$ e~$m$ é o número de arestas
  em~$G$.  Experimente executar \textit{o seu programa} nestes grafos:
  \href{http://www.ime.usp.br/~yoshi/2004i/mac328/Exercicios/ex11}{g1.gr},
  \href{http://www.ime.usp.br/~yoshi/2004i/mac328/Exercicios/ex11}{g2.gr},
  \href{http://www.ime.usp.br/~yoshi/2004i/mac328/Exercicios/ex11}{g3.gr}, e
  nos grafos \verb|book("anna",10,0,15,20,1,1,0)| e
  \verb|book("homer",561,0,1,24,1,1,0)| do Stanford GraphBase.  (Note que os
  grafos
  \href{http://www.ime.usp.br/~yoshi/2004i/mac328/Exercicios/ex11}{g2.gr} e
  \href{http://www.ime.usp.br/~yoshi/2004i/mac328/Exercicios/ex11}{g3.gr}
  são um tanto grandes.)
  \textbf{[Adiado por 3 dias!  \datedue{16/4/2004}]}
  
\item Familiarize-se com a plataforma \textsl{Stanford GraphBase} de Knuth.
  Para tanto, leia, pelo menos em algum detalhe, os Capítulos~1 a~4 do livro
  \href{http://www-cs-staff.stanford.edu/~knuth/sgb.html}{\textsl{Stanford
      GraphBase}}.  Uma ótima fonte local é uma
  \href{http://www.ime.usp.br/~coelho/grafos/}{página de uma edição de mac328}
  mantida pelo \href{http://www.ime.usp.br/~coelho/}{professor Coelho}.
  Finalmente, você deve entregar o seguinte: escreva um programa baseado no
  \texttt{queen.w} que gera \textit{três} grafos interessantes.  Você deve
  descrever os seus grafos em um pequeno texto, explicando a razão de sua
  escolha.  Seu programa deve imprimir uma descrição de seus grafos,
  possivelmente salientando as suas características que você achou
  interessantes.  (Entregue pelo Panda.) \datedue{20/4/2004}
  
\item Neste exercício, trataremos de árvores aleatórias.  O objetivo é
  determinar experimentalmente a \textit{altura esperada} de certas árvores
  aleatórias.  Você deve executar seus experimentos para valores de~$n$
  razoavelmente grandes, onde~$n$ é o número de vértices nas árvores
  aleatórias em questão.
  \begin{enumerate}
  \item Seja~$\cT(n)$ a família das árvores sobre o conjunto de
    vértices~$[n]=\{1,\dots,n\}$.  Considere~$\cT(n)$ como um espaço de
    probabilidade, atribuindo para todo elemento de~$T\in\cT(n)$ a mesma
    probabilidade.  Considere o vértice~$1$ como raiz de todos
    os~$T\in\cT(n)$; note que, fazendo isso, podemos definir a
    \textit{altura}~$h(T)$ de~$T$ em relação à raiz~$1$.  Estime
    experimentalmente o valor esperado de~$h(T)$.  \sugestao{Para gerar
      um~$T$, use a prova de Joyal para a fórmula de Cayley.}  \textbf{[A
      entrega deste item fica adiada para o dia 30/4/2004]}
    
  \item Consideremos agora o grafo completo~$K_n$ sobre o conjunto de
    vértices~$[n]$.  Podemos gerar uma árvore aleatória com raiz~$1$
    sobre~$[n]$ executando uma busca aleatória em~$K_n$ a partir de~$1$
    (considere a busca aleatória discutida em sala).  Seja~$R_n$ uma tal
    árvore aleatória.  Estime experimentalmente o valor esperado de~$h(R_n)$.
    \textbf{Use a seguinte versão do Programa 18.10}:{\small
\begin{verbatim}

void rfs(Graph G, Edge e)
  { link t; int v, w;
    RQput(e); 
    while (!RQempty())
      if (pre[(e = RQget()).w] == -1)
        { link t;
          pre[e.w] = cnt++; st[e.w] = e.v;
          for (t = G->adj[e.w]; t != NULL; t = t->next)
            if (pre[v = t->v] == -1)
                RQput(EDGE(e.w, v)); 
        }
  }

\end{verbatim}}
    O programa acima é como o Programa 18.8 do Sedgewick (apenas troquei os
    \verb|QUEUE| por \verb|RQ| (\textit{random queue})).  Note que,
    basicamente, o Programa 18.9 está para o Programa 18.8, como o Programa
    18.10 está para o programa acima.
  \end{enumerate}

  \datedue{23/4/2004}
  
\item 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$.  Prove que existe uma
  orientação fortemente conexa de~$G$ se e só se~$G$ é conexo e não tem
  arestas de corte.  \datedue{27/4/2004}
  
\item Seja~$G=(V,E)$ um grafo dirigido, onde~$V=\{v_1,\dots,v_n\}$, e
  seja~$A=(a_{ij})$ a matriz de adjacência para~$G$ com~$a_{ij}=1$
  se~$(i,j)\in E$ e~$a_{ij}=0$ se~$(i,j)\notin E$.  (Apenas para maior
  clareza, suponha que~$G$ não tem laços, de forma que~$a_{ii}=0$ para
  todo~$i$.)  O que é a entrada~$ij$ da matriz~$A^2$?  (Aqui~$A^2$ é o
  quadrado usual da matriz~$A$.)  Em geral, o que é a entrada~$ij$ da
  $k$-ésima potência~$A^k$ de~$A$ ($k\geq0$)?
  \datedue{11/5/2004}

\item Escreva um algoritmo que, dado um DAG~$D$, determina o comprimento
  máximo de um caminho dirigido em~$D$ (basta entregar um pseudocódigo em
  papel).  \datedue{18/05/2004}

\item 
  \begin{enumerate}
  \item[(\textit{i})]Descreva o que ocorre quando executamos o algoritmo de
    Kosaraju em um DAG.
  \item[(\textit{ii})]Descreva o que ocorre quando executamos o algoritmo de
    Tarjan em um DAG.
  \end{enumerate}\datedue{21/5/2004}
  
\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 é o 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{25/5/2004}
  
\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{exercício recomendado, sem data de entrega}
  
\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{exercício recomendado, sem data de entrega}
  
\item Suponha que os custos~$c(e)$ ($e\in E(G)$) das arestas de um grafo~$G$
  são todos inteiros, com~$1\leq c(e)\leq n=|V(G)|$.  O quão rápido podemos
  encontrar uma árvore geradora mínima de~$(G,c)$?  \datedue{1/6/2004}
  
\item Estude as implementações do algoritmo de Kruskal e do algoritmo de
  (Jarník--)Prim (com heaps binários) em
  \href{http://www.ime.usp.br/~yoshi/2004i/mac328/Slides/2004.05.28/miles_span.pdf}{\texttt{miles\_span}},
  do Stanford GraphBase.  As estatísticas relatadas na Seção~71 daquele
  programa foram compiladas com uma máquina Sun Sparc 2 (bastante antiga!).
  Compile estatísticas para máquinas Intel (ou Sun) mais modernas.  Faça uma
  pequena discussão com base nos dados que você obtiver.  Se você quiser
  experimentar estas implementações em mais instâncias, vá em frente!
  \datedue{4/5/2004}

\end{enumerate}  
 
\end{document}

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