Grafo planar

Disponível somente no TrabalhosFeitos
  • Páginas : 2 (314 palavras )
  • Download(s) : 0
  • Publicado : 10 de abril de 2013
Ler documento completo
Amostra do texto
GRAFO PLANAR

Um grafo diz­se planar se for possível desenhá­lo de tal forma que duas
arestas não se intersectem à excepção nos vértices inicial e final.  Um exemplos clássicos de grafos planares são dados pelos grafos que
representam os poliedros.
Abaixo um poliedro regular, o cubo e o grafo que o representa um grafo
regular.

  
A  representação  gráfica  de  um  grafo planar  na  qual  as  arestas  só  se
encontram  uma  com  outra  nos  vértices  não  é  única.  Um  grafo  planar
sempre a possui e ela se chama forma topológica ou grafo plano.Veja, porém, que podemos representar K4 pelo menos de duas maneiras,
a primeira admitindo cruzamento de arestas e a segunda não:

Em  todo  grafo  planar  vale  a  fórmula  de  Euler  N − A  +  R  = 2,  onde  N  é o
número  de vértices,  A  é o  número de arestas  e R  é o número de regiões

divididas no plano pelo grafo.

N = 13, A = 19 e R = 8. Logo 13 − 19 + 8 = 2.Detecção de Planaridade
Em  um  grafo  F  podemos,  com  segurança,  contrair  todos  os  vértices  de
grau  2  sem  afetar  seu  planaridade.  Esse  processo  é  chamado  de
Redução Elementar.Depois dessa operação, o grafo resultante G é:
1. uma única aresta;
2. um grafo completo com 4 vértices; ou
3. um grafo com n>= 5 e m>=7.
Se  G  estiver  nas  condições  1  ou  2  ele  é  planar, senão,  continua­se  a
investigação.

● Vértices: portas lógicas.
● Arestas: fios entre as portas lógicas
● Encontrar um desenho do circuito sem cruzamento de fios.
ReferenciasPATRICIO,Pedro.Grafos Planares. Grafos Planares. 2006 Disponível em:
Acesso em:
02/04/2013.
FONTES, Fábio F. da Costa. Grafos Planares. Disponível em:
Acesso em: 02/04/2013.
MEDEIROS,Esdras.Isomorfismos de Grafos, Grafos Planares e Árvores. Disponível em:
Acesso em: 02/04/2013.
SANTOS, Haroldo Gambini. Planaridade. 2011 Disponível em:
Acesso em:
02/04/2013....
tracking img