Grafos

Grafos

Consiste en un conjunto de vértice o nodos (v).[pic 1]

Son utilizados para representar redes de computadores, circuitos eléctricos etc.

Definición de Grafos

Un grafo G es un par (V,A) donde:

V = {V1, ..., Vn} es un conjunto de vértices.

A = {e1, ..., em} es un conjunto de aristas o arcos.

G(V,A): así se denota un grafo.

Los vértices se representan como puntos y las aristas como líneas entre vértices.

[pic 2]

Ejemplo:

• G = (V,A)
• V = {a,b,c,d} 
• A = {(a,b),(b,c),(a,c),(a,d),(d,b)}

Algunos usos de los grafos

• Redes.
• Ingeniería de Sistemas:

• Matemáticas Discretas.
• Inteligencia Artificial.
• Teoría de Compiladores.

• Ingeniería Industrial.
• Transportadoras:

• Ruta mínima.
• Ruta más rápida.
• Costo transporte.

Tipos de grafos

Grafos no Dirigidos

Es aquél en que los nodos están formados por arcos no apuntados no ordenados.

[pic 3]

Ejemplo: 

• V = {A,B,C,D}
• A = {(A,B),(A,D),(B,A),(B,C),(B,D),(C,B),(C,D),(D,A),(D,B),(D,C)}

 [pic 4]

Grafos Dirigidos

Son aquellos en el que los arcos están apuntando y ordenados.[pic 5]

Ejemplo:

• V = {1,2,3,4,5}
• A = {<1,2>,<1,3>,<2,3>,<2,5>,<3,1>,<3,4>,<3,5>,<5,4>}

[pic 6]

Terminología de los grafos

• Vértice adyacente: un nodo n es adyacente a un nodo m si hay un arco de m o n. es decir si forma un lado. Es decir, los que salen del vértice en el caso de los dirigidos.
• Grado de un vértice: es el número de aristas que contienen ese vértice (parten o llegan a ese vértice). Si grado(V) = 0, el vértice V está aislado.
• Grados dirigidos:

• Grado Entrante: número de arco que entran al vértice.
• Grado Saliente: número de arco que salen del vértice.
• Grado Total: la suma los entrantes con los salientes.

• Lazo o bucle: es una arista que conecta a un vértice consigo mismo.
• Trayectoria: son los vértices por los que hay que pasar para ir de un vértice I a un vértice J.
• Número de lados de un grafo:[pic 7]

• Para no dirigidos:[pic 8]
• Para dirigidos:

• Vértice adyacente: un nodo n es adyacente a un nodo m si hay un arco de m o n. es decir si forma un lado.[pic 9]

• A es con D y con B.
• A no es adyacente con C.
• C es adyacente con B y D
• B es adyacente con A , C y con D.

• Vértice adyacente: un nodo n es adyacente a un nodo m si hay un arco de m o n. es decir si forma un lado.[pic 10]

• 1 es adyacente 2 y 3.
• 1 no es adyacente con 
• 3 es adyacente con 1, 4 y 5.
• 2 es adyacente con 3 y 5.

• Grado de un vértice: es el número de aristas que contienen ese vértice (parten o llegan a ese vértice). Si grado(V) = 0, el vértice V está aislado.

• Grado Entrante:
• Grado Saliente:

• Lazo o bucle: es una arista que conecta a un vértice consigo mismo.

[pic 11]

• Trayectoria: son los vértices por los que hay que pasar para ir de un vértice I a un vértice J.
• ¿Para el grafo dos cual es el camino trayectoria para ir del 1 al 5?[pic 12]

• Trayectoria: son los vértices por los que hay que pasar para ir de un vértice I a un vértice J.
• ¿Para el grafo dos cual es el camino trayectoria para ir del 1 al 5?

• Respuesta: P(1,5) = {(1,2),(2,5)}

• ¿Qué otras rutas puede observar?

 [pic 13]

• Cuando de un vértice cualquiera i se puede llegar a un j:

• Dirigidos

• Grafo fuertemente conectado.

• No Dirigidos

• Grafo Conectado.

 [pic 14]

• Cuando de un vértice cualquiera i se puede llegar a un j:

• Grafo conectado:

• Para grafos NO dirigidos.

• Grafo fuertemente conectado:

• Para los dirigidos.

[pic 15]

• Cuando de un vértice cualquiera i se puede llegar a un j:

• Grafo conectado:

• Para grafos NO dirigidos.

• Grafo fuertemente conectado:

• Para los dirigidos.

 [pic 16]

• Cuando de un vértice cualquiera i se puede llegar a un j:

• Grafo conectado:

• Para grafos NO dirigidos.

• Grafo fuertemente conectado:

• Para los dirigidos.

 [pic 17]

• Grafo completo: si cada vértice es adyacente a todos los demás vértices del grafo. Un grafo completo de n vértices tendrá n (n -1) / 2 aristas.
• ¿Si un grafo está fuertemente conectado implica que está completo?
• ¿Si un grafo está completo estará fuertemente conectado?

[pic 18]

• Grafo completo: si cada vértice es adyacente a todos los demás vértices del grafo. Un grafo completo de n vértices tendrá n (n -1) / 2 aristas.
• ¿Si un grafo está fuertemente conectado implica que está completo?
• ¿Si un grafo está completo estará fuertemente conectado?

[pic 19]

Actividad

Número de lados de un grafo:[pic 20]

• Para no dirigidos:  
• Para dirigidos:

• Calcular el número de lados de un grafo:

• Para dirigidos:

Número de lados de un grafo:[pic 21]

• Para no dirigidos:
• Para dirigidos:[pic 22]

• Calcular el número de lados de un grafo:

• Para dirigidos: [pic 23]

Grafo Ponderado, Etiquetado o Valorado

Si las aristas del grafo tienen asignado un valor o peso, el cual debe ser un número no negativo. Cada camino tiene un peso total asociado, igual a la suma de los pesos de las aristas que lo conforman. [pic 24]

...