Lista 1

Prévia do material em texto

Universidade Federal de Juiz de Fora - UFJF 
Departamento de Ciência da Computação - DCC 
Disciplina: Teoria dos Grafos 
Prof. Stênio Sã 
Lista 1 
 
1) [CLR 25.2-4, CLRS 24.3-4] A cada arco uv de um digrafo está associado um número 
racional conf(uv) no intervalo [0,1]. Este número representa aconfiabilidade do 
arco uv, ou seja, a probabilidade de que o arco não vai "quebrar" nem "desaparecer". 
Dê uma definição apropriada para a confiabilidade de um passeio. Encontre 
passeios de confiabilidade máxima de um vértice r a cada um dos demais vértices. 
2) [CLR 25.2-2] Mostre que o algoritmo DIJKSTRA pode produzir resultados errados 
se f(uv) < 0 para algum arco uv. Mostre que isso pode acontecer mesmo que o 
digrafo não tenha ciclos de peso negativo. 
3) [IP 436] Suponha que os arcos de um digrafo têm pesos positivos. Queremos 
encontrar um passeio de r a s que tenha peso máximo. É possível resolver o 
problema trocando EXTRAI-MIN por EXTRAI-MÁX na linha 8 do algoritmo DIJKSTRA? 
(É claro que esse ajuste deve ser acompanhado de outros ajustes óbvios 
nas linhas 2 e 10.) 
4) Mostre que um digrafo (V, A) é fortemente conexo se e somente se, para 
toda bipartição (X, Y) de V, algum arco tem ponta inicial em X e ponta final em Y. 
5) Escreva um algoritmo que decida se um digrafo é fortemente conexo. 
6) Seja X um componente forte um digrafo. Mostre que o subdigrafo induzido por X é 
fortemente conexo. 
7) Mostre que cada vértice de um digrafo pertence a um e um só componente forte. 
8) Mostre que todos os vértices de qualquer ciclo de um digrafo pertencem ao mesmo 
componente forte do digrafo. 
9) Que aparência tem a matriz da adjacência do transposto de um digrafo? (Esse 
exercício revela a origem da termo "transposto"). Escreva uma 
rotinaTRANSPOSTO que receba as listas de adjacência Adj de um digrafo e produza as 
listas de adjacência do digrafo transposto. 
10) [CLRS 22-4 REACHABILITY] Seja D um digrafo com n vértices. Suponha que cada 
vértice u tem um rótulo p(u) do conjunto 1,2,…,n. Para cada vértice u, sejaR(u) o 
conjunto dos vértices acessíveis a partir de u. Para cada vértice u, seja min(u) o 
menor número da forma p(v) para v em R(u). Dê um algoritmo que calcule min(u) 
para cada u em tempo Ο(n+m). 
11) [IP 365] Um digrafo simétrico é bicromático (ou bipartido) se for possível atribuir 
uma de duas cores a cada um de seus vértices de tal modo que as pontas de cada 
arco tenham cores diferentes. Escreva um algoritmo que decide se um dado grafo é 
ou não bicromático. O algoritmo pode consumir Ο(n+m) unidades de tempo, ao 
processar um grafo com n vértices e m arcos. 
12) Quais das seguintes enumerações dos vértices da figura abaixo estão em pós-
ordem? 
e k l f b g h i c j d a 
h i g c k l f e b j d a 
k l f j d e b g h i c a 
 
 13 )Enumere em pós-ordem os vértices dos digrafos das figura da questão anterior. 
 
13) Um vértice x é acessível a partir de um vértice r se existe um passeio de r a x. 
O território de um vértice r é o conjunto de todos os vértices acessíveis a partir de r. 
Se X é o território de um vértice então nenhum arco sai de X: não existe arco com 
ponta inicial em X e ponta final fora de X. Qual a relação entre os territórios de dois 
vértices diferentes? 
14) . Nos Grafos abaixo, verifique se são isomorfos. Se forem, dê uma função ou funções que estabelecem o 
isomorfismo. Se não forem, dê pelo menos uma razão do não isomorfismo. 
 
 
FUNDAÇÃO UNIVERSIDADE FEDERAL DO VALE DO SÃO FRANCISCO – UNIVASF 
COLEGIADO DE ENGENHARIA DA COMPUTAÇÃO 
DISCIPLINA DE MATEMÁTICA DISCRETA 
Prof. Jorge Cavalcanti 
 
 
Av. Antonio Carlos Magalhães, 510 – Santo Antonio – Juazeiro-BA – ww.univasf.edu.br 
3 5 
2 1 
4 
 
 
1. Responda as seguintes perguntas sobre o grafo mostrado a seguir: 
 a. Este grafo é simples? 
b. Este grafo é completo? 
c. Este grafo é conexo? 
d. Existem dois caminhos entre os vértices 3 e 6? 
e. Este grafo possui algum ciclo? 
f. O grafo possui algum arco cuja remoção o tornaria um grafo acíclico? 
g. O grafo possui algum arco cuja remoção o tornaria desconexo? 
2. Esboce uma figura para cada um dos seguintes grafos: 
a. Um grafo simples com três nós, cada qual com grau 2 
b. Um grafo de quatro vértices, com ciclos de tamanho 1, 2, 3 e 4 
c. Um grafo não completo com quatro nós, cada um de grau 4 
3. Desenhe K6. 
4. Desenhe K3,4. 
5. Nos Grafos abaixos, verifique se são isomorfos. Se forem, dê uma função ou funções que estabelecem o 
isomorfismo. Se não forem, dê pelo menos uma razão do não isomorfismo. 
a) b) 
c) d) 
 
6. Mostre que o grafo K2,3 é planar. 
7. Se um grafo é planar simples e conexo, tem 6 nós, todos de grau 3, em quantas regiões ele divide o 
plano? 
 
 8 - Desenhe o grafo representado pela seguinte matriz de adjacência em forma de triangular inferior. 
 
 
9 - Escreva a matriz e a lista de adjacência para o grafo abaixo: 
 
LISTA DE EXERCÍCIOS – 5.1 – Grafos e Árvores 
«
«
«
«
¬
ª
0210
110
01
2