\input cwebmac
% coelho FEV 2003
\documentclass[language=brazil,structure=flat]{cweb}

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

\setlength{\topmargin}{-0.5in}
\setlength{\textheight}{9in}
\setlength{\oddsidemargin}{-.125in}
\setlength{\evensidemargin}{-.125in}
\setlength{\textwidth}{6.75in}

% Macros do LaTeX
\newcommand{\cweb}{\texttt{CWEB}}
\newcommand{\sgb}{\texttt{SGB}}
\newcommand{\defi}[1]{\textit{#1}}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\ceil}[1]{\lceil #1 \rceil}
\newcommand{\seq}[1]{\langle #1 \rangle}
\newcommand{\opcao}[1]{$\langle$#1$\rangle$}
\newcommand{\caminho}[1]{$\langle$#1$\rangle$}
\newcommand{\conjunto}[1]{\{\,#1\,\}}
\newcommand{\conj}[1]{\{#1\}}
\newcommand{\NP}{\textup{NP}}
\newcommand{\PP}{\textup{P}}

% \pch  problema do circuito hamiltoniano
\newcommand{\pch}{\textsc{PCH}}

\newcommand{\gbb}{\textsc{gb\_basic}}
\newcommand{\gbr}{\textsc{gb\_rand}}
\newcommand{\gbs}{\textsc{gb\_save}}

\begin{document}




\title{{\small Exemplo de uso do Stanford GraphBase com \texttt{CWEB}-\LaTeX}\\
Grafos Hamiltonianos}
\author{coelho}

\maketitle

\tableofcontents


\N{2}{1}Introdução. Esta é uma demonstração do \sgb\ com \cweb-\LaTeX.
Antes de descrever o problema e o programa para resolvê-lo é conveniente
introduzir alguma terminologia.

%%%%% Passeio
Um \defi{passeio} num grafo \PB{\|g} é qualquer seqüência da forma
\begin{eqnarray}
\label{passeio}
\seq{v_{0}, a_{1}, v_{1}, \ldots, a_{k}, v_{k}}
\end{eqnarray}
onde $v_{0}, \ldots, v_{k}$ são vértices, $a_{1}, \ldots, a_{k}$
são arcos e, para cada $i$, $a_{i}$ é o arco $v_{i-1}v_{i}$.
%%%%% início e fim de passeios
O vértice $v_{0}$ é o \defi{início} do passeio e o $v_{k}$ é seu
\defi{término}.
%%%%% caminho

%%%% caminho e circuito hamiltoniano
Um \defi{caminho} é um passeio
sem vértices repetidos. Já um \defi{circuito} é um caminho onde o início
e término coincidem.
Um caminho ou circuito que contém todos os vértices do grafo é dito
\defi{hamiltoniano}.
O \defi{problema do circuito hamiltoniano} (\textit{Hamiltonian circuit
problem}), denotado pela sigla \pch\ é o seguinte:

\begin{quote}
\textbf{Problema} \pch\PB{(\|g)}: %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Dado um grafo \PB{\|g}, encontrar um circuito hamiltoniano.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{quote}

Um grafo que possui um circuito hamiltoniano é dito \defi{hamiltoniano}.
O \pch\ é um problema computacionalmente difícil.  Tecnicamente falando
o \pch\ é \NP-difícil. Isto significa que todo algoritmo conhecido só
consegue resolver o problema para grafos `grandes' após consumir uma
quantidade de tempo indecente.  \texttt{MAC0338} Análise de Algoritmos é
uma disciplina que esclarece o significado desse termo de uma maneira
mais precisa.




\fi

\N{2}{2}O que o programa faz.  Este programa recebe um grafo, através de um
arquivo no formato do \sgb\ ou de uma opção para gerá-lo, e decide se o grafo
dado é ou não hamiltomiano.

Se o grafo é hamiltoniano o programa devolve, para
a saída padrão, uma seqüência dos vértices do grafo que formam um circuito
hamiltoniano. Já, se o grafo não é hamiltoniano, o programa responde apenas
que lamenta \ldots Seria bacana se tivéssemos um programa que
devolvesse algum objeto que fosse uma prova cabal de que o grafo não é
hamiltoniano. Mais ainda, seria ótimo que o programa pudesse verificar
rapidamente essas provas ou certificados. Uma característica dos problemas
\NP-difíceis é que estes admitem um certificado `sucinto' (ou seja, verificável
rapidamente) para a resposta \textsc{sim} (no caso, o grafo é hamiltoniano),
mas não se
conhece um certificado sucinto para a respotas \textsc{não} (no caso, o grafo
não é
hamiltoniano).


\fi

\N{2}{3}Como usar o programa.
Para usar o programa o
usuário deve, na linha de comando, escrever
\begin{quote}
\texttt{meu\_prompt> hamiltoniano \opcao{opções}}
\end{quote}
onde \texttt{\opcao{opções}} consiste de zero ou mais das seguintes
especificações em qualquer ordem
\begin{description}
\item[\texttt{-r}]  Usa a subrotina \PB{\\{random\_graph}} do módulo
\gbr\ do \sgb\ para gerar um grafo pseudo-aleatório com \PB{\|n}
vértice \PB{\|m} arcos ou arestas, usando um gerador de números
pseudo-aleatórios que depende de um semente (veja opção \texttt{-s}).

\item[\texttt{-c}] Usa a subrotina \PB{\\{circuit}} do módulo \gbb\ do
\sgb\ para gerar um circuito simétrico com \PB{\|n} vértices. Todo
circuito é hamiltoniano.

\item[\texttt{-e}] Usa a subrotina \PB{\\{empty}} do módulo \gbb\ do
\sgb\ para gerar um grafo com \PB{\|n} vértices e zero arcos.
O grafo sem arcos não é hamiltoniano.

\item[\texttt{-p}] Usa a subrotina \PB{\\{petersen}} do módulo \gbb\ do
\sgb\ para gerar o grafo de Petersen. O grafo de Petersen não é
hamiltoniano.

\item[\texttt{-t}] Usa a subrotina \PB{\\{transitive}} do módulo \gbb\ do
\sgb\ para gerar um torneio com \PB{\|n} vértices. Um torneio é um grafo
que tem um arco de \PB{\|u} a \PB{\|v} se \PB{$\|u<\|v$}. Torneios não são
hamiltonianos.

\item[\texttt{-k}] Usa a subrotina \PB{\\{complete}} do módulo \gbb\ do
\sgb\ para gerar um grafo simétrico completo com \PB{\|n} vértices. Num
grafo completo simétrico temos uma arco de \PB{\|u} a \PB{\|v} para cada para
\PB{\|u} e \PB{\|v} de vértices distintos. Todo grafo completo simétrico é
hamiltoniano.

\item[\texttt{-g\opcao{nome}}] Nenhum grafo será gerado. O grafo sobre
o qual o programa trabalhará será lido do arquivo  \opcao{nome}.

\item[\texttt{-s\opcao{número}}] Usa o número \PB{\|s} como semente do
gerardor de números pseudo-aleatórios, onde \PB{\|s} é o \opcao{número} dado.

\item[\texttt{-n\opcao{número}}] O grafo gerado terá \PB{\|n} vértices,
onde \PB{\|n} é o \opcao{número} dado.

\item[\texttt{-m\opcao{número}}] O grafo gerado terá \PB{\|m} arcos ou
arestas, onde \PB{\|m} é o \opcao{número} dado.

\item[\texttt{-h\opcao{número}}] Usa a heurística do vértice de grau de
saída mínimo.

\item[\texttt{-o\opcao{nome}}] O grafo de trabalho é salvo no arquivo
\opcao{nome}.
\end{description}
É evidente que só faz sentido usar apenas uma entre as opções \texttt{-r,
-c, -e, -p, -t, -k, -g}. Também não faz sentido usar a opção
\texttt{-g} junto com as opções \texttt{-n, -s} e \texttt{-m}. Só faz
sentido usar a opção \texttt{-m} junto com \texttt{-r}.

Como de hábito, caso o usuário escreva apenas
\begin{center}
\texttt{meu\_prompt> hamiltoniano}
\end{center}
o programa deve descrever o seu funcionamento.

\Y\B\4\X3:Função \PB{\\{mostre\_uso}}\X${}\E{}$\6
\&{void} \\{mostre\_uso}(\,)\1\1\2\2\6
${}\{{}$\1\6
${}\\{fprintf}(\\{stdout},{}$\6
\.{"Uso:\ \%s\ [-r|-c|-e|-}\)\.{p|-t|-k|-g<nome>]\ [-}\)\.{h]\ [-s<num>]\
[-n<num}\)\.{>]\ "}\.{"[-m<num>]\ [-o<nome>}\)\.{]\\n"}\6
\.{"\ \ \ \ \ -r\ \ grafo\ pseu}\)\.{do-aleatorio\ com\ n\ v}\)\.{ertices\ e\ m%
\ arestas\\}\)\.{n"}\6
\.{"\ \ \ \ \ -c\ \ circuito\ c}\)\.{om\ n\ vertices\\n"}\6
\.{"\ \ \ \ \ -e\ \ grafo\ com\ }\)\.{n\ vertices\ e\ zero\ ar}\)\.{cos\\n"}\6
\.{"\ \ \ \ \ -p\ \ grafo\ de\ P}\)\.{etersen\\n"}\6
\.{"\ \ \ \ \ -t\ \ torneio\ co}\)\.{m\ n\ vertices\\n"}\6
\.{"\ \ \ \ \ -k\ \ grafo\ sime}\)\.{trico\ completo\ com\ n}\)\.{\ vertices%
\\n"}\6
\.{"\ \ \ \ \ -g<nome>\ traba}\)\.{lha\ com\ o\ grafo\ do\ a}\)\.{rquivo\
<nome>\\n"}\6
\.{"\ \ \ \ \ -s<num>\ \ para\ }\)\.{o\ gerar\ numeros\ pseu}\)\.{do-aleatorios%
\\n"}\6
\.{"\ \ \ \ \ -n<num>\ numero}\)\.{\ de\ vertices\\n"}\6
\.{"\ \ \ \ \ -m<num>\ numero}\)\.{\ de\ arcos/arestas\\n"}\6
\.{"\ \ \ \ \ -o<nome>\ grafo}\)\.{\ de\ trabalho\ sera\ sa}\)\.{lvo\ no\
arquivo\ <nome}\)\.{>\\n"}\6
${},\39\\{nome\_programa});{}$\6
\\{exit}(\T{0});\6
\4${}\}{}$\2\par
\U7.\fi

\N{2}{4}Estratégia de solução.
Para resolver certos problemas é necessário enumerar todas as
configurações (ou objetos) de um certo tipo. O número de configurações é
tipicamente muito grande, e portanto os algoritmos enumerativos
usualmente consomem uma quantidade absurda de tempo. Este programa
é uma implementação de uma algoritmo enumerativo do tipo
\textit{backtracking}. Este tipo de algoritmo também é conhecido como
\defi{tipo força-bruta}, pois examina sistematicamente todos os candidados a
solução. Você já estudou algoritmos enumerativos em
\texttt{MAC0122}. Veja, por exemplo, o \defi{problema das $n$ rainhas}

\begin{center}
\texttt{http://www.ime.usp.br/%
\~{}coelho/mac122/conteudo/backtracking/nrainhas.c}
\end{center}

\noindent
e do \defi{problema do escalonamento}

\begin{center}
\texttt{http://www.ime.usp.br/\~{}coelho/mac122/eps/ep4/}~.
\end{center}

Algoritmos enumerativos são muitas vezes escritos de maneira
recursiva. Este programa, só por nos diversão, apresenta uma implementação
iterativa.



\fi

\N{2}{5}Estrutura geral do programa.
Abaixo encontra-se o `layout' do programa, como é visto pelo
compilador \texttt{C}.


\Y\B\8\#\&{include} \.{<stdio.h>}\6
\8\#\&{include} \.{<string.h>}\6
\8\#\&{include} \.{"gb\_graph.h"}\C{ estruturas de dados padrão do \sgb\ }\6
\8\#\&{include} \.{"gb\_save.h"}\C{ rotinas para ler e salvar um grafo }\6
\8\#\&{include} \.{"gb\_basic.h"}\C{ rotinas para gerar alguns grafos básicos }%
\6
\8\#\&{include} \.{"gb\_rand.h"}\C{ produz um grafo pseudo-aleatório }\6
\ATH\7
\X6:Variáveis globais\X\6
\X7:Declaração de funções\X\7
\&{int} ${}\\{main}(\\{argc},\39\\{argv}){}$\1\1\6
\&{int} \\{argc};\C{ o número de argumentos na linha de comando }\6
\&{char} ${}{*}\\{argv}[\,]{}$;\C{ o vetor de strings contendo os argumentos }%
\2\2\6
${}\{{}$\1\6
\X8:Variáveis locais do \PB{\\{main}}\X;\6
\X9:Examine as opções na linha de comando\X;\6
\X11:Crie o grafo \PB{\|g} dado\X;\6
\X18:Verifique se \PB{\|g} é hamiltoniano\X;\6
\&{if} (\\{salva\_arquivo})\1\5
\X24:Salve o grafo \PB{\|g} no arquivo \PB{\\{salva\_arquivo}}\X;\2\6
\\{gb\_recycle}(\|g);\C{ devolve a memória usada por \PB{\|g} }\6
\&{return} \T{0};\C{ termino normal }\6
\4${}\}{}$\2\par
\fi

\M{6} Gosto que \PB{\\{nome\_programa}} e algumas outras variáveis sejam
globais.
Além disso, se o programa encontra algum problema, então um código de erro é
devolvido através de \PB{\\{exit}}.

\Y\B\4\X6:Variáveis globais\X${}\E{}$\6
\&{typedef} \&{enum} ${}\{{}$\1\6
${}\.{FALSE},\39\.{TRUE}{}$\2\6
${}\}{}$ \&{Boolean};\6
\&{char} ${}{*}\\{nome\_programa}\K\NULL{}$;\C{ nome do programa }\6
\&{enum} ${}\{{}$\C{ código de erros }\1\6
${}\\{opção\_invalida}\K{-}\T{1},{}$\6
\\{salva\_grafo\_erro}${}\K{-}\T{2},{}$\6
\\{putz\_programa\_errado}${}\K{-}{}$\T{3}\2\6
${}\}{}$;\par
\A13.
\U5.\fi

\M{7}A seguir está a lista de funções que fazem parte do programa. Hummm, neste
programa só temos uma função, excluindo-se o \PB{\\{main}}.
\Y\B\4\X7:Declaração de funções\X${}\E{}$\6
\X3:Função \PB{\\{mostre\_uso}}\X\par
\U5.\fi

\N{2}{8}Tratamento das opções.
Entre as váriaveis local do \PB{\\{main}} teremos o grafo \PB{\|g} sobre o qual
trabalharemos. Outras variáveis são relativas a opções do programa.
Estas váriáveis são inicializadas com seu valores default. Assim
\begin{center}
\texttt{meu\_prompt> hamiltoniano -n30}
\end{center}
tem o mesmo efeito que
\begin{center}
\texttt{meu\_prompt> hamiltoniano -r -n30 -m100}
\end{center}


\Y\B\4\X8:Variáveis locais do \PB{\\{main}}\X${}\E{}$\6
\&{unsigned} \&{long} \|n${}\K\T{20}{}$;\C{ número de vértices }\6
\&{unsigned} \&{long} \|m${}\K\T{100}{}$;\C{ número de arcos    }\6
\&{long} \\{directed}${}\K\T{1}{}$;\C{ o grafo gerado não precisa ser simétrico
}\6
\&{long} \\{seed}${}\K\T{0}{}$;\C{ semente para o gerador pseudo-aleatório }\6
\&{Boolean} \\{aleatório}${}\K\.{FALSE}{}$;\C{ gerar um grafo pseudo-aleatório
}\6
\&{Boolean} \\{circuito}${}\K\.{FALSE}{}$;\C{ gerar um circuito  }\6
\&{Boolean} \\{vazio}${}\K\.{FALSE}{}$;\C{ gerar um grafo sem arcos }\6
\&{Boolean} \\{petersen}${}\K\.{FALSE}{}$;\C{ gerar o grafo de Petersen }\6
\&{Boolean} \\{torneio}${}\K\.{FALSE}{}$;\C{ gerar um torneio }\6
\&{Boolean} \\{completo}${}\K\.{FALSE}{}$;\C{ gerar um grafo completo }\6
\&{Boolean} \\{heurística}${}\K\.{FALSE}{}$;\C{ heurística do grao de saída
mínimo }\6
\&{Boolean} \\{escolheu}${}\K\.{FALSE}{}$;\C{ indica se foi escolhido como
criar o grafo }\6
\&{char} ${}{*}\\{nome\_arquivo}\K\NULL{}$;\C{ nome do arquivo do grafo de
trabalho }\6
\&{char} ${}{*}\\{salva\_arquivo}\K\NULL{}$;\C{ para salvar o grafo de trabalho
}\par
\As10, 14\ETs22.
\U5.\fi

\M{9}As opções podem ser fornecidas em qualquer ordem. Se o grafo é dado
por mais de uma maneira (opções \texttt{-r, -c, -e, -p, -t, -k} ou
\texttt{-g}), o programa pára com uma mensagem de erro. A variável
\PB{\\{escolheu}} é usada para detectar este tipo de inconsistência. Está é a
única inconsistência verificada na linha de comando. Assim, por exemplo,
o programa não reclama se for chamado com as opções \texttt{-c -n10 -m1000};
note que todo circuito com 10 vértices tem 20 arcos.


\Y\B\4\X9:Examine as opções na linha de comando\X${}\E{}$\6
$\\{nome\_programa}\K\\{argv}[\T{0}];{}$\6
\&{if} ${}(\\{argc}\E\T{1}){}$\1\5
\\{mostre\_uso}(\,);\2\6
\&{while} ${}(\MM\\{argc}){}$\5
${}\{{}$\1\6
\&{if} ${}(\\{strcmp}(\\{argv}[\\{argc}],\39\.{"-r"})\E\T{0}\W\R%
\\{escolheu}){}$\1\5
${}\\{escolheu}\K\\{aleatório}\K\.{TRUE};{}$\2\6
\&{else} \&{if} ${}(\\{strcmp}(\\{argv}[\\{argc}],\39\.{"-c"})\E\T{0}\W\R%
\\{escolheu}){}$\1\5
${}\\{escolheu}\K\\{circuito}\K\.{TRUE};{}$\2\6
\&{else} \&{if} ${}(\\{strcmp}(\\{argv}[\\{argc}],\39\.{"-e"})\E\T{0}\W\R%
\\{escolheu}){}$\1\5
${}\\{escolheu}\K\\{vazio}\K\.{TRUE};{}$\2\6
\&{else} \&{if} ${}(\\{strcmp}(\\{argv}[\\{argc}],\39\.{"-p"})\E\T{0}\W\R%
\\{escolheu}){}$\1\5
${}\\{escolheu}\K\\{petersen}\K\.{TRUE};{}$\2\6
\&{else} \&{if} ${}(\\{strcmp}(\\{argv}[\\{argc}],\39\.{"-t"})\E\T{0}\W\R%
\\{escolheu}){}$\1\5
${}\\{escolheu}\K\\{torneio}\K\.{TRUE};{}$\2\6
\&{else} \&{if} ${}(\\{strcmp}(\\{argv}[\\{argc}],\39\.{"-k"})\E\T{0}\W\R%
\\{escolheu}){}$\1\5
${}\\{escolheu}\K\\{completo}\K\.{TRUE};{}$\2\6
\&{else} \&{if} ${}(\\{strncmp}(\\{argv}[\\{argc}],\39\.{"-g"},\39\T{2})\E\T{0}%
\W\R\\{escolheu}){}$\5
${}\{{}$\1\6
${}\\{escolheu}\K\.{TRUE};{}$\6
${}\\{nome\_arquivo}\K\\{argv}[\\{argc}]+\T{2};{}$\6
\4${}\}{}$\2\6
\&{else} \&{if} ${}(\\{strcmp}(\\{argv}[\\{argc}],\39\.{"-h"})\E\T{0}){}$\1\5
${}\\{heurística}\K\.{TRUE};{}$\2\6
\&{else} \&{if} ${}(\\{sscanf}(\\{argv}[\\{argc}],\39\.{"-n\%lu"},\39{\AND}\|n)%
\E\T{1}){}$\1\5
;\2\6
\&{else} \&{if} ${}(\\{sscanf}(\\{argv}[\\{argc}],\39\.{"-m\%lu"},\39{\AND}\|m)%
\E\T{1}){}$\1\5
;\2\6
\&{else} \&{if} ${}(\\{sscanf}(\\{argv}[\\{argc}],\39\.{"-s\%ld"},\39{\AND}%
\\{seed})\E\T{1}){}$\1\5
;\2\6
\&{else} \&{if} ${}(\\{strncmp}(\\{argv}[\\{argc}],\39\.{"-o"},\39\T{2})\E%
\T{0}){}$\1\5
${}\\{salva\_arquivo}\K\\{argv}[\\{argc}]+\T{2};{}$\2\6
\&{else}\5
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"Uso:\ \%s\ [-r|-c|-e|-}\)\.{p|-t|-k|-g<nome>]]%
\ [}\)\.{-h]\ [-s<semente>]\ [-}\)\.{n<num>]\ [-m<num>]\ [-}\)\.{o<nome>]\\n"},%
\39\\{nome\_programa});{}$\6
\\{exit}(\\{opção\_invalida});\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\&{if} ${}(\R\\{escolheu}){}$\1\5
${}\\{aleatório}\K\.{TRUE}{}$;\C{ opção default }\2\par
\U5.\fi

\N{2}{10}Criação do grafo. O trabalho desta parte do programa é construir ou
reconstruir o grafo \PB{\|g} sobre o qual trabalharemos. O grafo será
construído se algumas das opções de geração automática do grafo foi
usada. Caso a opção \texttt{-g\opcao{nome}} tenha sido usada o grafo
será recontruído a partir do conteúdo de \PB{\\{nome\_arquivo}}. A criação
do grafo depende da

\Y\B\4\X8:Variáveis locais do \PB{\\{main}}\X${}\mathrel+\E{}$\6
\&{Graph} ${}{*}\|g\K\NULL{}$;\C{ grafo de trabalho }\par
\fi

\M{11}Se uma rotina de criação do grafo encontrar um problema, ela devolve
\PB{$\NULL$} (ou seja, \texttt{NULL}), depois de colocar um número de código
que
identifica o erro na variável externa \PB{\\{panic\_code}}.  Se não ocorrer
problemas a rotina devolve o endereço do grafo criado (\PB{\&{Graph} ${}{*}$}).


\Y\B\4\X11:Crie o grafo \PB{\|g} dado\X${}\E{}$\6
\&{if} (\\{aleatório})\1\5
${}\|g\K\\{random\_graph}(\|n,\39\|m,\39\T{0},\39\T{0},\39\\{directed},\39%
\NULL,\39\NULL,\39\T{1},\39\T{1},\39\\{seed});{}$\2\6
\&{else} \&{if} (\\{circuito})\1\5
${}\|g\K\\{circuit}(\|n);{}$\2\6
\&{else} \&{if} (\\{vazio})\1\5
${}\|g\K\\{empty}(\|n);{}$\2\6
\&{else} \&{if} (\\{petersen})\1\5
${}\|g\K\\{petersen}(\,);{}$\2\6
\&{else} \&{if} (\\{torneio})\1\5
${}\|g\K\\{transitive}(\|n);{}$\2\6
\&{else} \&{if} (\\{completo})\1\5
${}\|g\K\\{complete}(\|n);{}$\2\6
\&{else} \&{if} (\\{nome\_arquivo})\1\5
${}\|g\K\\{restore\_graph}(\\{nome\_arquivo}){}$;\2\6
\&{if} ${}(\|g\E\NULL{}$)\6
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"\%s:\ grafo\ nao\ pode\ }\)\.{ser\ criado\
(codigo\ d}\)\.{o\ erro:\ \%ld)\\n"},\39\\{nome\_programa},\39\\{panic%
\_code});{}$\6
\&{return} ${}{-}\T{1}{}$;\C{ Opsss ... }\6
\4${}\}{}$\2\6
${}\\{fprintf}(\\{stdout},\39\.{"grafo:\ \%s.\\nnumero\ }\)\.{de\ vertices:\ %
\%ld.\\nn}\)\.{umero\ de\ arcos:\ \%ld.}\)\.{\\n"},\39\|g\MG\\{id},\39\|g\MG%
\|n,\39\|g\MG\|m){}$;\par
\A17.
\U5.\fi

\N{2}{12}Algoritmo enumerativo. Finalmente chegamos no coração do programa.
Durante a execução do programa cada vértice do grafo está no estado `ativo' ou
`inativo'. Os vértices ativos fazem parte de um caminho na iteração corrente
de um vértice \PB{\|s} a um vértice \PB{\|u} e
os vértices inativos são os que não estão no caminho. Grosseiramente falando,
a missão da iteração é estender esse caminho corrente a um caminho
hamiltoniano de \PB{\|s} a um certo vértice \PB{\|t} ou se arrepender-se
(\textit{backtrack}) e voltar nas suas `próprias pegadas'.

A estruturas de dados que representa o estado corrente do algoritmo é
implementada usando três `utility fields' em cada vértice: \PB{\\{estado}}, %
\PB{\\{pred}}
(predecessor) e \PB{\\{current\_arc}}.  Consideraremos cada um deles
separadamente.


\fi

\M{13}O \PB{\\{estado}} de um vértice é um inteiro. Ele é zero (ou, \PB{%
\.{ATIVO}}) quando o
vértice está inativo. Assim que o vértice passa a ser a ponta final \PB{\|u} do
caminho corrente ele se torna ativo e o valor de seu \PB{\\{estado}} passa a
ser um
(ou \PB{\.{ATIVO}}).  Ao final do programa, caso um caminho hamiltoniano de %
\PB{\|s} a \PB{\|t}
tenha sido encontrado, o programa certifica-se do seu achado e durante este
processo transforma o estado dos vértices de \PB{\.{ATIVO}} para \PB{%
\.{MARCADO}}.

\Y\B\4\D$\\{estado}$ \5
$\|z.{}$\|I\C{ o \PB{\\{estado}} de um vértice é armazenado no utility field %
\PB{\|z} }\par
\Y\B\4\X6:Variáveis globais\X${}\mathrel+\E{}$\6
\&{enum} ${}\{{}$\1\6
${}\.{INATIVO}\K\T{0},\39\.{ATIVO}\K\T{1},\39\.{MARCADO}\K\T{2}{}$\2\6
${}\}{}$;\par
\fi

\M{14}Os vértices ativos formam um caminho de um vértice inicial \PB{\|s} a um
vértice
\PB{\|u}.  Todo vértice ativo tem um predecessor no caminho, indicado pelo
campo
\PB{\\{pred}}. Este predecessor é outro vértice
ativo; a única excessão é a ponta inicial \PB{\|s} do caminho que tem como
predecessor o vértice especial \PB{\|t}, que não é ativo. Assim,
um arco de \PB{\|v} a \PB{\|w} no caminho é
representado na estrutura por \PB{$\|w\MG\\{pred}\E\|v$}. O campo \PB{\\{pred}}
permite que o
programa faça backtracking no caminho.

Assim, no fundo, o programa mantém uma representação `reversa' do caminho
corrente de \PB{\|s} a \PB{\|u},  definida pelos campos \PB{\\{pred}} de cada
vértice ativo, ou seja, o caminho corrente é
\begin{center}
\caminho{\PB{$\|s\K\|u\MG\\{pred}$ $\MG$}\ldots\PB{$\MG$ \\{pred} $,$}\ldots%
\PB{$,$ $\|u\MG\\{pred}\MG\\{pred}\MG\\{pred},\|u\MG\\{pred}\MG\\{pred},\|u\MG%
\\{pred},\|u$}}.
\end{center}

\Y\B\4\D$\\{pred}$ \5
$\|y.{}$\|V\C{ o predecessor (\PB{\\{pred}}) de um vértice e armazenado no
utility field \PB{\|y}}\par
\Y\B\4\X8:Variáveis locais do \PB{\\{main}}\X${}\mathrel+\E{}$\6
\&{Vertex} ${}{*}\|s{}$;\C{ vértice que é ponta inicial do caminho corrente }\6
\&{Vertex} ${}{*}\|u{}$;\C{ vértice que é ponta final do caminho corrente }\6
\&{Vertex} ${}{*}\|t{}$;\C{ vértice destino do caminho corrente }\par
\fi

\M{15}Todos os arcos do grafo são explorados sistematicamente, a partir do
vértice
origem \PB{\|s}, como numa busca em profundidade. Suponha que no caminho
corrente
existe um arco de \PB{\|v} a \PB{\|w}. Logo, \PB{$\|w\MG\\{pred}\K\|v$}. O arco
de \PB{\|v} a \PB{\|w} também é
representado diretamente na estrutura pelo campo \PB{\\{current\_arc}} do
vértice \PB{\|v}. Desta forma,  tem-se que \PB{$\|v\MG\\{current\_arc}\MG%
\\{tip}\K\|w$}.
Este tipo de apontador é bem conhecido e útil (veja
o livro \textit{Network Flows: Theory, Algorithms, and Applications},
R.K.~Ahuja, Th.L.~Magnanti, J.B.~Orlin, Prentice Hall, 1993).
O caminho corrente é representado por
\begin{center}
\caminho{\PB{$\|s,\|s\MG\\{current\_arc}\MG\\{tip},\|s\MG\\{current\_arc}\MG%
\\{tip}\MG\\{current\_arc}\MG\\{tip}$ $,$}\ldots\PB{$,$ $\|s\MG\\{current\_arc}%
\MG\\{tip}$ $\MG$}\ldots\PB{$\MG$ $\\{current\_arc}\MG\\{tip},\|u$}}.
\end{center}

\Y\B\4\D$\\{current\_arc}$ \5
$\|x.{}$\|A\par
\fi

\M{16}Busca em profundidade explora um grafo sistematicamente, visitando
todos os vértices e verificando para onde estes vértices podem nos conduzir.
O vértice ativo que é ponta final do caminho corrente é \PB{\|u}.

Há duas possibilidade, o arco \PB{$\|u\MG\\{current\_arc}$} tenha ponta final
em um
vértice \PB{\|v} que é  ativo ou inativo.
Se o vértice \PB{\|v} é ativo, então \PB{\|v} já faz parte do caminho corrente
e
tentaremos estender o caminho através do arco sucessor de
\PB{$\|u\MG\\{current\_arc}$} na lista de adjacência de \PB{\|u}. Caso \PB{\|v}
seja inativo,
marcamos \PB{\|v} passa a ser a nova ponta final e do caminho corrente e
passamos
a examinar
os arcos com ponta inicial nele. Se chegarmos a um ponto em que todos os
arcos com ponta inicial em \PB{\|u} nos levam a vértices ativos, chegou a
hora de dar um passo atrás e fazer com que \PB{$\|u\MG\\{pred}$} volte a ser a
ponta final
do caminho.

Para tentar encontrar um circuito hamiltoniano no grafo \PB{\|g}
precederemos da seguinte maneira. O \defi{grau de saída} de um vértice é
o número de arcos que têm ponta inicial nele.
Inicialmente o programa escolhe um vértice `destino' \PB{\|t};
se a opção \texttt{-h} foi usada escolheremos como \PB{\|t} um vértice de \PB{%
\|g}
que tem grau de saída mínimo. Se
encontramos em \PB{\|g} um caminho hamiltoniano de \PB{\|s} a \PB{\|t}, então %
\PB{\|g} é
hamiltoniano.  De fato, a concatenação do caminho ao arco de \PB{\|t} a \PB{%
\|s} é um
circuito hamiltoniano.

A idéia básica do algoritmo enumerativo abaixo é a seguinte. Com \PB{\|t}
fixado tente, para cada arco da forma \PB{\\{ts}}, encontar um caminho
hamiltoniano de \PB{\|s} a \PB{\|t}. É evidente que se todas as buscas por um
tal
caminho falharem, então o grafo não é hamiltoniano.

\fi

\M{17}O campo \PB{\\{util\_types}} de um grafo contém um string de comprimento
14,
seguido do caractere nulo `\PB{\\T{0}}'. Os primeiros 6 caracteres do
\PB{\\{util\_type}} indicam o uso dos campos utilitários \PB{$\|u,\|v,\|w,\|x,%
\|y$} e \PB{\|z}
dos registros \PB{\&{Vertex}}. Os próximos dois caracteres dão o formato dos
campos utilitários \PB{\|a} e \PB{\|b} em \PB{\&{Arc}}. Finalmente, os seis
último caracteres
mostram o formato dos campos utilitários \PB{$\\{uu},\\{vv},\\{ww},\\{xx},%
\\{yy}$} e \PB{\\{zz}} em
\PB{\&{Graph}}.
Cada caractere deve ser um \texttt{I} (denotando um inteiro longo),
\texttt{S}  (representando o endereço de um string), \texttt{V}
(indicando o endereço de um \PB{\&{Vertex}}), \texttt{A} (denotando o endereço
de um \PB{\&{Arc}}), \texttt{G} (endereço de um \PB{\&{Graph}}), ou \texttt{Z}
(significando que o campo não está em uso).

\Y\B\4\X11:Crie o grafo \PB{\|g} dado\X${}\mathrel+\E{}$\6
$\\{strcpy}(\|g\MG\\{util\_types},\39\.{"ZZZAVIZZZZZZZZ"}){}$;\par
\fi

\M{18}Estrutura geral do algoritmo enumerativo.
Seja \PB{\|t} um vértice de \PB{\|g}. É evidente que se \PB{\|g} é hamiltoniano
então existe
um arco, digamos de \PB{\|t} a \PB{\|s}, que faz parte desse circuito. Logo,
existe um
caminho hamiltoniano de \PB{\|s} a \PB{\|t} em \PB{\|g}. Este fato determina o
comportamento
do trecho de código a seguir: um vértice \PB{\|t} e determinado e para cada
arco da
forma \PB{\\{ts}} o programa procura um caminho hamiltoniano de \PB{\|s} a \PB{%
\|t}.
Se para algum arco \PB{\\{ts}} um tal caminho é encontrado entõa o grafo é
hamiltoniano, caso contrário o programa declara que o grafo dado não é
hamiltoniano e pára.

\Y\B\4\X18:Verifique se \PB{\|g} é hamiltoniano\X${}\E{}$\6
${}\{{}$\1\6
\&{Boolean} \\{hamiltoniano}${}\K\.{FALSE}{}$;\7
\&{if} (\\{heurística})\1\6
\X20:Encontre em \PB{\|g} um vértice \PB{\|t} de grau de saída mínimo\X\2\6
\&{else}\1\5
${}\|t\K\|g\MG\\{vertices};{}$\2\6
\X19:Marque todos vértices como inativos\X;\6
${}\|t\MG\\{current\_arc}\K\|t\MG\\{arcs};{}$\6
\&{while} ${}(\|t\MG\\{current\_arc}\W\R\\{hamiltoniano}{}$)\6
${}\{{}$\1\6
${}\|s\K\|t\MG\\{current\_arc}\MG\\{tip};{}$\6
${}\|s\MG\\{pred}\K\|t;{}$\6
\X21:Se existe um caminho hamiltoniano de \PB{\|s} a \PB{\|t}, \PB{$%
\\{hamiltoniano}\K\.{TRUE}$}\X;\6
\&{if} ${}(\R\\{hamiltoniano}){}$\1\5
${}\|t\MG\\{current\_arc}\K\|t\MG\\{current\_arc}\MG\\{next};{}$\2\6
\4${}\}{}$\2\6
\&{if} (\\{hamiltoniano})\6
${}\{{}$\1\6
\X23:Verifique se os \PB{\\{current\_arc}}'s formam um circuito hamiltoniano\X;%
\6
${}\\{fprintf}(\\{stdout},\39\.{"O\ grafo\ e\ hamiltoni}\)\.{ano.\\n"});{}$\6
\4${}\}{}$\2\6
\&{else}\1\5
${}\\{fprintf}(\\{stdout},\39\.{"O\ grafo\ nao\ e\ hamil}\)\.{toniano.%
\\n"});{}$\2\6
${}\\{fprintf}(\\{stdout},\39\.{"no\ backtrackings:\ \%}\)\.{ld.\\nno\ nos\
gerados:}\)\.{\ \%ld.\\n"},\39\\{no\_backtrackings},\39\\{no\_nos});{}$\6
\4${}\}{}$\2\par
\U5.\fi

\M{19}
\Y\B\4\X19:Marque todos vértices como inativos\X${}\E{}$\6
${}\{{}$\1\6
\&{register} \&{Vertex} ${}{*}\|v;{}$\7
\&{for} ${}(\|v\K\|g\MG\\{vertices};{}$ ${}\|v<\|g\MG\\{vertices}+\|g\MG\|n;{}$
${}\|v\PP){}$\1\5
${}\|v\MG\\{estado}\K\.{INATIVO};{}$\2\6
\4${}\}{}$\2\par
\U18.\fi

\M{20}Ao final deste bloco a variável \PB{\|t} contém um vértice
em \PB{\|g} de grau de saída máximo.

\Y\B\4\X20:Encontre em \PB{\|g} um vértice \PB{\|t} de grau de saída mínimo%
\X${}\E{}$\6
${}\{{}$\1\6
\&{register} \&{Vertex} ${}{*}\|v;{}$\6
\&{register} \&{Arc} ${}{*}\|a;{}$\6
\&{unsigned} \&{long} \\{grau\_min}${}\K\T{0};{}$\7
${}\|t\K\|g\MG\\{vertices};{}$\6
\&{for} ${}(\|a\K\|t\MG\\{arcs};{}$ \|a; ${}\|a\K\|a\MG\\{next}){}$\1\5
${}\\{grau\_min}\PP;{}$\2\6
\&{for} ${}(\|v\K\|g\MG\\{vertices}+\T{1};{}$ ${}\|v<\|g\MG\\{vertices}+\|g\MG%
\|n;{}$ ${}\|v\PP{}$)\6
${}\{{}$\1\6
\&{unsigned} \&{long} \\{grau}${}\K\T{0};{}$\7
\&{for} ${}(\|a\K\|v\MG\\{arcs};{}$ \|a; ${}\|a\K\|a\MG\\{next}){}$\1\5
${}\\{grau}\PP;{}$\2\6
\&{if} ${}(\\{grau}<\\{grau\_min}{}$)\6
${}\{{}$\1\6
${}\|t\K\|v;{}$\6
${}\\{grau\_min}\K\\{grau};{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
${}\\{fprintf}(\\{stdout},\39\.{"Vertice\ origem:\ \%s.}\)\.{\\nGrau\ de\
saida:\ \%lu}\)\.{.\\n"},\39\|t\MG\\{name},\39\\{grau\_min});{}$\6
\4${}\}{}$\2\par
\U18.\fi

\M{21}Cada iteração do trecho de código deste bloco começa com um caminho de %
\PB{\|s} a
\PB{\|u}. Cada iteração tenta estender este caminho a um caminho hamiltoniano
que
vá de \PB{\|s} a \PB{\|t}. Assim, por exemplo, se no início de uma iteração
tem-se que
\PB{$\|u\K\|t$} e o comprimento do caminho é \PB{$\|g\MG\|n-\T{1}$}, tem-se que
um caminho
hamiltoniado de \PB{\|s} a \PB{\|t} acaba de ser encontrado.

O número de iterações do laço \PB{\&{while} ${}(\R\\{tentou\_tudo}\W\R%
\\{hamiltoniano})$} é
essencialmente dado pela soma de \PB{\\{no\_nos}} e \PB{\\{no\_backtrackings}}.
A váriável
\PB{\\{no\_nos}} indica o número de nós gerados na árvore de decisão e \PB{%
\\{backtrackings}}
indica o número de arrependimentos feitos pelo programa.

Durante a execução o número de nós gerados da árvore de decisão é
contado. A cada 10 Mega nós um ponto (`.') é impresso para indicar que o
programa ainda está trabalhando.


\Y\B\4\X21:Se existe um caminho hamiltoniano de \PB{\|s} a \PB{\|t}, \PB{$%
\\{hamiltoniano}\K\.{TRUE}$}\X${}\E{}$\6
${}\{{}$\1\6
\&{unsigned} \&{long} \\{comprimento};\C{ número de arcos no caminho corrente }%
\6
\&{Boolean} \\{tentou\_tudo};\C{ indica se todos os candidatos a solução foram
                           testados }\7
${}\|u\K\|s;{}$\6
${}\|u\MG\\{current\_arc}\K\|u\MG\\{arcs};{}$\6
${}\|u\MG\\{estado}\K\.{ATIVO};{}$\6
${}\\{comprimento}\K\T{0};{}$\6
${}\\{tentou\_tudo}\K\.{FALSE};{}$\6
\&{while} ${}(\R\\{tentou\_tudo}\W\R\\{hamiltoniano}{}$)\6
${}\{{}$\1\6
\&{if} ${}(\|u\E\|t\W\\{comprimento}\E\|g\MG\|n-\T{1}){}$\1\5
${}\\{hamiltoniano}\K\.{TRUE};{}$\2\6
\&{else} \&{if} ${}(\|u\E\|s\W\|u\MG\\{current\_arc}\E\NULL){}$\5
${}\{{}$\1\6
${}\|u\MG\\{estado}\K\.{INATIVO};{}$\6
${}\\{tentou\_tudo}\K\.{TRUE};{}$\6
\4${}\}{}$\2\6
\&{else} \&{if} ${}(\|u\E\|t\V\|u\MG\\{current\_arc}\E\NULL){}$\5
${}\{{}$\C{ backtracking }\1\6
${}\\{no\_backtrackings}\PP;{}$\6
${}\|u\MG\\{estado}\K\.{INATIVO};{}$\6
${}\\{comprimento}\MM;{}$\6
${}\|u\K\|u\MG\\{pred};{}$\6
${}\|u\MG\\{current\_arc}\K\|u\MG\\{current\_arc}\MG\\{next};{}$\6
\4${}\}{}$\2\6
\&{else} \&{if} ${}(\|u\MG\\{current\_arc}\MG\\{tip}\MG\\{estado}\E%
\.{ATIVO}{}$)\6
${}\{{}$\C{ vamos tentar o próximo arco }\1\6
${}\\{no\_nos}\PP;{}$\6
${}\|u\MG\\{current\_arc}\K\|u\MG\\{current\_arc}\MG\\{next};{}$\6
\4${}\}{}$\2\6
\&{else}\6
${}\{{}$\C{ cresce o caminho corrente }\1\6
\&{Vertex} ${}{*}\|v{}$;\7
${}\\{no\_nos}\PP{}$;\6
${}\|v\K\|u\MG\\{current\_arc}\MG\\{tip};{}$\6
${}\|v\MG\\{estado}\K\.{ATIVO};{}$\6
${}\\{comprimento}\PP;{}$\6
${}\|v\MG\\{pred}\K\|u;{}$\6
\&{if} ${}(\|v\I\|t){}$\1\5
${}\|v\MG\\{current\_arc}\K\|v\MG\\{arcs};{}$\2\6
${}\|u\K\|v;{}$\6
\4${}\}{}$\2\6
\&{if} ${}(\\{no\_nos}\MOD\T{10000000}\E\T{0}{}$)\C{ só para ver se o prog.
ainda está vivo }\6
${}\{{}$\1\6
${}\\{fprintf}(\\{stdout},\39\.{"."});{}$\6
\\{fflush}(\\{stdout});\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
${}\\{fprintf}(\\{stdout},\39\.{"\\n"});{}$\6
\4${}\}{}$\2\par
\U18.\fi

\M{22}

\Y\B\4\X8:Variáveis locais do \PB{\\{main}}\X${}\mathrel+\E{}$\6
\&{unsigned} \&{long} \\{no\_nos}${}\K\T{0};{}$\6
\&{unsigned} \&{long} \\{no\_backtrackings}${}\K\T{0}{}$;\par
\fi

\M{23}Se o programa encontra um circuito hamiltoniano, então os
\PB{\\{current\_arc}}'s formam este circuito. Neste bloco são contados
e marcados todos os vértices que fazem parte do suposto circuito
hamiltoniano. Caso os \PB{\\{current\_arc}}'s não formem um circuito
hamiltoniano,  o programa para após escrever uma mensagem de erro.


\Y\B\4\X23:Verifique se os \PB{\\{current\_arc}}'s formam um circuito
hamiltoniano\X${}\E{}$\6
${}\{{}$\1\6
\&{register} \&{Arc} ${}{*}\|a;{}$\6
\&{long} \\{comprimento};\C{ número de arcos percorridos }\7
${}\\{fprintf}(\\{stdout},\39\.{"Circuito\ hamiltonia}\)\.{no:\ "});{}$\6
${}\\{fprintf}(\\{stdout},\39\.{"\%s"},\39\|t\MG\\{name});{}$\6
\&{for} ${}(\|a\K\|t\MG\\{current\_arc},\39\\{comprimento}\K\T{1};{}$ ${}\|a\MG%
\\{tip}\I\|t;{}$ ${}\|a\K\|a\MG\\{tip}\MG\\{current\_arc}){}$\5
${}\{{}$\1\6
${}\\{fprintf}(\\{stdout},\39\.{",\ \%s"},\39\|a\MG\\{tip}\MG\\{name});{}$\6
\&{if} ${}(\|a\MG\\{tip}\MG\\{estado}\E\.{ATIVO}){}$\5
${}\{{}$\1\6
${}\\{comprimento}\PP;{}$\6
${}\|a\MG\\{tip}\MG\\{estado}\K\.{MARCADO};{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\2\7
${}\\{fprintf}(\\{stdout},\39\.{"\\n"});{}$\6
\&{if} ${}(\\{comprimento}\I\|g\MG\|n){}$\5
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"\%s:\ os\ current\_arc'}\)\.{s\ nao\ formam\
um\ circ}\)\.{uito\ hamiltoniano!\\n}\)\.{"}\.{"comprimento:\ \%ld.\\n}\)\.{"},%
\39\\{nome\_programa},\39\\{comprimento});{}$\6
\&{return} (\\{putz\_programa\_errado});\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U18.\fi

\N{2}{24}Salva grafo. Se o usuário utilizou a opção
\texttt{-o}\opcao{nome} o grafo \PB{\|g} é salvo no arquivo
\opcao{nome}. É usual que o arquivo que contém um grafo no formato do
\sgb\ tenha a extensão \texttt{.gb}. Para salvar um grafo usamos a
subrotina \PB{\\{gb\_save}} do módulo \gbs\ do \sgb.



\Y\B\4\X24:Salve o grafo \PB{\|g} no arquivo \PB{\\{salva\_arquivo}}\X${}\E{}$\6
${}\{{}$\1\6
\&{long} \\{anomalia}${}\K\\{save\_graph}(\|g,\39\\{salva\_arquivo});{}$\7
\&{if} (\\{anomalia})\6
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"\%s:\ grafo\ nao\ pode\ }\)\.{ser\ salvo\ no\
arquivo}\)\.{"}\.{"\ \%s\ (codigo\ do\ erro}\)\.{:\ \%ld)\\n"},\39\\{nome%
\_programa},\39\\{salva\_arquivo},\39\\{anomalia});{}$\6
\\{gb\_recycle}(\|g);\6
\\{exit}(\\{salva\_grafo\_erro});\C{ Opsss ... }\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U5.\fi

\M{25}

\fi

\N{2}{26}Exercícios.
\begin{enumerate}
\item[1.]  Qual o consumo de tempo do programa quando \PB{\|g} é um
circuito com \PB{\|n} vértices
(opção \texttt{-c})? A heurística (opção \texttt{-h}) reduz o consumo
de tempo neste caso?

\item[2.]  Qual o consumo de tempo do programa quando \PB{\|g} é um
grafo com \PB{\|n} vértices e sem arcos
(opção \texttt{-e})? A heurística (opção \texttt{-h}) reduz o consumo
de tempo neste?


\item[3.] Qual o consumo de tempo do programa quando \PB{\|g} é um
torneio com \PB{\|n} vértices
(opção \texttt{-t})? A heurística (opção \texttt{-h}) reduz o consumo
de tempo neste caso?

\item[4.] Qual o consumo de tempo do programa quando \PB{\|g} é um
grafo completo com \PB{\|n} vértices
(opção \texttt{-c})? A heurística (opção \texttt{-h}) reduz o consumo
de tempo neste caso?

\item[5.] Qual o consumo de tempo assintótico no pior caso deste
programa? Apresente um tipo de grafo no qual este consumo de tempo é
alcançado.


\item[6.] Descreva alguns tipos de grafos para os quais a heurítica do
vértice de menor de grau de saída (opção \texttt{-h}) faz com que o
programa/algoritmo gaste uma quantidade de tempo significativamente menor.

\item[7.] Descreva um exemplo em que o tempo gasto pelo
programa/algoritmo utilizando a heurística é maior que se não ela não
fosse usada.

\item[8.] `Envenene' esta implementação através de mais algumas
heurísticas.

\item[9.] O \sgb\ possui mais geradores de grafos. Acrescente esses
geradores a este programa e considere o consumo de tempo do programa
tende esses grafos como entrada.

\item[10.] Algoritmos de enumeração  são muitas vezes escritos de
manera recursiva. Quais estruturas de dados que na presente
implementação fazem o papel da tal pilha de recursão?

\item[11.] Escreva uma função recursiva
\begin{center}
\PB{\&{Boolean}(\&{Graph} ${}{*}\|g){}$ $\{$ $\,\ldots\,$ $\}$}
\end{center}
que devolve \PB{\.{TRUE}} se \PB{\|g} é hamiltoniano e \PB{\.{FALSE}} caso
contrário.

\end{enumerate}

\cwebIndexIntro{%
Aqui vai uma lista de identificadores usados e onde eles aparecem.
Entradas grifadas indicam os lugares de definições. Mensagens de erros
também são mostradas.
}

\end{document}


\fi


\inx
\fin
\con
