Clasificación de los grafos

Clasificación de los grafos

Grafos dirigidos y no dirigidos dependiendo del tipo de relación entre los vértices del grafo, se definen distintos tipos de grafos. Así se distinguen aristas dirigidas y no dirigidas:

Arista dirigida: es aquella que define un par ordenado de vértices (a,b), donde el primer vértice u es el origen de la arista y el segundo vértice v es el término (o vértice final). El par (a, b) ≠ (a, b).

Arista no dirigida: es aquella que define un par no ordenado de vértices (a, b), donde (a, b) = (a, b).

Grafo dirigido

Es aquel cuyas aristas son no dirigidas. Representan relaciones simétricas como relaciones de hermandad y colaboración, conexiones de transportes, etc.

Cada arco esta representado por un par ordenado de vertices, de forma que representan dos arcos diferentes.

En grafos dirigidos se impone un sentido a los enlaces. Cada arista del grafo dirigido incluye una flecha para indicar la dirección.

Grafo no dirigido

Es aquel cuyas aristas son dirigidas. Los grafos dirigidos suelen representar relaciones asimétricas como por ejemplo: relaciones de herencia, los vuelos entre ciudades, etc.

Los arcos en el grafo no tienen una dirección particular, es decir, son bidireccionales(pueden ser considerados un caso particular de los anteriores).

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.