P1 - Teoria dos Grafos - 2021-2

Instituto de Matem´atica e Estat´ıstica - UERJ 1a. Prova de Teoria dos Grafos Professor: Luerbio Faria Data: 21/03/2022 1. [2.0] Mostre que se G ´e um grafo com exatamente 2 v´ertices u e v de grau ´ımpar, ent˜ao existe um caminho que liga u at´e v em G. 2. [2.0] Mostre que S ⇢ V ´e um conjunto independente de um grafo G = (V, E) se e somente se V \ S ´e uma cobertura por v´ertices de G. 3. Dada a Figura a seguir. (a) [1.2] Verifique se o par de grafos G e H s˜ao isomorfos: (b) [0.4] Defina Conjunto independente, clique, conjunto dominante e cobertura por v´ertices. (c) [0.4] Para o grafo G, determine um conjunto independente m´aximo S ⇢ V (G). E prove porque S ´e m´aximo. (d) [0.4] Para o grafo H, determine um conjunto dominante m´ınimo R ⇢ V (H). E prove porque R ´e m´ınimo. (e) [0.4] Para o grafo H, determine uma cobertura por v´ertices m´ınima M ⇢ V (H). E prove porque M ´e m´ınima. 1 2 3 4 6 5 12 11 10 9 7 8 a b c d e f l k j i h g G H 4. [2.0] Encontre o grafo G = (V, E) com menor n´umero de v´ertices tal que 2 = cv(G), 4 = ce(G), e δ = 4 = ∆. 5. [2.0] Responda com as contas - Quantos v´ertices possui um grafo: (a) 5-regular com 80 arestas? (b) ac´ıclico com 7 componentes conexas e 50 arestas? (c) ´arvore com 21 folhas e diˆametro 2? (d) Com menor n´umero de v´ertices e 30 arestas?