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.
Componentes de un grafo.
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.
• Cruce: Son dos aristas que cruzan en un punto. 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.
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.
• Cruce: Son dos aristas que cruzan en un punto. 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.
Tipos de grafos
Podemos clasificar los grafos en dos grupos:
dirigidos y no dirigidos. En un grafo no dirigido el par de vértices que
representa un arco no está ordenado. Por lo tanto, los pares (v1, v2) y (v2,
v1) representan el mismo arco. En un grafo dirigido cada arco está representado
por un par ordenado de vértices, de forma que y representan dos arcos
diferentes.
Ejemplo:
G1 = (V1, A1)V1 = {1, 2, 3, 4} A1 = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}G2 = (V2, A2)V2 = {1, 2, 3, 4, 5, 6} A2 = {(1, 2), (1, 3), (2, 4), (2, 5), (3, 6)}G3 = (V3, A3)V3 = {1, 2, 3} A3 = { <1, 2>, <2, 1>, <2, 3> }
Gráficamente estas tres estructuras de vértices y arcos se pueden representar de la siguiente manera:
Representación de grafos
• 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.
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 del vértice correspondiente. Una fila compuesta sólo por ceros corresponde a un vértice aislado.
Representación Matemática de los grafos
En matemáticas y ciencias de la computación, la
teoría de grafos, también llamada teoría de loas graficas estudia las
propiedades de los grafos (también llamados graficas) Un grafo es un conjunto,
no vacío, de objetos llamados vértices (o nodos) y una selección de partes de
vértices llamados aristas.
Representación Computacional de los grafos
Existen diferentes formas de almacenar grafos en una computadora. La estructura de datos, usada depende de las características del grafo y el algoritmo usado para manipularlo. Entre las estructuras mas sencillas y usadas se encuentran las listas y las matrices y aunque frecuentemente se usa una combinación de ambos.
Algoritmos de recorrido y búsqueda
Algoritmos de recorrido y búsqueda El
camino más corto
El problema de los caminos más cortos es el
problema que consiste en encontrar un camino entre dos vértices (o nodos) de
tal manera que la suma de los pesos de las aristas que lo constituyen es
mínima. Ahora bien, podemos emplear el algoritmo de Dijkstra para éstos casos,
los pasos o procedimientos a seguir para éste algoritmo son los siguientes:
Teniendo un grafo dirigido ponderado de N nodos no aislados, sea x el nodo
inicial, un vector D de tamaño N guardará al final del algoritmo las distancias
desde x al resto de los nodos.
1. Inicializar todas las distancias en D con un valor infinito relativo ya que son desconocidas al principio, exceptuando la de x que se debe colocar en 0 debido a que la distancia de x a x sería 0.
2. Sea a = x (tomamos a como nodo actual).
3. Recorremos todos los nodos adyacentes de a, excepto los nodos marcados, llamaremos a estos vi
4. Si la distancia desde x hasta va guardada en D es mayor que la distancia desde x hasta a, sumada a la distancia desde a hasta vi; esta se sustituye con la segunda nombrada.
5. Marcamos como completo el nodo a.
6. Tomamos como próximo nodo actual el de menor valor en D (puede hacerse almacenándolos valores en una cola de prioridad) y volvemos al paso 3 mientras existan nodos no marcados.
1. Inicializar todas las distancias en D con un valor infinito relativo ya que son desconocidas al principio, exceptuando la de x que se debe colocar en 0 debido a que la distancia de x a x sería 0.
2. Sea a = x (tomamos a como nodo actual).
3. Recorremos todos los nodos adyacentes de a, excepto los nodos marcados, llamaremos a estos vi
4. Si la distancia desde x hasta va guardada en D es mayor que la distancia desde x hasta a, sumada a la distancia desde a hasta vi; esta se sustituye con la segunda nombrada.
5. Marcamos como completo el nodo a.
6. Tomamos como próximo nodo actual el de menor valor en D (puede hacerse almacenándolos valores en una cola de prioridad) y volvemos al paso 3 mientras existan nodos no marcados.
Algoritmos de recorrido y búsqueda A lo ancho
La búsqueda en anchura es otro procedimiento para
visitar sistemáticamente todos los vértices de un grafo. Es adecuado
especialmente para resolver problemas de optimización, en los que se deba
elegir la mejor solución entre varias posibles. Al igual que en la búsqueda en
profundidad se comienza en un vértice v (la raíz) que es el primer vértice
activo. En el siguiente paso se etiquetan como visitados todos los vecinos del
vértice activo que no han sido etiquetados. Se continúa etiquetando todos los
vecinos de los hijos de v (que no hayan sido visitados aún). En este proceso
nunca se visita un vértice dos veces por lo que se construye un grafo sin
ciclos, que será un árbol
Algoritmos de recorrido y búsqueda En
profundidad
En la búsqueda en profundidad se avanza de vértice
en vértice, marcando cada vértice visitado. La búsqueda siempre avanza hacia un
vértice no marcado, internándose “profundamente” en el grafo sin repetir ningún
vértice. Cuando se alcanza un vértice cuyos vecinos han sido marcados, se
retrocede al anterior vértice visitado y se avanza desde éste.
----------------------------------------------------------------------------------------------------------
REFERENCIAS:
(24 de 11 de 2012). Obtenido de
http://mdiscretas.blogcindario.com/ficheros/paginawebm_discretas/unidad6.html
