• Author / Uploaded
• adan_enrique

Citation preview

Grafos CONCEPTOS BÁSICOS

Grafo  Es un conjunto de puntos (vértices o nodos) en el

espacio, que están conectados por un conjunto de líneas (aristas o arcos).  G = (V, E)

Elementos  Un nodo o vértice es la unidad fundamental de los

que esta formado un grafo, se representa con puntos o círculos.  Una arista o arco es la relación o corresponde a la

relación entre dos vértices.

Grafo No Dirigido  Se compone de dos conjuntos finitos, el conjunto de

nodos V = (v1, v2, …), que contiene el conjunto de nodos de G; y el conjunto de aristas E = (e1, e2, …), que es un conjunto de pares no ordenados de nodos diferentes de G.  G = (V, E)

Nodos Adyacente  Si dos nodos son unidos por una arista se dice que

son adyacentes o el nodo A es adyacente al nodo B.  G = (V, E) B A

D C

Nodos Adyacente  Si dos nodos son unidos por una arista se dice que

son adyacentes o el nodo A es adyacente al nodo B  G = (V, E) Además se dice que Ese enlace es incidente En A y en B.

B A

D C

Dado que son pares no ordenados (A,B) y (B,A) representan la misma arista.

Bucle  Es una arista que conecta al mismo nodo. En los

grafos no dirigidos no es posible un bucles.

B A

D C

Grado de un Nodo  En un grafo no dirigido viene dado por el numero de

aristas incidentes en un nodo. 2 3

B A

3 D

2 C

Ejercicio  El grafo dirigido G = (V,E) con conjunto de nodos  

 

V=(v1,v2,v3,v4) y el conjunto de aristas E=(e1=(v1,v4), e2=(v1,v4), v3 v2 e3=(v1,v3), e3 e4 e2 e4=(v3,v4)) v1

v4 e1

Grafo Dirigido  Consiste en un conjunto de nodos y un conjunto de

aristas. Sin embargo, en estos grafos las aristas consisten en pares ordenados de nodos de V.  Es decir, la dirección de la arista es importante v2 e2

En arista e=(u,v) se dice que es incidente desde el nodo u e incidente hacia v.

e4 e1

v1

v3 e3

También se dice que v es adyacente hacia u y u es adyacente desde v

Grados de nodos  En un grafo dirigido se dice que es:  Grado de salida de un nodo al numero de aristas que son incidentes desde el. 

Grado de entrada es el numero de aristas incidentes hacia el.



Grado del nodo se define como la suma del grado de entrada y del grado de salida.

Ejercicio  Determinar los grados de entrada para cada uno de

los nodos, los de salida y el grado del nodo. Y representarlo v2

e1

e4 E2

v1

v3 e3

Grafo Valorado  Al usar grafos dirigidos o no dirigidos para modelar

ciertas relaciones, a menudo resulta útil asociar un peso a cada arista.  Para esto se usa w(u,v), para denotar peso asociado a la arista (u,v).

Tarea  Describir:  Paseo  Paseo cerrado  Paseo abierto  Paseo simple  Camino  Camino accesible  Circuito  Ciclo  A cíclico

Paseo  Se define como una secuencia alternada de nodos y

aristas, comenzando y terminando con nodos, tal que cada arista es incidente en los nodos que la preceden y la siguen.

Paseo  Paseo cerrado: Comienza y termina en el mismo

nodo.  Paseo abierto: Paseo que no esta cerrado.  Paseo simple: Es en el cual no se repite ninguna

arista.  Camino: No se repite ningún nodo.

Camino  Si hay un camino desde el nodo u hasta el nodo v,

entonces se dice que v es accesible desde u. se escribe u v

Circuito  Circuito: Es un paseo simple cerrado.  Ciclo: Circuito cuyos nodos son diferentes, solo el

primero y ultimo se excluyen.  Acíclico: Grafo sin ciclos.

Grafo conexo  Conexo: Es un grafo donde existe al menos un

camino entre cada par de nodos.

 Fuertemente conexo: si cualquiera dos nodos del

grafo dirigido son accesibles el uno del otro.

Aplicación  Se utilizan para estudiar los problemas que surgen

de una gran variedad de áreas de aplicación incluyendo la ciencia informática, ingeniería eléctrica, química, investigación, política, economía, etc.

Aplicación  Estructuras físicas mas

fáciles de modelar son aquellas que pueden concebirse como redes.  Como las redes de comunicaciones, circuitos eléctricos, redes de interconexión de computadoras, etc.  Por ejemplo una colección de redes de gente, computadoras o cualquier otra entidad que sean capaces de comunicarse.

Aplicación  Para modelar una red como grafo se representa cada

miembro como un nodo y se dibuja una arista dirigida entre dos nodos si es posible comunicar directamente entre sus correspondientes miembros.

Aplicación  Ejemplos:  Una red de transportes donde cada punto o nodo representa una ciudad o almacén. 

Tareas que se necesitan completar para realizar algún trabajo

Determinar caminos  Para grafos no valorados se busca pasar por el menos

numero de nodos hasta llegar al nodo destino.  En grafos valorados se busca el camino mas barato o

que recorra aristas con menos pesos.

Ejemplo

v1 v7

v4

v6 v5 v9 v2

v8

v10

v3

Representación de Grafos  Para resolver un problema con grafos utilizando una

computadora, debemos ser capaces de almacenar grafos en la memoria de la computadora. Así que se representan como una estructura de datos. 

Matriz de Adyacencia



Lista de Adyacencia

Matriz de Adyacencia  Es una matriz que usa los nodos como filas y como

columnas, y se representan las relaciones entre ellos por medio de un 1 en la intersección y cero si no existe relación. v1

v4

v5

v2

v3

1

2

3

4

5

1

0

1

0

1

0

2

1

0

0

0

1

3

0

0

0

0

1

4

1

0

0

0

1

5

0

1

1

1

0

Lista de Adyacencia  Enlista cada nodo y señala con que nodo esta

relacionado. v1

v4

v5

v2

v3

Búsquedas  Para resolver cualquier casi problema de grafos se

requiere el examen de todas las aristas y los nodos en un grafo. 

Búsqueda en Profundidad



Búsqueda en Anchura

Búsqueda en profundidad  Es un algoritmo que permite recorrer todos los

nodos de un grafo o árbol de manera ordenada, pero no uniforme. Su funcionamiento consiste en ir expandiendo todos y cada uno de los nodos que va localizando, de forma recurrente, en un camino concreto. Cuando ya no quedan mas nodos que visitar en dicho camino regresa de modo que repite el mismo proceso con cada uno de los hermanos del nodo ya procesado.

Búsqueda en Anchura  Es un algoritmo de búsqueda que recorre todos los

nodos de un árbol o grafo de manera uniforme. Expande cada uno de los nodos de un nivel antes de continuar con el siguiente.

TAREA REALIZAR ACTIVIDAD #8