Tipos de Grafos

Los grafos en primer lugar se pueden clasificar en:

Dirigidos y no Dirigidos: En un grafo dirigido cada arco está representado por un par ordenado de vértices, de forma que representan dos arcos diferentes. En un grafo no dirigido el par de vértices que representa un arco no está ordenado.

Tipos de Grafos

1. Grafos Simples: Un grafo es simple si a lo más existe una arista uniendo dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos. Un grafo que no es simple se denomina multígrafo.
2. Grafo Completo: Un grafo es completo si existen aristas uniendo todos los pares posibles de vértices. Es decir, todo par de vértices (a, b) debe tener una arista e que los une. El conjunto de los grafos completos es denominado usualmente K, siendo Kn el grafo completo de n vértices.
3. Grafo Regular: Aquel con el mismo grado en todos los vértices.
4. Grafo Bipartito: Es aquel con cuyos vértices pueden formarse dos conjuntos disjuntos de modo que no haya adyacencias entre vértices pertenecientes al mismo conjunto.
5. Grafo Nulo: Se dice que un grafo es nulo cuando los vértices que lo componen no están conectados, esto es, que son vértices aislado.
6. Grafos Isomorfos: Dos grafos son isomorfos cuando existe una correspondencia biunívoca (uno a uno), entre sus vértices de tal forma que dos de estos quedan unidos por una arista en común.
7. Grafos Platónicos: Son los Grafos formados por los vértices y aristas de los cinco sólidos regulares Sólidos Platónicos), a saber, el tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro.
8. Grafo conexo: Un grafo se puede definir como conexo si cualquier vértice V pertenece al conjunto de vértices y es alcanzable por algún otro.
9. Digrafo (o Grafo Dirigido): A un grafo dirigido se le puede definir como un grafo que contiene aristas dirigidas,
10. Grafo Trivial: En teoría de grafos, un grafo trivial es un grafo con 0 aristas, y 0 ó 1 vértices.
11. Grafo Plano: Es un grafo que puede ser dibujado en el plano sin que ninguna arista se cruce (una definición más formal puede ser que este grafo pueda ser "incrustado" en un plano).
12. Grafo Rueda: Es un grafo con n vértices que se forma conectando un único vértice a todos los vértices de un ciclo. 
13. Grafos Ponderados: Llamamos grafos ponderados a los grafos en los que se asigna un número a cada una de las aristas. Este número representa un peso para el recorrido a través de la arista.
14. Pseudografo: Es un conjunto de pares no ordenados de elementos. Es decir, un pseudografo es un grafo no dirigido que acepta bucles entre sus nodos.