Grafos
Páginas: 22 (5426 palabras)
Publicado: 8 de septiembre de 2010
CAPÍTULO 3
CONCEPTOS BÁSICOS DE GRAFOS Y REDES
3 Grafos Dirigidos
Un grafo dirigido G=(N,A) consiste en un conjunto N de nodos y un conjunto A de arcos cuyos elementos son pares ordenados de distintos nodos.
4 Red Dirigida
Una red dirigida es un grafo dirigido cuyos nodos o arcos tienen asociadosvalores numéricos tales como costos, capacidades, ofertas, demandas, tiempo etc. Denotaremos el número de nodos con la letra n y al número de arcos con la m.
1. Grafos no Dirigidos
Un grafo no dirigido G=(N,A) consiste en un conjunto N de nodos y un conjunto A de arcos cuyos elementos son pares no ordenados de nodos distintos. En un grafo nos podemos referir al arco queune a los nodos i-j, como [pic] o [pic]. Un grafo no dirigido permite el flujo en ambas direcciones, es decir desde el nodo i al nodo j o viceversa.
1 Colas y Cabezas
Un arco dirigido [pic] tiene dos puntos de finalización i y j. Nos referiremos al nodo i como la cola del arco y al nodo j como su cabeza. Diremos que al arco [pic] emana del nodo i y termina en el nodo j.El arco [pic] es incidente a los nodos i y j.
El arco [pic] es un arco saliente del nodo i y un arco entrante al nodo j. Siempre que el arco [pic] pertenezca al conjunto A, diremos que el nodo j es adyacente al nodo i.
2 Grados
El grado interno de un nodo es el número de arcos que llegan al nodo y su grado externo es el número de arcos que salen del nodo. Alsumar el grado interno de un nodo con su grado externo se obtiene el grado del nodo. Se observa que la suma de los grado interno de todos los nodos es igual a la suma de todos los grados externos de todos los nodos y ambos son iguales al número de arcos m en la red.
3 Lista de Adyacencia
La lista de arcos de adyacencia A(i) de un nodo i es el conjuntode arcos que emanan del nodo i, esto es:
[pic]
La lista de nodos de adyacencia A(i), de un nodo i es el conjunto de nodos adyacentes al nodo i.
[pic]
Supondremos que los arcos en la lista de adyacencia están ordenados de manera que los nodos cabeza y los arcos están en orden creciente.
4 Multiarcos
Multiarcos son dos o más arcoscon los mismos nodos cabeza y
cola.
5 Lazos
Un lazo es un arco cuyo nodo cabeza es el mismo que su nodo cola.
6 Subgrafo
Un grafo G’=(N’,A’) es un subgrafo de G=(N,A) si N’[pic]N y A’[pic]A. Diremos que G’=(N’,A’) es el subgrafo de G inducido por N’ si A’ contiene cada arco de A con ambos puntos de finalización en N’. Un grafo G’=(N’,A’) es unsubgrafo de expansión de G=(N,A) si N’=N y A’[pic]A.
3.10. Camino
Un camino en un grafo dirigido G=(N,A) es un subgrafo de G que
satisface la propiedad que para todo k, donde 1[pic]k[pic]r-1, se tiene
que:
ak=[pic] [pic] A o ak=[pic] [pic] A.
3.11. Camino Dirigido
Un camino dirigido es una versión orientada de un camino, en elsentido de que para dos nodos consecutivos ik e ik+1 en el camino, se tiene que [pic] [pic]A.
3.12. Ruta
Una ruta es un camino sin repetición de nodos. Es posible particionar los arcos de un camino en dos grupos: los arcos que van hacia delante y los arcos que van hacia atrás. Un arco [pic] en el camino es un arco dirigido hacia delante si la ruta visita alnodo i antes de visitar al nodo j, de ser contrario es un arco que está dirigido hacia atrás.
3.13. Ruta Dirigida
Una ruta dirigida es un camino dirigido en el que no se repiten nodos. Dicho de otra forma en una ruta dirigida no existen arcos dirigidos hacia atrás. Resulta fácil almacenar una ruta en una
computadora definiendo un índice pred(j), para...
CONCEPTOS BÁSICOS DE GRAFOS Y REDES
3 Grafos Dirigidos
Un grafo dirigido G=(N,A) consiste en un conjunto N de nodos y un conjunto A de arcos cuyos elementos son pares ordenados de distintos nodos.
4 Red Dirigida
Una red dirigida es un grafo dirigido cuyos nodos o arcos tienen asociadosvalores numéricos tales como costos, capacidades, ofertas, demandas, tiempo etc. Denotaremos el número de nodos con la letra n y al número de arcos con la m.
1. Grafos no Dirigidos
Un grafo no dirigido G=(N,A) consiste en un conjunto N de nodos y un conjunto A de arcos cuyos elementos son pares no ordenados de nodos distintos. En un grafo nos podemos referir al arco queune a los nodos i-j, como [pic] o [pic]. Un grafo no dirigido permite el flujo en ambas direcciones, es decir desde el nodo i al nodo j o viceversa.
1 Colas y Cabezas
Un arco dirigido [pic] tiene dos puntos de finalización i y j. Nos referiremos al nodo i como la cola del arco y al nodo j como su cabeza. Diremos que al arco [pic] emana del nodo i y termina en el nodo j.El arco [pic] es incidente a los nodos i y j.
El arco [pic] es un arco saliente del nodo i y un arco entrante al nodo j. Siempre que el arco [pic] pertenezca al conjunto A, diremos que el nodo j es adyacente al nodo i.
2 Grados
El grado interno de un nodo es el número de arcos que llegan al nodo y su grado externo es el número de arcos que salen del nodo. Alsumar el grado interno de un nodo con su grado externo se obtiene el grado del nodo. Se observa que la suma de los grado interno de todos los nodos es igual a la suma de todos los grados externos de todos los nodos y ambos son iguales al número de arcos m en la red.
3 Lista de Adyacencia
La lista de arcos de adyacencia A(i) de un nodo i es el conjuntode arcos que emanan del nodo i, esto es:
[pic]
La lista de nodos de adyacencia A(i), de un nodo i es el conjunto de nodos adyacentes al nodo i.
[pic]
Supondremos que los arcos en la lista de adyacencia están ordenados de manera que los nodos cabeza y los arcos están en orden creciente.
4 Multiarcos
Multiarcos son dos o más arcoscon los mismos nodos cabeza y
cola.
5 Lazos
Un lazo es un arco cuyo nodo cabeza es el mismo que su nodo cola.
6 Subgrafo
Un grafo G’=(N’,A’) es un subgrafo de G=(N,A) si N’[pic]N y A’[pic]A. Diremos que G’=(N’,A’) es el subgrafo de G inducido por N’ si A’ contiene cada arco de A con ambos puntos de finalización en N’. Un grafo G’=(N’,A’) es unsubgrafo de expansión de G=(N,A) si N’=N y A’[pic]A.
3.10. Camino
Un camino en un grafo dirigido G=(N,A) es un subgrafo de G que
satisface la propiedad que para todo k, donde 1[pic]k[pic]r-1, se tiene
que:
ak=[pic] [pic] A o ak=[pic] [pic] A.
3.11. Camino Dirigido
Un camino dirigido es una versión orientada de un camino, en elsentido de que para dos nodos consecutivos ik e ik+1 en el camino, se tiene que [pic] [pic]A.
3.12. Ruta
Una ruta es un camino sin repetición de nodos. Es posible particionar los arcos de un camino en dos grupos: los arcos que van hacia delante y los arcos que van hacia atrás. Un arco [pic] en el camino es un arco dirigido hacia delante si la ruta visita alnodo i antes de visitar al nodo j, de ser contrario es un arco que está dirigido hacia atrás.
3.13. Ruta Dirigida
Una ruta dirigida es un camino dirigido en el que no se repiten nodos. Dicho de otra forma en una ruta dirigida no existen arcos dirigidos hacia atrás. Resulta fácil almacenar una ruta en una
computadora definiendo un índice pred(j), para...
Leer documento completo
Regístrate para leer el documento completo.