busca geral em grafos e digrafos

Prévia do material em texto

2. Busca Geral em Grafos e Digrafos
1. Formular uma descric¸a˜o do algoritmo geral do busca, no caso do grafo (na˜o direcionado) de en-
trada na˜o ser necessariamente conexo. Fac¸a a modificac¸a˜o necessa´ria para determinar o nu´mero
de componentes conexos de G.
2. Baseado no algoritmo geral de busca, formular uma descric¸a˜o sucinta do algoritmo de busca em
largura, isto e´, ja´ sabendo que a estrutura e´ uma fila, explicitar o que pode ser rapidamente
modificado no algoritmo.
3. Formular uma descric¸a˜o do algoritmo de busca em largura que classifica as arestas, criando 4
estruturas, uma para cada tipo de aresta (pai, tio, irma˜o e primo), e tambe´m com cada aresta
tendo a informac¸a˜o de a qual tipo ela pertence.
4. Em uma busca, um outro paraˆmetro u´til de ser computado e´ a ordem em que os ve´rtices entram
e saem da estrutura M . No caso da busca em largura, este paraˆmetro e´ chamado de largura
L do ve´rtice, e no caso de busca em profundidade, temos a PE profundidade de entrada e PS
profundidade de sa´ıda denotando, respectivamente, a ordem em que entram em M e que saem
de M . Explique porque na˜o e´ interessante ter dois valores para a Largura (de entrada e de
sa´ıda). Fac¸a a modificac¸a˜o no algoritmo de busca em largura, para determinar L, para todos os
ve´rtices de G.
5. Decida se a seguinte ideia esta´ correta, para determinar se um grafo tem triaˆngulos: Execute
uma busca em largura em G com raiz v (qualquer) determinando se existe aresta irm~ao. Se
tiver alguma, conclua que o grafo tem triaˆngulo, se na˜o, conclua que o grafo na˜o tem triaˆngulo.
Se tiver correta, analise a sua complexidade. Se na˜o estiver, ale´m de dar um contra-exemplo,
fac¸a uma proposta de algoritmo que de fato, identifica se G tem um triaˆngulo.
6. Prove que um grafo G tem um ciclo ı´mpar, se e somente se, em qualquer busca em largura em
G existe ao menos uma aresta primo ou irm~ao.
Baseado nisto, deˆ um algoritmo o´timo que reconhece se um grafo e´, ou na˜o, um grafo bipartido.
7. Formular uma descric¸a˜o recursiva do algoritmo de busca em profundidade.
8. Um ve´rtice u e´ chamado de raiz de um digrafo se existe um caminho (direcionado) de u para
todo ve´rtice do digrafo.
Observe que nem sempre e´ o caso de uma busca em um digrafo produzir uma u´nica a´rvore de busca,
mesmo no caso do seu grafo subjacente ser conexo. Neste caso, dizemos que produz uma floresta de
busca. Sempre que uma busca e´ executada, consideramos que ela foi executada no grafo todo, mesmo ele
na˜o sendo conexo.
Mostre que G e´ fortemente conexo se e somente se toda busca em profundidade em G gera uma
(u´nica) a´rvore de busca.
9. Fac¸a as devidas incluso˜es de comandos no algoritmo geral de busca para determinar PE e PS
indepedentemente do grafo ser conexo ou na˜o, direcionado, ou na˜o.
10. Em que condic¸o˜es sobre G uma busca em profundidade em um grafo (na˜o direcionado) satisfaz:
Se PE(u) < PE(v), enta˜o PS(u) < PS(v), para todos u, v ∈ V (G)?
versa˜o 1 de 2018/2, em 1 set 2018