Grafos

 En matemáticas y en ciencias de la computación, la teoría de grafos estudia las propiedades de los grafos.

Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas (edges en inglés) que pueden ser orientados o no.

Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).

Complementos del Grafo

Tipos de Grafos

Un grafo dirigido o grafo orientado, es un tipo de grafo en el cual el conjunto de las aristas tiene una dirección definida, a diferencia del grafo generalizado, en el cual la dirección puede estar especificada o no.

Grafo simple o simplemente grafo es aquel que acepta una sola 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. Es la definición estándar de un grafo. No contiene aristas paralelas, lazos ni aristas dirigidos.

Un grafo se dice conexo si, para cualquier par de vértices a y b en G, existe al menos una trayectoria (una sucesión de vértices adyacentes que no repita vértices) de a a b.

Matriz de Adyacencia

Una de las maneras más fáciles de implementar un grafo es usar una matriz bidimensional. En esta implementación de matriz, cada una de las filas y columnas representa un vértice en el grafo. El valor que se almacena en la celda en la intersección de la fila X y la columna Y indica si hay una arista desde el vértice X al vértice Y.

Ejemplo

Ejercicio: