5.1.1 Tipos de grafos

 

• Grafo simple: Se dice que el grafo G = (V, E) es un grafo simple de grado n si todos sus vértices tienen grado n. 
  
  
• Grafo completo: Un grafo es completo si cada par de vértices está unido por una arista. Se denota por Kn al grafo completo de n vértices.

  
• Grafo bipartido: Un grafo es bipartido si V=V1?V2 y cada arista de E une un vértice de V1 y otro de V2. 

  
• Grafo bipartido completo: Un grafo es bipartido completo si V=V1?V2 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, donde V1 tiene r vértices y V2 tiene s vértices.

  
• Grafos planos: Un grafo plano es aquel que puede ser dibujado en el plano sin que ninguna arista se interseca. 

  
• Grafos conexos: Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde "a" hacia "b".

  
• • Grafo ponderado: Un grafo es ponderado si presenta los pesos de cada arista y se puede determinar la longitud de una ruta, la cual es la suma de todos los pesos de las aristas.