Grafos

¿Qué es un Grafo?

Es un conjunto de puntos (NODOS o VÉRTICES) unidos por líneas (ARCOS o ARISTAS)

Son estructuras de datos que permiten representar diferentes tipos de relaciones entre los objetos, compuesta por vértices (nodos) y arcos (aristas).

 GENERALIDADES

• Son estructuras de datos
• Conjunto de nodos, vértices, arcos , aristas
• Son usados en diferentes campos
• Se utilizan en el manejo de redes, en la construcción de circuitos eléctricos, estrategias de ventas, economía, cartografía, transporte.

GRAFOS DIRIGIDOS

Los grafos dirigidos indican que los arcos o aristas poseen dirección

Ejemplos

ADYACENCIA

Se dice que hay adyacencia entre dos vértices si están unidos por 2 arcos.

A Y B son adyacentes

A Y C son adyacentes

B Y A son adyacentes

INCIDENCIA

Los arcos inciden en los vértices, incide si una de sus puntas llega a ese vértice 

Ejemplo:

El arco a incide en A Y B

Como observamos en el ejemplo de arriba  el arco es incidente en B porque vemos es la única dirección hacia la que esta apuntando.

COMPONENTES CONECTADOS SEPARADAMENTE

Estos pueden tener varios componentes separados 

Ejemplo:

Grafos y dígrafos fuertemente conectados

Si es de cualquier vértice se puede llegar a los demás

CAMINO SIMPLE

Si partiendo de cualquier vértice podemos recorrer toda la estructura sin repetir  vértices ni arcos.

GRAFO EULERIANO

Si partiendo de cualquier vértice podemos recorrer todo los arcos llegando el nuevo al Vértice origen

Se pueden visitar los vértices cuantas veces sea necesario, los arcos de pueden recorrer sólo una vez.

Grafo Hamiltoniano

Si partiendo de cualquier vértice podemos recorrer todas las vértices sin repetir ninguno y finalmente llegar al mismo vértice origen.

Los arcos se pueden recorrer una o más veces 

ORDEN DE UN GRAFO

Es el número de vértices que posee un grafo

GRADOS DE UN GRAFO

Es el número de arcos que inciden en ese vértice

Grado en F =  4

Grado en G = 4

Grado en E =  2

Grado en C = 2

Grado en H = 4

y así sucesivamente.

GRAFOS REGULARES

Se dice que es regular si todos los vértices tienen el mismo grado

ARCO CÍCLICO

Es Cíclico si parte de un vértice y llega al mismo

MULTIGRAFO

Es una estructura donde los vértices están unidos por más de un arco

GRAFO COMPLETO

Es complemento si cada vértice tiene un grado igual a N-1, donde n es el número de vértices que componen el grafo.

n = 5 vertices
n-1 = 4 grado

GRAFO SIMÉTRICO

Se dice que es simétrico si al doblar la matriz por  la diagonal los ceros coinciden

LISTA DE ADYACENCIA

Almacena por cada vértice la lista de adjuntos desde otros vértices

Con la estructura podemos calcular fácilmente el grado de entradas de cualquier vértice solamente contando el número de nodos de la lista de vértice requerido

 MATRIZ DE ADYACENCIA

Todo grafo simple puede ser representado por una matriz, que llamamos matriz de adyacencia.

Se trata de una matriz cuadrada de N filas X°n  columnas (siendo N el número de vértices del grafo).

Para construir la matriz de adyacencia, cada elemento  vale {{1}} cuando haya una arista que una los vértices  y . En caso contrario el elemento  vale 0.

La matriz de adyacencia, por tanto, estará formada por ceros y unos.

Matriz de caminos

• Para saber cuantos caminos de longitud M existen entre cualquier vertice y todos los demas.
• Se parte de la matriz de adyacencia(grafo, digrafo).