AV3 de Introdução à Combinatória da UFPE - 2018.2

1.Escreva uma relação de recorrência que determina o número de regiões do plano determinadas por n circunferências concêntricas em um dado ponto P com raios distintos e n retas concorrentes em P; para n 1. Determine a solução.

Observe as seguintes representações de dois grafos G e H e responda.

a)G é um grafo simples ou multigrafo? Justifique.

b)G e H são grafos isomorfos? Justifique.

c)Qual é a definição de grafo euleriano? Existe uma condição necessária e suficiente para sim? (Se sim descreva).

d)G é euleriano? Se sim, exiba a estrutura que satisfaz a definição, senão justifique.

e)G é bipartido? Justifique.

f)G é planar? Justifique.

g)Enuncie o Teorema de Euler que dá uma condição necessária para todo grafo planar.

h)Defina árvore