ALGORITMOS E IMPLEMENTAÇÕES ⇒ Grafos

[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.

[Rafa2604]

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]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[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]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[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]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[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.