Grafo completo

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Um grafo completo é um grafo simples em que todo vértice é adjacente a todos os outros vértices. O grafo completo de n vértices é frequentemente denotado por K_n.

Número de arestas[editar | editar código-fonte]

O grafo K_n tem {n \choose 2}=\frac{n(n-1)}{2} arestas (correspondendo a todas as possíveis escolhas de pares de vértices).

Planaridade[editar | editar código-fonte]

O teorema de Kuratowski tem como consequência que um grafo K_n é grafo planar se e somente se n\le 4.

Ver também[editar | editar código-fonte]

K_1: 0 arestas K_2: 1 aresta K_3: 3 arestas K_4: 6 arestas
Complete graph K1.svg Complete graph K2.svg Complete graph K3.svg Complete graph K4.svg
K_5: 10 arestas K_6: 15 arestas K_7: 21 arestas K_8: 28 arestas
4-simplex graph.svg 5-simplex graph.svg 6-simplex graph.svg 7-simplex graph.svg
K_9: 36 arestas K_{10}: 45 arestas K_{11}: 55 arestas K_{12}: 66 arestas
8-simplex graph.svg 9-simplex graph.svg 10-simplex graph.svg 11-simplex graph.svg