P1 - Teoria dos Grafos - 2023-1

Instituto de Matem´atica e Estat´ıstica - UERJ 1a. Prova de Teoria dos Grafos Professor: Luerbio Faria Data: 21/03/2023 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 se G ´e uma ´arvore, ent˜ao m = n − 1. 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. G H 4. [2.0] Encontre o grafo G = (V, E) com menor n´umero de v´ertices tal que 1 = cv(G), 2 = ce(G), δ = 3 e ∆ = 4. 5. [2.0] Responda com as contas - Quantos v´ertices possui um grafo: (a) 5-regular com 40 arestas? (b) ac´ıclico com 15 componentes conexas e 50 arestas? (c) Com menor n´umero de v´ertices e 49 arestas? (d) ´arvore com 11 folhas e diˆametro 3?