Ordem de grafos e grau de um vértice

Explicação

O grau ou valência de um vértice é o número de arestas que começam ou terminam nele. O lacete conta duas vezes, porque começa e termina no mesmo vértice.

Um grafo é regular quando todos os seus vértices têm o mesmo grau.

A ordem de um grafo é o número de vértices que o grafo tem.

Nota: A soma de todos os graus dos vértices é igual ao dobro do número de arestas.

Exemplo

	Grau de $\text{A}$ : $1$	Grau de $\text{E}$ : $1$
	Grau de $\text{B}$ : $2$	Grau de $\text{F}$ : $2$
	Grau de $\text{C}$ : $4$	Grau de $\text{G}$ : $0$
	Grau de $\text{D}$ : $4$

Neste caso, a ordem do grafo é $7$ .

Somando os graus dos vértices do grafo anterior, temos

$1+2+4+4+1+2+0=14$

Confirmamos que temos $7$ arestas, e que $7\times2=14$ .

Grafo completo

Um grafo completo é um grafo cujos vértices têm todos o mesmo grau e no qual cada vértice está ligado a todos os outros vértices do grafo.

Os grafos completos e simples são representados pela notação $\boldsymbol{K_n}$ , em que $n$ é a ordem do grafo.

Nota: O grau dos vértices de $K_n$ é $n-1$ .

Exemplo

Na figura, podes observar um grafo completo de ordem $5$ , em que cada vértice tem grau $4$ , e está ligado todos os outros vértices. Denotamos este grafo por $K_5$ .

Matemática Aplicada às Ciências Sociais; Modelos de grafos; 11º Ano; Ordem de grafos e grau de um vértice