Algoritmos e Teoremas em Grafos

Prévia do material em texto

Lista 4 - To´picos Especiais em Algoritmos e Grafos
1. Explique o erro no Teorema 1 de [1], na parte que diz que todo grafo distaˆncia heredita´rio tem
dois ve´rtices folhas ou um par de ve´rtices geˆmeos e explique como este teorema foi corrigido pelo
Teorema 2.4 de [2].
[1] Bandelt, H., Mulder, H., Distance-Hereditary Graphs, Journal of Combinatorial Theory 41,
182–208, 1986.
[2] Bandelt, H., Henkmann, A., Nicolai, F., Powers of distance-hereditary graphs, Discrete
Mathematics 145, 37–60, 1995.
2. Elabore um algoritmo para obter uma colorac¸a˜o o´tima de grafos cordais utilizando o seu esquema
de eliminac¸a˜o perfeita de ve´rtices simpliciais. Prove a corretude do seu algoritmo e analise a sua
complexidade.
3. Elabore um algoritmo para obter uma colorac¸a˜o o´tima de grafos P4-tidy.
4. Elabore um algoritmo para obter pv(G), o nu´mero mı´nimo de caminhos disjuntos em ve´rtices,
de grafos P4-tidy.
5. Diga se as seguintes afirmac¸o˜es sa˜o verdadeiras ou falsas, justificando sucintamente.
(a) Um grafo G e´ (5, 2) se e somente se G e´ sem C5 induzido.
(b) Todo grafo de permutac¸a˜o e´ um grafo (6, 2).
(c) Todo grafo P4-tidy e´ um grafo (7, 3).
(d) Todo grafo (6, 2) e´ um grafo P4-tidy.
(e) Todo grafo bipartido distaˆncia heredita´rio e´ um grafo bipartido cordal.
6. Considere que o problema ciclo hamiltoniano e´ NP-completo para grafos bipartido cor-
dais. Utilize tal informac¸a˜o para provar que ciclo hamiltoniano e´ NP-completo para grafos
fortemente cordais.
7. Mostre que o grafo da figura 1 e´ um grafo fortemente cordal (apresentando um esquema de
eliminac¸a˜o perfeito forte para este grafo).
Figura 1: Grafo do exerc´ıcio 7.
8. Mostre que o grafo da figura 2 e´ um grafo bipartido cordal transformando uma de suas clas-
ses de cores emuma clique e verificando que o grafo resultando e´ um grafo fortemente cordal,
apresentando assim um esquema de eliminac¸a˜o perfeito forte para este grafo.
Figura 2: Grafo do exerc´ıcio 8.