ALGORITMOS E IMPLEMENTAÇÕES ⇒ Grafos
Moderador: [ Moderadores TTB ]
Abr 2014
23
15:22
Grafos
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
Razão: Alterar Título
Fev 2017
26
11:26
Re: Grafos
Vamos considerar primeiramente cada subgrafo separadamente, pois são componente conexas de G.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.
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.
-
- Tópicos Semelhantes
- Respostas
- Exibições
- Última msg
-
- 0 Respostas
- 236 Exibições
-
Última msg por Lucastadeu14
-
- 1 Respostas
- 225 Exibições
-
Última msg por Idocrase
-
- 0 Respostas
- 181 Exibições
-
Última msg por Thiagosn1