CLASIFICACIÓN DE LOS GRAFOS

Multigrafo: Es un grafo no orientado con múltiples aristas entre pares de nodos.

Grafo simple: Es un grafo sin bucles, sin múltiples aristas entre pares de vértices.

Grafo completo Para todo par de vértices de G, existe por lo menos una arista que los une. Por lo tanto, un grafo completo de n vértices es aquel que tiene sus n vértices mutuamente adyacentes. n-clique, es un grafo completo simple de n vértices. Se nota Kn.

Subgrafo de G = (X,U) engendrado por el conjunto A ⊂ X, es un grafo cuyos vértices pertenecen al conjunto A y cuyas aristas son aquellas de G que tienen las dos extremidades en A. 

Grafo parcial de G = (X,U) engendrado por V ⊂ U, es el grafo G' = (X,V) cuyos vértices son los mismos de G y cuyas aristas son las que conforman el conjunto V ⊂ U. 

Subgrafo parcial de G, es un subgrafo de un grafo parcial de G

Grafo bipartito: Es un grafo cuyo conjunto de vértices puede ser particionado en dos clases X1 y X2 de tal forma que dos vértices de la misma clase no sean jamás adyacentes. Se nota G = (X1,X2,U)

Grafo bipartito completo, es aquel en el que para todo elemento de X1 y todo elemento de X2 existe por lo menos un arco que los liga.

Un grafo simple bipartito completo con p elementos en X1 y q elementos en X2 se nota Kp,q.

Grafo Regular: es aquel en el que todos sus vértices tienen el mismo grado.

Grafo Ponderado G = (X, U, W) donde (X, U,) es un grafo y W es una función W: U → Z+ (Z+: enteros positivos) . Si u ∈ U, w(u) es llamado el peso de la arista u. Estos pesos corresponden, según la aplicación, a costos, capacidades u otras propiedades de las aristas o arcos. Cuando se desea asignar valores negativos o reales a los pesos de las aristas, se debe tener especial cuidado en la elección de los algoritmos ya que la correctitud de los mismos puede depender de la restricción a Z+.

Grafo Conexo: es aquel en el que para cada par de vértices de G, existe una cadena que los une. En grafos orientados se definen 2 conceptos:

1.  Débilmente conexo: si existe una cadena (sin tener en cuenta la orientación) que une cada par de nodos distintos. 
2.  Fuertemente conexo: si para cada par ordenado de nodos x e y, existe un camino que va de x a y. 

Una componente conexa de un grafo G, es un subgrafo de G engendrado por los vértices que pueden unirse a un vértice xi dado, mediante una cadena (puede ser todo el grafo G).

Cibergrafía:

https://www.fing.edu.uy/inco/grupos/bioinf/bioinfo1/teorico/grafos.pdf