GrafoInformalmente, un grafo es un conjunto de objetos llamados vrtices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto.Tpicamente, un grafo se representa grficamente como un conjunto de puntos (vrtices o nodos) unidos por lneas (aristas).Desde un punto de vista prctico, los grafos permiten estudiar las interrelaciones entre unidades que interactan unas con otras. Por ejemplo, una red de computadoras puede representarse y estudiarse mediante un grafo, en el cual los vrtices representan terminales y las aristas representan conexiones (las cuales, a su vez, pueden ser cables o conexiones inalmbricas).Lazos o bucles Un lazo o bucle es una arista que relaciona al mismo nodo; es decir, una arista donde el nodo inicial y el nodo final coinciden.Grafo no dirigido Grafo no dirigidoUn grafo no dirigido o grafo propiamente dicho es un grafo G = (V,E) donde: es un conjunto de pares no ordenados de elementos de .Un par no ordenado es un conjunto de la forma {a,b}, de manera que {a,b} = {b,a}. Para los grafos, estos conjuntos pertenecen al conjunto potencia de V de cardinalidad 2, el cual se denota por .Grafo dirigido Grafo dirigidoUn grafo dirigido o digrafo es un grafo G = (V,E) donde: es un conjunto de pares ordenados de elementos de .Dada una arista (a,b), a es su nodo inicial y b su nodo final.

Por definicin, los grafos dirigidos no contienen bucles.

Un grafo mixto es aquel que se define con la capacidad de poder contener aristas dirigidas y no dirigidas. Tanto los grafos dirigidos como los no dirigidos son casos particulares de este.