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
Última edição: poti (Sex 02 Mai, 2014 19:14). Total de 1 vez.
Razão: Alterar Título
Razão: Alterar Título
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.
Última edição: Rafa2604 (Dom 26 Fev, 2017 12:34). Total de 1 vez.