Baixe o app para aproveitar ainda mais
Prévia do material em texto
Pontifícia Universidade Católica de Minas Gerais Sistemas de Informação - Algoritmos em Grafos Profa.: Michelle Nery Nascimento 1/2020 Valor: 2,5 pontos – Data de entrega: 09/03/2020 (via SGA) 1) Determine o número de vértices de um grafo G simples, regular, com 15 arestas. 2) Determine o número de vértices de um grafo G, simples, de 9 arestas e cujos vértices, todos, têm grau 3. 3) Indique um grafo simples com 8 vértices com os seguintes graus: 1, 1, 2, 3, 3, 4, 5 e 7. 4) Apresente um grafo conexo, sem loops, com 8 vértices com os seguintes graus: 1, 1, 1, 2, 3, 4, 5 e 7. 5) Um grafo possui oito vértices e seis arestas? Esse grafo é conexo? Justifique a resposta. 6) Os grafos abaixo são isomorfos? Justifique. 7) Represente o grafo abaixo usando matriz de adjacência e, depois, lista de adjacência: 8) (Wilson, 1996) Jonh gosta de Jordan, Jean e Jane; Joe gosta de Jane e Joan; Jean e Joan gostam um do outro. Desenhe um dígrafo ilustrando estes relacionamentos entre Jonh, Joan, Jean, Jane e Joe. 9) Desenhe o grafo 𝐾" e diga quantas arestas este grafo contém. 10) Quantas arestas contém o grafo 𝐾#$? 11) Seja V um conjunto de pontos no plano. Digamos que dois desses pontos são adjacentes se a distância entre eles é menor que 2. Essa relação de adjacência define o grafo dos pontos no plano (sobre o conjunto V). Faça uma figura do grafo definido pelos pontos: (0, 2) (0, 1) (0, 0) (1, 2) (1, 1) (1, 0) (2, 2) (2, 1) (2, 0) Escreva a matriz de adjacência e a lista de adjacência do grafo. 12) Seja G um grafo com 𝑣 vértices e 𝑎 arestas. Quantas arestas contém o grafo complementar de G? 13) Encontre e mostre as condições que fazem um grafo bipartido completo Kn,m ser: a. Euleriano b. Hamiltoniano 14) Diga se os grafos abaixo são Eulerianos, Hamiltonianos, Unicursais ou nenhum deles: a. O grafo 𝐾" b. O grafo 𝐾. c. O grafo bipartido 𝐾/,0 d. O grafo bipartido 𝐾.,. 15) Se existem nove times de futebol em uma liga, é possível programar um torneio em que cada time jogue com exatamente três outros times? Resolva usando a teoria de grafos. 16) Seja 𝐺 um grafo com 𝑣 vértices e 𝑎 arestas. Quantas arestas contém 𝐺 ∪ �̅�? 17) Mostre quantos ciclos hamiltonianos disjuntos de arestas existem no grafo 𝐾/$. 17) Os grafos abaixo são isomorfos? Justifique
Compartilhar