GRAFO: Conjunto de vértices (V) unidos entre si mediante enlaces, aristas o arcos (A), G=(V,A).
- No dirigidos: Las uniones son aristas, sin sentido definido (equivalente a un segmento). Funcionan para ambas direcciones.
- Dirigidos: Las uniones son arcos, con sentido definido, representado con una flecha (equivalente a un vector). Si en un grafo dirigido ignoramos la dirección de los arcos obtenemos en grafo no dirigido asociado.
- Mixto: Contiene tanto aristas como arcos.
- Simple: Sin bucles (union de un vértice consigo mismo), y sin más de una arista (o más de un arco en el mismo sentido) que unan el mismo par de vértices.
- Multigrafo: Grafo que no es simple.
- Completo: Con al menos una arista (o un arco para cada uno de los sentidos) uniendo cada par de vértices.
- Incompleto: Un grafo que no es completo. Si no hay ninguna unión el grafo se llama vacío.
- Bipartido: Los vértices pueden dividirse en dos conjuntos (por ejemplo X e Y) y los enlaces siempre unen un vértice de X con uno de Y. Un grafo dirigido es bipartido si lo es su grafo no dirigido asociado.
- Regular: De cada vértice parte el mismo número de aristas. Si son dirigidos se cuentan las aristas que entran y salen.
ESPECIFICACIONES:
Un grafo completo, no dirigido y simple se denomina Kn, siendo n el número de vértices
Los extremos (vértices) de un enlace (arista o arco) son incidentes a ese enlace
Dos vértices incidentes al mismo enlace son adyacentes entre sí.
En un grafo simple, un enlace queda definido por los vértices a los que une
Un grafo regular se representa como n-regular, siendo n el numero de enlaces con los que cada vértice es incidente.