Investigación De Grafos

INSTITUTO TECNOLOGICO DE SAN LUIS POTOSI, CAPITAL

Teoría de Grafos

6.1 Elementos y características de losgrafos.6.2 Representación de los grafos.6.3 Algoritmos de recorrido y búsqueda.6.4 Arboles.6.5 Redes.(teorema de flujo máximo, teorema de flujo mínimo, pareos y redes de Petri).6.6 Aplicaciones de grafos y árboles.

Profesor: Ing. Rafael de la Cruz Pérez

07/12/2014

Karla Josefina Saldivar González

Índice

6.1 Elementos y características de los grafos. 2 - 4

6.1.1 Componentes de un grafo (vértices, aristas, lazos, valencia)

6.1.2 Tipos de grafos (Simples, completos, bipartidos, planos, conexos, ponderados)

6.2 Representación de los grafos. 5 - 6

6.2.1 Matemática

6.2.2. Computacional

6.3 Algoritmos de recorrido y búsqueda. 7 - 8

6.3.1 El camino más corto

6.3.2. A lo ancho

6.3.3 En profundidad

6.4 Arboles. 8 - 13

6.4.1 Componentes (raíz, hoja, padre, hijo, descendientes, ancestros)

6.4.2 Propiedades

6.4.3 Clasificación (altura, número de nodos)

6.4.4 Árboles con peso

6.4.5 Recorrido de un árbol: Preorden,

Inorden, Postorden,

6.5 Redes. (Teorema de flujo máximo, teorema de flujo mínimo, pareos y redes de Petri) 13 - 14

6.6 Aplicaciones de grafos y árboles. 14 – 15

Conclusiones 15

Bibliografía 16 - 17

6.1 Elementos y características de los grafos.

Un grafo, G, es un par ordenado de V y A, donde V es el conjunto de vértices o nodos del grafo y A es un conjunto de pares de vértices, a estos también se les llama arcos o ejes del grafo. Un vértice puede tener 0 o más aristas, pero toda arista debe unir exactamente a dos vértices. Los grafos representan conjuntos de objetos que no tienen restricción de relación entre ellos. Un grafo puede representar varias cosas de la realidad cotidiana, tales como mapas de carreteras, vías férreas, circuitos eléctricos, etc. La notación G = A (V, A) se utiliza comúnmente para identificar un grafo. Los grafos se constituyen principalmente de dos partes: las aristas, vértices y los caminos que pueda contener el mismo grafo.

6.1.1 Componentes de un grafo (vértices, aristas, lazos, valencia).

Vértices.- Son los puntos o nodos con los que esta conformado un grafo. Llamaremos grado de un vértice al número de aristas de las que es extremo. Se dice que un vértice es `par' o `impar' según lo sea su grado.

• Vértices Adyacentes: si tenemos un par de vértices de un grafo (U, V) y si tenemos un arista que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice inicial y V el vértice adyacente.

• Vértice Aislado: Es un vértice de grado cero.

• Vértice Terminal: Es un vértice de grado 1.

Aristas.- Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos. Si la arista carece de dirección se denota indistintamente {a, b} o {b, a}, siendo a y b los vértices que une. Si {a, b} es una arista, a los vértices a y b se les llama sus extremos.

• Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen en el mismo vértice.

• Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son el mismo.

• Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo.

Lazo: es una arista cuyos extremos inciden sobre el mismo vértice.

Valencia de un vértice.- Es el numero de lados que salen o entran a un vértice. En el grafo anterior las valencias de los vértices son:

Valencia (a)=2 Valencia (b)=4 Valencia (c)=2 Valencia (d)=3

6.1.2 Tipos de grafos (Simples, completos, bipartidos, planos, conexos, ponderados).

Grafos simples.- Un grafo es simple si a lo más existe 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. Un grafo que no es simple se denomina multígrafo.

Grafo completo.- Un grafo es completo si existen aristas uniendo todos los pares posibles de vértices. Es decir, todo par de vértices (a, b) debe tener una arista e que los une. El conjunto de los grafos completos es denominado usualmente K, siendo Kn el grafo completo de n vértices. Un Kn, es decir, grafo completo de n vértices tiene exactamente n(n-1)/2 aristas.

La representación gráfica de los como los vértices de un polígono regular da cuenta de su peculiar estructura.

Grafos bipartitos.- Un grafo G es bipartito si puede expresarse como G = {V1 U V2, A} (es decir, sus vértices son la unión de dos grupos de vértices), bajo las siguientes condiciones:

 V1 y V2 son disjuntos y no vacíos.

 Cada arista de A une un vértice de V1 con uno de V2.

 No existen aristas uniendo dos elementos de V1; análogamente para V2.

Bajo estas condiciones, el grafo se considera bipartito, y puede describirse informalmente como el grafo que une o relaciona dos conjuntos de elementos diferentes, como aquellos resultantes de los ejercicios y puzzles en los que debe unirse un elemento de la columna A con un elemento de la columna B.

Grafos Planos.- Un grafo G es planar si admite una representación en el plano de tal forma que las aristas no se cortan, salvo en sus extremos. A dicha representación se le denomina grafo plano. Se dice que un grafo es plano si puede dibujarse en el plano de manera que ningún par de sus aristas se corte. A ese dibujo se le llama representación plana del grafo.

Grafo conexo.- Un grafo se dice que es conexo si cada par de sus vértices están conectados. Es decir,

G es conexo ⇐⇒∀u, v : ∃µ = [u, v]

En caso contrario, diremos que G es un grafo desconexo.

Grafos ponderados.- Llamamos grafos ponderados a los grafos en los que se asigna un numero a cada una de las aristas. Este número representa un peso para el recorrido a través de la arista. Este peso podrá indicar, por ejemplo, la distancia, el costo monetario o el tiempo invertido, entre otros.

Definimos la longitud de un camino en un grafo ponderado como la suma delos pesos de las aristas de ese camino.

6.2 Representación de los grafos.

Existen diferentes formas de representar un grafo (simple), además de la geométrica y muchos métodos para almacenarlos en una computadora. La estructura de datos usada depende de las características del grafo y el algoritmo usado para manipularlo. Entre las estructuras más sencillas y usadas se encuentran las listas y las matrices, aunque frecuentemente se usa una combinación de ambas. Las listas son preferidas en grafos dispersos porque tienen un eficiente uso de la memoria. Por otro lado, las matrices proveen acceso rápido, pero pueden consumir grandes cantidades de memoria.

Matriz de adyacencia

Dado un grafo G = (V, E) con n vértices {v1,..., vn} su matriz de adyacencia es la matriz de orden n×n, A (G)=(aij) donde aijes el número de aristas que unen los vértices vi y vj. La matriz de adyacencia de un grafo es simétrica. Si un vértice es aislado entonces la correspondiente fila (columna) esta compuesta sólo por ceros. Si el grafo es simple entonces la matriz de adyacencia contiene solo ceros y unos (matriz binaria) y la diagonal esta compuesta sólo por ceros.

Matriz de incidencia

Dado un grafo simple G = (V, E) con n=|V| vértices {v1, ..., vn} y m=|E| aristas {e1, ..., em}, su matriz de incidencia es la matriz de orden nxm, B(G)=(bij), donde bij=1 si vi es incidente con ej ybij=0 en caso contrario. La matriz de incidencia sólo contiene ceros y unos (matriz binaria). Como cada arista incide exactamente en dos vértices, cada columna tiene exactamente dos unos. El número de unos que aparece en cada fila es igual al grado

...