TIPOS DE GRAFOS

DEFINIMOS: Se dice que el grafo G = (V, E) es:


a)      un grafo regular de grado n si todos sus vértices tienen grado n.

 

Grafos regulares de grado 2.

 

Grafos regulares de grado 3.

b)      un grafo completo si cada par de vértices está unido por una arista. Se denota por K_n al grafo completo de n vértices

 

c)      un ciclo si V = {v₁, v₂, . . . v_n},  n³> 3, y  E = {(v₁, v₂), (v₂, v₃), . . . , (v_n, v₁)}. Se denota por C_n al ciclo de n vértices

 

d)      una rueda si V = {v₀, v1, v₂, . . . v_n}, n n> 3, y E = {(v₁, v₂), (v₂, v₃), . . . , (v_n, v₁), {(v₁, v₀), (v₂, v₀), . . . , (v_n, v₀) }. Se denota por W_n a la rueda de n+1 vértices

 

e)      un cubo si sus vértices y aristas están relacionados como los de un cubo n-dimensional. Se denota por Q_n al cubo asociado al cubo n-dimensional.

 

f)        un grafo bipartido si V=V₁UV₂ y cada arista de E une un vértice de V₁ y otro de V₂

 

_{g)      un grafo bipartido completo si V=V1UV2 y dos vértices de V están unidos por una arista de E si y solo si un vértice está en V1 y el otro en V2. Se denota por Kr,s al grafo bipartido completo donde V1 tiene r vértices y V2 tiene s vértices}