2a Prova de Algoritmos e Teoria dos Grafos (2006-1)
(1) Leia com atenção toda a prova. Entender o enunciado das questões faz parte da prova.
(2) A prova vale 100 pontos. (3) Não precisa devolver a folha de questões e pode responder as
questões usando lápis. (4) A prova é sem consulta. (5) Se fizer alguma pergunta cuja resposta
é algum item acima, perde 10 pontos.
1) O k-cubo é o grafo cujo conjunto de vértices são as seqüencias binárias de k
bits e dois vértices são adjacentes se e somente se as k-tuplas correspondentes
diferem exatamente em uma posição.
Por exemplo, o 3-cubo tem oito vértices, pois são oito seqüências binárias
distintas com 3 bits. É 3-regular, pois a vizinhança do vértice b1 b2 b3 são os
três vértices obtidos complementando-se um dos bits bi de cada vez, e tem
doze arestas. Uma representação geométrica é dada pelo diagrama abaixo.
110.
v
010
..
....
....
....
....
.
.
.
..
....
....
v
v
000
..
....
....
....
....
.
.
.
..
....
....
011
v
.
....
....
....
....
.
.
.
...
....
....
111v
100
v
v
.
....
....
....
....
.
.
.
...
....
....
v
101
001
O k-cubo é um grafo bastante simétrico: mantendo um dos bits fixos, por
exemplo fixando o mais significativo como 0, o grafo induzido por esses vértices
é (isomorfo a) um (k − 1)-cubo. Essa caracterı́stica ajuda a provar muitas
propriedades satisfeitas pelo k-cubo por indução em k.
A distância entre dois vértices a1 a2 . . . ak e b1 b2 . . . bk num k-cubo é o
número de posições das seqüências em que os bits são diferentes, ou seja
Pk
i=1 (ai xor bi ).
Resolva os questões abaixo para todo k > 1.
(i) (10) Qual é o número de vértices, o grau dos vértices e o número de
arestas do k-cubo? Justifique brevemente as respostas.
O número de vértices é |V | = 2k pois esse é o número de seqüências binárias
de comprimento k. O vértice b1 b2 . . . bi . . . bk tem como vizinhos os vértices
b1 b2 . . . b i . . . b k
b1 b2 . . . b i . . . b k
..
.
b1 b2 . . . bi . . . b k
..
.
b1 b2 . . . b i . . . bk
onde bj é o complemento do bit bj . Assim, o k-cubo é k-regular (ou log2 |V |regular). O número de arestas é metade da soma dos graus, ou seja
k2k
|V | log2 |V |
= k2k−1 =
.
2
2
(ii) (10) Qual é o diâmetro e a cintura do k-cubo? Justifique suas respostas.
2
A distância entre dois vértices a = a1 a2 . . . ak e b = b1 b2 . . . bk num k-cubo
é
dist(a, b) =
k
X
(ai xor bi ) 6 k.
i=1
Como a distância entre 00 . . . 0 e 111 . . . 1 é k temos que o diâmetro é k =
log2 |V |.
A cintura do 1-cubo é ∞. A do 2-cubo é 4 pois o grafo é um circuito de
comprimento 4. Para todo k > 2 o k-cubo contém um subgrafo isomorfo ao
2-cubo (basta fixar k − 2 bits quaisquer e varia os outros 2) e não contém
triângulo (se a, b e c são vértices, ab e ac arestas então b e c têm pelo
menos dois bits diferentes e bc não é artesta), então a cintura é 4.
(iii) (10) No k-cubo, considere o subgrafo induzido pelos vértices da
forma 0b2 . . . bk , denotado por G0 , e o subgrafo induzido pelos vértices da
forma 1b2 . . . bk , denotado G1 . Mostre que se S é um subconjunto com menos que k vértices cuja remoção desconecta o k-cubo, então a remoção de S
desconecta G0 ou G1 .
Suponha G0 e G1 conexos. Como |S| < k deve existir no k-cubo menos
S uma aresta da forma {Ob2 . . . bk , 1b2 . . . bk } e portanto o k-cubo menos S é
conexo.
(iv) (30) Demonstre que o k-cubo tem conexidade k. (Sugestão: item
anterior e indução em k.)
Para k = 1 a conexidade é 1 pois o grafo é um caminho e, vimos em aula,
caminhos têm conexidade 1. Suponha que o k − 1-cubo tem conexidade k − 1
(k > 1).
O k-cubo tem 2k > k vértices. Suponha que a remoção de menos que
k vértices desconecta o k-cubo. Pelo item anterior G0 ou G1 é desconexo,
vamos supor que G0 é desconexo. A conexidade de G0 é k − 1, por hipótese
de indução. Portanto k > |S ∩ V (G0 )| > k − 1, ou seja S ⊂ V (G0 ). Todos
os vértices que sobraram em G0 após a remoção de S têm um vizinho em G1 ,
que é conexo pois todos os vértices removidos estavam em G0 , logo o k-cubo
menos S é conexo. Uma contradição. A remoção de menos de k vértices não
desconecta o k-cubo e a remoção de k desconecta (remova os vizinhos de um
vértice) portanto a conexidade é k.
(v) (20) Determine a aresta-conexidade do k-cubo. Justifique.
De (i) temos o grau mı́nimo δ = k. Do item anterior temos a conexidade
κ = k. Do teorema κ(G) 6 λ(G) 6 δ(G) tiramos que a aresta-conexidade do
k-cubo é k.
2) (30) Escreva um algoritmo O(|V | + |E|) que receba um grafo G = (V, E) e
responda sim se G for um caminho e não se G não for um caminho. Explique
e justifique o funcionamento do algoritmo e prove que ele tem a complexidade
pedida. G é caminho se e só se é conexo, tem dois vértices de grau 1 e os
vértices restantes têm grau 2. Assim
1. Teste se o grafo é conexo.
2. Para cada vértice v calcule o grau de v. Se o resultado é maior que
2 devolva N~
AO, sen~
ao se for 1 incremente cont.
3. Se cont=2 devolva SIM sen~
ao devolva N~
AO.
3
Usando lista de adjacencias, o passo 1 pode ser feito em tempo O(|V | + |E|)
usando um algoritmo de busca. O passo 2 é feito em tempo O(|E|) e o 3 em
O(1).