Grafo completo: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
subcategorização |
|||
Linha 1:
Um '''grafo completo''' é um [[grafo simples]] em que todo [[vértice]] é adjacente a outro vértice. O grafo completo de n vértices é frequentemente denotado por <math>K_n</math>.
▲Um '''grafo completo''' é um [[grafo simples]] em que todo [[vértice]] é adjacente a outro vértice. O grafo completo de n vértices é frequentemente denotado por <math>K_n</math>. Ele tem n*(n-1)/2 arestas (correspondendo a todas as possíveis escolhas de pares de vértices).
==Número de arestas==
O grafo <math>K_n</math> tem <math>{n \choose 2}=\frac{n(n-1)}{2}</math> arestas (correspondendo a todas as possíveis escolhas de pares de vértices).
==Planaridade==
O [[teorema de Kuratowski]] tem como consequência que um grafo <math>K_n</math> é [[grafo planar]] se e somente se <math>n\le 4</math>.
=={{Ver também}}==
*[[Grafo completo bipartido]]
<center>
<gallery>
Image:Complete graph K1.svg|<math>K_1</math>
Image:Complete graph K2.svg|<math>K_2</math>
Image:Complete graph K3.svg|<math>K_3</math>
Image:Complete graph K4.svg|<math>K_4</math>
Image:Complete graph K5.svg|<math>K_5</math>
Image:Complete graph K6.svg|<math>K_6</math>
Image:Complete graph K7.svg|<math>K_7</math>
Image:Complete graph K8.svg|<math>K_8</math>
</gallery>
</center>
[[categoria:Teoria de grafos|Grafo completo]]
| |||