Prova de Reposição - Teoria dos Grafos - 2021-1

Instituto de Matemática e Estatística - UERJ Prova de Reposição de Teoria dos Grafos Professor: Luberio Faria Data: 20/09/2021 1. [2,0] Considere a relação de amizade reflexiva. Mostre que em uma reunião com 2 ou mais pessoas existem pelo menos duas com o mesmo número de amigos na mesma reunião. 2. [2,0] Desenhe todos os grafos não isomorfos com 5 vértices e 7 arestas (conexos ou não). Explique porque eles não são isomorfos 2-à-2. 3. Dada a Figura a seguir. (a) [1,2] Verifique se o par de grafos G e H são isomorfos: (b) [0,4] Para o grafo G, determine um conjunto independente máximo S ⊂ V(G). E prove porque S é máximo. (c) [0,4] Para o grafo H, determine um conjunto dominante mínimo R ⊂ V(H). E prove porque R é mínimo. (d) [0,4] Para o grafo H, determine uma cobertura por vértices mínima M ⊂ V(H). E prove porque M é mínima. (Imagem dos grafos G e H) 4. [2,0] Encontre o grafo G = (V, E) com menor número de vértices tal que 2 = cv(G), 3 = ce(G), e δ = 4. 5. [2,0] Responda com as contas - Quantos vértices possui um grafo: (a) com menor número de vértices e 120 arestas. (b) conexo com maior número de vértices e 80 arestas. (c) árvore com diâmetro menor ou igual a 3, e 93 folhas. (d) 9-regular com 243 arestas.