ALGORITMOS E IMPLEMENTAÇÕESGrafos

Implementação de equações dentro da computação, programação e algoritmos.

Moderador: [ Moderadores TTB ]

Avatar do usuário
Autor do Tópico
Kssy
Pleno
Mensagens: 66
Registrado em: Ter 19 Fev, 2013 13:23
Última visita: 02-09-15
Abr 2014 23 15:22

Grafos

Mensagem não lida por Kssy »

Seja G um grafo conexo com exatamente 3 componentes conexos G1, G2 e G3. Sabendo que G1 é um grafo 2-regular com 10 vértices, G2 é um grafo completo com 5 vértices e que G3 é uma árvore com 15 vértices, calcule o número de arestas de G. Justifique.

Última edição: poti (Qua 23 Abr, 2014 15:49). Total de 1 vez.
Razão: Alterar Título



Avatar do usuário
Rafa2604
2 - Nerd
Mensagens: 351
Registrado em: Qua 13 Jul, 2016 09:32
Última visita: 29-01-18
Fev 2017 26 11:26

Re: Grafos

Mensagem não lida por Rafa2604 »

Kssy escreveu:Seja G um grafo conexo com exatamente 3 componentes conexos G1, G2 e G3. Sabendo que G1 é um grafo 2-regular com 10 vértices, G2 é um grafo completo com 5 vértices e que G3 é uma árvore com 15 vértices, calcule o número de arestas de G. Justifique.
Vamos considerar primeiramente cada subgrafo separadamente, pois são componente conexas de G.
Então, temos que:
G1 = grafo 2-regular com 10 vértices.
G2 = grafo completo com 5 vértices.
G3 = árvore com 15 vértices.

Vamos considerar o seguinte teorema para resolvermos o problema:
Teorema do Aperto de Mãos: Seja G = (V, E) um grafo não orientado com e arestas, então [tex3]2e = \sum_{v \in V} gr(v)[/tex3] .

i) G1 = grafo 2-regular com 10 vértices.
Se G1 é um grafo 2-regular, então todos os seus vértices possuem grau 2, portanto, utilizando o Teorema acima temos:
[tex3]2e = \sum_{v \in V} gr(v) \;\; \rightarrow \;\; 2e = 10 \cdot 2 \;\; \rightarrow \;\; e = 10[/tex3] arestas

ii) G2 = grafo completo com 5 vértices.
Se G2 é um grafo completo com n vértices, então todos os seus vértices possuem grau (n-1), ou seja, todos os 5 vértices possuem grau 4. Portanto, utilizando o Teorema, temos:
[tex3]2e = \sum_{v \in V} gr(v) \;\; \rightarrow \;\; 2e = 5 \cdot 4 \;\; \rightarrow \;\; e = \frac{5 \cdot 4}{2} = 10[/tex3] arestas

iii) G3 = árvore com 15 vértices.
Se G3 é uma árvore, então é G3 é conexo e sem ciclos, portanto se G3 tem n vértices, G3, possui (n-1) arestas.
Portanto, como G3 possui 15 vértices, então G3 possui 14 arestas.

Logo, temos que:
G1: 10 arestas
G2: 10 arestas
G3: 14 arestas

E, portanto, G possui 34 arestas.

Última edição: Rafa2604 (Dom 26 Fev, 2017 11:26). Total de 1 vez.



Responder
  • Tópicos Semelhantes
    Respostas
    Exibições
    Última msg
  • Nova mensagem (China) Combinatória com Grafos
    por Deleted User 23699 » » em Olimpíadas
    2 Respostas
    660 Exibições
    Última msg por Deleted User 23699
  • Nova mensagem Grafos
    por Lucastadeu14 » » em Ensino Superior
    0 Respostas
    224 Exibições
    Última msg por Lucastadeu14
  • Nova mensagem Grafos
    por Idocrase » » em Ensino Superior
    1 Respostas
    209 Exibições
    Última msg por Idocrase
  • Nova mensagem Teoria dos Grafos
    por Thiagosn1 » » em Ensino Superior
    0 Respostas
    172 Exibições
    Última msg por Thiagosn1

Voltar para “ALGORITMOS E IMPLEMENTAÇÕES”