Prova Grafos (2016.2)

Prévia do material em texto

Teoria​ ​dos​ ​Grafos 
 
Nome​ ​: ​ ​​​ ​​ ​​ ​Nota 
 
1)(1,0)​ ​Desenhe​ ​a​ ​árvore​ ​de​ ​12​ ​vértices​ ​associada​ ​ao​ ​seguinte​ ​código​ ​prüfer​ ​2772555888. 
2)(1,5) Mostre que se G é um grafo com e m(G)<n(G), onde m(G) é o número de arestas 
de​ ​G​ ​e​ ​n(G)​ ​é​ ​o​ ​número​ ​de​ ​vértices​ ​de​ ​G​ ​então​ ​G​ ​tem​ ​pelo​ ​menos​ ​dois​ ​vértices​ ​de​ ​grau​ ​1. 
3)(1,5)​ ​Quantas​ ​​spanning​ ​trees​​ ​o​ ​grafo​ ​abaixo​ ​possui​ ​? 
 
 
4)​ ​(1,0)​ ​Use​ ​o​ ​​método​ ​de​ ​Maghout​​ ​para​ ​determinar​ ​os​ ​cliques​ ​maximais​ ​do​ ​grafo​ ​abaixo 
 
5) (1,0) Determine a quantidade de maneiras para colorir o grafo abaixo com ​k ​cores (ou 
seja,​ ​seu​ ​​polinômio​ ​cromático​). 
 
 
 
Boa​ ​Prova,​ ​28/11/2006 
Edson​ ​Prestes