Seja G um grafo planar conexo com sequência de vértices (2, 2, 3, 3, 3, 4, 5).
Em quantas regiões qualquer representação plana de G divide o plano? Justifique.
ALGORITMOS E IMPLEMENTAÇÕES ⇒ Grafo Planar
Moderador: [ Moderadores TTB ]
Mai 2014
02
18:45
Grafo Planar
Editado pela última vez por poti em 02 Mai 2014, 19:14, em um total de 1 vez.
Razão: Alterar Título
Razão: Alterar Título
-
Rafa2604
- Mensagens: 351
- Registrado em: 13 Jul 2016, 09:32
- Última visita: 29-01-18
- Agradeceu: 21 vezes
- Agradeceram: 135 vezes
Fev 2017
26
12:34
Re: Grafo Planar
Teorema do Aperto de Mãos: Seja G = (V, E) um grafo não orientado com e arestas, então [tex3]2e=\sum_{v∈V}gr(v)[/tex3] .
Seja G um grafo planar conexo com sequência de vértices (2, 2, 3, 3, 3, 4, 5).
Então temos 7 vértices de modo que:
[tex3]gr(v_1) = 2, \; gr(v_2) = 2, \; gr(v_3) = 3, \; gr(v_4) = 3, \; gr(v_5) = 3, \; gr(v_6) = 4, \; gr(v_7) = 5[/tex3] .
Portanto, pelo Teorema, temos:
[tex3]2e=\sum_{v∈V}gr(v) \;\; \rightarrow \;\; 2e = (2+2+3+3+3+4+5) \;\; \rightarrow \;\; 2e = 22 \;\; \rightarrow \;\; e = 11[/tex3] arestas.
Teorema de Euler: Seja G um grafo simples planar conexo com e arestas e v vértices.
Seja r o número de regiões em uma representação planar de G.
Então, [tex3]r = e - v + 2[/tex3] .
Portanto, pelo Teorema de Euler, temos:
[tex3]r = e - v + 2 \;\; \rightarrow \;\; r = 11 - 7 + 2 \;\;\rightarrow \;\; r = 6[/tex3] regiões.
Editado pela última vez por Rafa2604 em 26 Fev 2017, 12:34, em um total de 1 vez.
