Grafos

Definiciones
Un grafo G es un par ordenado G = (V,E), donde:
* V es un conjunto de vértices o nodos, y
* E es un conjunto de arcos o aristas, que relacionan estos nodos.
Normalmente V sueleser finito. Muchos resultados importantes sobre grafos no son aplicables para grafos infinitos. Se llama orden de G a su número de vértices, | V | .
Lazos o bucles
Un lazo o bucle es una arista querelaciona al mismo nodo; es decir, una arista donde el nodo inicial y el nodo final coinciden.
Grafo no dirigido

Grafo no dirigido
Un 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 conjuntospertenecen al conjunto potencia de V de cardinalidad 2, el cual se denota por .
Grafo dirigido

Grafo dirigido
Un grafo dirigido o digrafo es un grafo G = (V,E) donde:
*
* es un conjunto depares ordenados de elementos de .
Dada una arista (a,b), a es su nodo inicial y b su nodo final.
Por definición, los grafos dirigidos no contienen bucles.
Un grafo mixto es aquel que se define conla capacidad de poder contener aristas dirigidas y no dirigidas. Tanto los grafos dirigidos como los no dirigidos son casos particulares de este.
Pseudografo
Un pseudografo es un grafo G = (V,E)donde:
*
* es un conjunto de pares no ordenados de elementos de .
Es decir, un pseudografo es un grafo no dirigido que acepta bucles en .
Pseudografo dirigido
Un pseudografo dirigido es ungrafo G = (V,E) donde:
*
* es un conjunto de pares ordenados y etiquetados de elementos de
Es decir, un pseudografo dirigido es un grafo dirigido que acepta bucles en .
Variantes sobre lasdefiniciones principales
Algunas aplicaciones requieren extensiones más generales a las dos propuestas clásicas de grafos. Aunque la definición original los permite, según la aplicación concreta...