Exercícios Resolvidos de Introdução à Estatística

Ver Teoria

Enunciado

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

Passo 1

Eai pessoal, nessa questão o primeiro passo é enumerar os vértices do grafo G e do grafo H, fazendo a correspondência dos vértices e arestas de cada um para identificar isomorfismo.

Precisamos lembrar também que grafos simples não possuem a arestas laço. Logo o grafo G não é simples, pois possui aresta laço.

Como visto na Figura podemos mostrar que:

1 ⇒ a

2 ⇒ b

3 ⇒ c

4 ⇒ d

5 ⇒ e

6 ⇒ f

Portanto, os grafos G e H são isomorfos já que é possível fazer correspondência entre os vértices e arestas de ambos respeitando as relações de incidência (conexões).

Passo 2

Precisamos recordar que a definição de um grafo euleriano diz que se é possível construir um ciclo que use cada aresta do grafo exatamente uma vez, então o grafo é euleriano.

Como G não tem arestas:

G   é   e u l e r i a n o   ⇔ G   é   c o n e x o   e   ∀ v ∈ V ( G ) , d ( v )   é   p a r , sendo d(v) o grau de v.

Para descrever o ciclo de G, basta citar apenas os vértices pois não temos arestas em paralelo, começando pelo laço: λ   =   1,1 , 2,3 , 1,5 , 3,4 , 5,6 , 4,2 , 6,1 equivalente à λ '   =   a , a , d , e , a , b , e , f , d , c , f , d , c , a em H.

Outra condição importante é que para um grafo ser bipartido não pode possuir circuito de comprimento ímpar, logo G não é bipartido por conta do circuito 1,3,5,1 por exemplo. Além disso, G não é planar já que possui uma representação (grafo H) em que suas arestas não se cruzam.

Para enunciar o teorema de Euler que dá condição necessária vamos supor G planar. Se G é um grafo planar, então temos

V ( G )   -   E ( G )   + f   =   p   + 1

V ( G ) é   o   n ú m e r o   d e   v é r t i c e s

E ( G ) é   o   n ú m e r o   d e   a r e s t a s

f é o número de faces de uma representação plana

p é o número de componentes conexos de G.

Por fim, uma árvore é um grafo conexo sem circuito ou um grafo minimamente conexo. Portanto, árvore é um grafo G no qual ∀ u   e   v ∈   V ( G ) ,   u ≠ v , existe um único u-v caminho em G.

Resposta

a) G não é grafo simples, é multigrafo, pois tem aresta laço ( incidente a apenas um v )

b) Sim,é possível fazer correspondência entre os vértices e arestas de ambos respeitando as relações de incidência (conexões). Como não temos arestas em paralelo basta corresponder os vértices.

c) Um grafo é euleriano se é possível construir um ciclo que use cada aresta do grafo exatamente uma vez, então o grafo é euleriano. G não tem aresta. G   é   e u l e r i a n o   ⇔ G   é   c o n e x o   e   ∀ v ∈ V ( G ) , d ( v )   é   p a r , sendo d(v) o grau de v.

d) Sim, vamos descrever o ciclo citando apenas os vértices pois não temos arestas em paralelo, começando pelo laço: λ   =   1,1 , 2,3 , 1,5 , 3,4 , 5,6 , 4,2 , 6,1 equivalente à λ '   =   a , a , d , e , a , b , e , f , d , c , f , d , c , a em H.

e)Não, G não é bipartido já que possui circuito de comprimento ímpar como 1,3,5,1.

f) G não é planar já que possui uma representação (grafo H) em que suas arestas não se cruzam.

g) Se G é um grafo planar, então temos V ( G )   -   E ( G )   + f   =   p   + 1

V ( G ) é   o   n ú m e r o   d e   v é r t i c e s

E ( G ) é   o   n ú m e r o   d e   a r e s t a s

f é o número de faces de uma representação plana

p é o número de componentes conexos de G.

h) Uma árvore é um grafo conexo sem circuito ou um grafo minimamente conexo. Portanto, árvore é um grafo G no qual ∀ u   e   v ∈   V ( G ) ,   u ≠ v , existe um único u-v caminho em G.

Exercícios de Livros Relacionados

Faça um experimento de simulação usando um pacote estatístico ou outro software para estudar a distribuição de X - quando a distribuição da população é lognormal com E l n X = 3 e V l n X = 1 . Consid
Faça um experimento de simulação usando um pacote estatístico ou outro software para estudar a distribuição de X - quando a distribuição da população é Weibull com α = 2 e β = 5 , como no Exemplo 5.19
Tabela de números aleatóriosUse a décima linha da Tabela B.1 para gerar 10 números aleatórios entre 1 e 920.
Vinte e uma pacientes de uma clínica médica tiveram o seu nível de potássio no plasma medido. Os resultados foram os seguintes:Construa o histograma.Determine os 1°, 2° e 3° quartis.Qual a porcentagem
O conjunto de dados representa o número de filmes assistidos em um ano por uma amostra de 24 pessoas.121 148 94 142 170 88 221 106 186 85 18 106 67 149 28 60 101 134 139 168 92 154 53 66(d) Descreva a