ALGORITMOS E IMPLEMENTAÇÕESGrafo Planar

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
Mai 2014 02 18:45

Grafo Planar

Mensagem não lida por Kssy »

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.

Última edição: poti (Sex 02 Mai, 2014 19:14). 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 12:34

Re: Grafo Planar

Mensagem não lida por Rafa2604 »

Kssy escreveu: 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.
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.



Responder

Voltar para “ALGORITMOS E IMPLEMENTAÇÕES”