Grafos
daya
27 de Enero del 2004
Necesito que me ayudes con la programacion de cualquier algoritmo en grafo
katthy
27 de Enero del 2004
Programación no numérica - Grafos
Definición de grafo:
Desafortunadamente no existe una terminología estandarizada en la teoría de los grafos, por lo tanto es oportuno aclarar que las presentes definiciones pueden variar ligeramente entre diferentes publicaciones de estructura de datos y de teoría de grafos, pero en general se puede decir que un grafo como indica su nombre lo indica es la representación (para nuestro caso) gráfica de los datos de una situación particular, ejemplo:
Los datos contienen, en algunos casos, relaciones entre ellos que no es necesariamente jerárquica. Por ejemplo, supongamos que unas líneas aéreas realizan vuelos entre las ciudades conectadas por líneas como se ve en la figura anterior (más adelante se presentaran grafos con estructuras de datos); la estructura de datos que refleja esta relación recibe el nombre de grafo.
Se suelen usar muchos nombres al referirnos a los elementos de una estructura de datos. Algunos de ellos son "elemento", "ítem", "asociación de ítems", "registro", "nodo" y "objeto". El nombre que se utiliza depende del tipo de estructura, el contexto en que usamos esa estructura y quien la utiliza.
En la mayoría de los textos de estructura de datos se utiliza el termino "registro" al hacer referencia a archivos y "nodo" cuando se usan listas enlazadas, arboles y grafos.
También un grafo es una terna G = (V,A,j ), en donde V y A son conjuntos finitos, y j es una aplicación que hace corresponder a cada elemento de A un par de elementos de V. Los elementos de V y de A se llaman, respectivamente, "vértices" y "aristas" de G, y j asocia entonces a cada arista con sus dos vértices.
Esta definición da lugar a una representación gráfica, en donde cada vértice es un punto del plano, y cada arista es una línea que une a sus dos vértices.
Si el dibujo puede efectuarse sin que haya superposición de líneas, se dice que G es un grafo plano. Por ejemplo, el siguiente es un grafo plano:
puesto que es equivalente a este otro:
Representación de un grafo:
Existen dos formas de mantener un grafo "G" en la memoria de una computadora, una se llama Representación secuencial de G, la cual se basa en la matriz de adyacencia A; la otra forma, es la llamada Representación enlazada de G y se basa en listas enlazadas de vecinos. Independientemente de la forma en que se mantenga un grafo G en la memoria de una computadora, el grafo G normalmente se introduce en la computadora por su definición formal: Un conjunto de nodos y un conjunto de aristas
· Representación secuencial de un grafo:
Considere el grafo siguiente "G":
y suponga que los nodos se mantienen en memoria en un array DATOS tal como sigue:
DATOS: X, Y, Z, W
Para hallar la matriz de adyacencia A del grafo "G", tenemos que tomar en cuenta que los nodos están normalmente ordenados de acuerdo con la forma en que aparecen en memoria; o sea, asumimos que u 1 = X, u 2 = Y, u 3 = Z, y u 4 = W, la matriz de adyacencia A de G seria la siguiente:
aquí a i j = 1 si hay una arista u i a u j ; si no a i j = 0.
Así entonces para hallar la matriz de camino P de G mediante las potencias de la matriz de adyacencia A, como G tiene cuatro nodos se calcula
por lo tanto la matriz de caminos P se obtiene ahora haciendo pi j = 1 siempre que haya una entrada positiva en la matriz B4 . así
La matriz de caminos muestra que no hay camino de u 1 a u 2 de hecho, no hay camino de ningún nodo a u 1 por tanto, G no es fuertemente conexo.
· Representación enlazada de un grafo:
Un grafo "G" se guarda en memoria como sigue:
NODO A B E D C
SIG 7 4 0 6 8 0 2 3
ADY 1 2 5 7 9
1 2 3 4 5 6 7 8
PRINCIPIO = 1, NDISP = 5
DEST 2 6 4 6 7 4 4 6
ENL 10 3 6 0 0 0 0 4 0 0
1 2 3 4 5 6 7 8 9 10
ADISP = 8
Para dibujar el respectivo grafo "G", primero debemos buscar todos los vecinos de cada NODO[K] recorriendo su lista de adyacencia que tiene el puntero de adyacencia ADY[J]. Esto da como resultado:
A: 2(B) y 6(D)
B: 6(D), 4(E) y 7(C)
C: 4(E)
D: 4(E)
E: 6(D)
Entonces procedemos a dibujar el diagrama del grafo como sigue:
Sea G un grafo dirigido con m nodos. La representación secuencial de G en la memoria, o sea, la representación de G por su matriz de adyacencia A, tiene unas cuantas desventajas importantes.
En primer lugar, puede ser difícil insertar y eliminar nodos de G, esto es por que el tamaño de A debería ser cambiado y los nodos deberían ser reordenados, así que habría muchos cambios en la matriz A; más aun, si el numero de aristas es O(m) o O(m log2 m), entonces la matriz A estará desperdiciada (contendrá muchos ceros); por tanto, se desperdiciará una gran cantidad de espacio; entonces G normalmente se representa en memoria por una representación enlazada, también llamada estructura de adyacencia.
Considere el grafo G de la figura siguiente y su respectiva tabla de adyacencia, donde se muestra cada nodo de G seguido por la lista de nodos adyacentes, también llamados sucesores o vecinos.
Para apreciar aun más esta situación, podemos también usar un diagrama esquemático de la representación enlazada de G en la memoria, específicamente, la representación enlazada contendrá dos listas (o archivos), una lista de nodos NODO y una lista de aristas ARISTA, tal como sigue:
Cada elemento de la lista NODO corresponderá a un nodo de G y será un registro de la forma:
NODO SIG ADY
Aquí NODO será el nombre o valor clave del nodo, SIG será un puntero al siguiente nodo de la lista NODO y ADY será un puntero al primer elemento de la lista de adyacencia del nodo, que se mantiene en la lista ARISTA; el área restante indica que puede haber otra información en el registro, tal como el grado de entrada GraEnt del nodo, el grado de salida GraSal del nodo, el ESTADO del nodo durante la ejecución de un algoritmo, etc.
Adicional a esto, cada elemento de la lista ARISTA corresponderá a una arista de G y será un registro de la forma:
DEST ENL
Donde el campo DEST apuntará a la posición en la lista NODO del nodo destino o terminal de la arista, el campo ENL enlazará juntas las aristas con el mismo nodo inicial, o sea, los nodos con la misma lista de adyacencia, y el campo restante indica que puede existir otra información en el registro correspondiente a la arista, tal como un campo ARIS conteniendo los datos etiquetados de la arista cuando G es un grafo con etiquetas, un campo PESO conteniendo el peso de la arista cuando G es un grafo con peso, etc.
Técnicas básicas de búsqueda:
BÚSQUEDA EN GRAFOS
Para efectuar una búsqueda de los vértices de un grafo, se pueden emplear dos estrategias diferentes:
Búsqueda en profundidad (BEP): Se comienza en cualquier vértice y en cada paso se avanza a un nuevo vértice adyacente siempre que se pueda. Cuando todos los adyacentes a X hayan sido visitados, se retrocede al vértice desde el que se alcanzó X y se prosigue. Así se consigue etiquetar (visitar) todos los vértices de la componente conexa en que se encuentre el vértice inicial.
Esta técnica se utiliza cuando necesitamos encontrar respuesta a un problema sobre un grafo sin condiciones de optimización.
La idea en general de la búsqueda en profundidad comenzando en un nodo A es la siguiente:
Primero examinamos el nodo inicial A. Luego examinamos cada nodo N de un camino P que comience en A; a sea, procesamos un vecino de A, luego un vecino de un vecino de A y así sucesivamente, hasta llegar a un punto muerto o final del camino P, y de aquí volvemos atrás por P hasta que podamos continuar por otro camino P´ y así sucesivamente.
Este algoritmo es similar al del recorrido inorden de un árbol binario, y también a la forma en que se debe pasar a través de un laberinto. Observe que se hace uso una pila en lugar de una cola, y este es el detalle fundamental que hace la diferencia para realizar la búsqueda en profundidad.
Algoritmo para la búsqueda en profundidad:
Este algoritmo realiza la búsqueda en profundidad el grafo G comenzando en un nodo A.
1. Inicializar todos los nodos al estado de preparado (ESTADO=1)
2. Meter el nodo inicial A en la pila y cambiar su estado a estado de espera (ESTADO=2).
3. Repetir los pasos 4 y 5 hasta que la pila este vacia.
4. Sacar el nodo N en la cima de la pila. Procesar el nodo N y cambiar su
estado al de procesado (ESTADO=3).
5. Meter en la pila todos los vecinos de N que estén en estado de
preparados (ESTADO=1) y cambiar su estado a estado de espera
(ESTADO=2).
[ fin de bucle del paso 3 ]
6. Salir.
nota: tomado del libro Estructura de datos, serie schaum Mcgraw-Hill,
pagina: 337, capitulo: 8 Grafos y sus aplicaciones, autor: Seymour Lipschutz
Búsqueda en anchura (BEA): A diferencia con la BEP ahora se visitan todos los vecinos de un vértice antes de pasar al siguiente. Por tanto no hay necesidad de retroceder. Una vez etiquetados todos los vecinos de un vértice X, se continúa con el primer vértice alcanzado después de X en la búsqueda.
Esta técnica se utiliza para resolver problemas en los que se pide hallar una solución óptima entre varias.
En general la búsqueda en anchura comenzando de un nodo de partida A es la siguiente:
Primero examinamos el nodo de partida A.
Luego examinamos todos los vecinos de A. Luego examinamos todos los vecinos de los vecinos de A y así sucesivamente. Con el uso de una cola, garantizamos que ningún nodo sea procesado más de una vez y usando un campo ESTADO que nos indica el estado actual de los nodos.
Algoritmo para la búsqueda en anchura:
Este algoritmo realiza la búsqueda en anchura en un grafo G comenzando en un nodo de partida A.
1. Inicializar todos los nodos al estado de preparados (ESTADO=1).
2. Poner el nodo de partida A en la COLA y cambiar su estado a espera (ESTADO=2).
3. Repetir pasos 4 y 5 hasta que COLA esté vacía.
4. Quitar el nodo del principio de la cola, N. Procesar N y cambiar su
estado a procesado (ESTADO=3).
5. Añadir a COLA todos los vecinos de N que estén en estado de
preparados (ESTADO=1) y cambiar su estado al de espera
(ESTADO=2).
[ fin del bucle del paso 3 ]
6. Salir.
nota: tomado del libro Estructura de datos, serie schaum Mcgraw-Hill,
pagina: 334 - 335, capitulo: 8 Grafos y sus aplicaciones, autor: Seymour Lipschutz
Arboles de recubrimiento mínimo (búsqueda del camino más corto):
CAMINOS MINIMOS EN GRAFOS
Para lograr el propósito del recorrido mínimo dentro de un grafo G, es necesario para nuestro caso en particular (puesto que no es la única técnica existente) la utilización del algoritmo de WARSHALL para el camino mínimo, el cual se expresa de la forma siguiente:
Sea G un grafo con m nodos, u 1 , u 2 , ..., u m suponga que queremos encontrar la matriz de caminos P para el grafo G. WARSHALL dio un algoritmo para este propósito que es mucho más eficiente que calcular las potencias de la matriz de adyacencia A y aplicar la proposición:
donde sea A la matriz de adyacencia y P = Pij la matriz de caminos de un grafo G entonces, Pij = 1 si y solo sí hay un numero positivo en la entrada ij de la matriz
Este algoritmo de WARSHALL se usa para calcular el camino mínimo y existe un algoritmo similar para calcular el camino mínimo de G cuando G tiene peso.
Algoritmo de WARSHALL:
Un grafo dirigido G con M nodos está en memoria por su matriz adyacente A, este algoritmo encuentra la matriz de caminos (Booleana) P del grafo G.
1. [ Inicializar P ] repetir para I, J =1, 2, ... M:
si A[ I, J ]=0, entonces: hacer P[ I, J ]:=0;
si no: hacer P[ I, J ]:=1.
[ fin de bucle ]
2. [ Actualizar P ] repetir paso 3 y 4 para K=1, 2, ..., M:
3. repetir paso 4 para I=1, 2, ..., M:
4. repetir para J=1, 2, ..., M:
hacer P[ I, J ]:= P[ I, J ] V ( P[ I, J] ^ P[ K, J ]).
[ fin de bucle ]
[ fin de bucle paso 3 ]
[ fin de bucle paso 2 ]
5. Salir.
nota: tomado del libro Estructura de datos, serie schaum Mcgraw-Hill,
pagina: 322, capitulo: 8 Grafos y sus aplicaciones, autor: Seymour Lipschutz
Algoritmo de matriz de camino mínimo:
Cuando se trata de un grafo con peso G de M nodos está memoria mediante su matriz de peso W; este algoritmo encuentra la matriz Q tal que [ I, J ] es la longitud del camino mínimo del nodo VI al nodo VJ . INFINITO es un número muy grande y MIN es la función del valor mínimo.
1. [ Inicializar Q ] repetir para I, J=1, 2, . . ., M:
si W [ I, J ] = 0, entonces: hacer Q [ I, J ]:= INFINITO;
si no: hacer Q [ I, J ] := W [ I, J ].
[ fin de bucle ]
2. [ Actualizar Q ] repetir pasos 3 y 4 para K=1, 2, . . ., M:
3. repetir paso 4 para I = 1, 2, . . ., M:
4. repetir para J = 1, 2, . . ., M:
hacer Q [ i, J ] := MIN(Q [ i, J ]+ Q [ i, K ]+ Q [ K, J ]).
[ fin de bucle ]
[ fin de bucle del paso 3 ]
[ fin de bucle del paso 2 ]
5. Salir.
nota: tomado del libro Estructura de datos, serie schaum Mcgraw-Hill,
pagina: 324, capitulo: 8 Grafos y sus aplicaciones, autor: Seymour Lipschutz
Enunciado para ejemplo:
Dado un grafo simple no dirigido, conexo y ponderado de n nodos etiquetados con los números naturales desde el 1 hasta el n, se numeran los ejes desde 1 hasta m de acuerdo con el orden. Dados a continuación dos nodos cualesquiera, se trata de encontrar el camino más corto entre ambos nodos, utilizando el algoritmo de Dijkstra.
Entrada: En la primera línea, un número natural que indica el número de casos que se van a plantear. Para cada caso, una línea con el número de nodos n del grafo, y la representación decimal del mismo (entero menor que ) separados por un blanco. En la siguiente línea, separados por blancos, m números naturales que representan los pesos de los ejes del grafo. En la siguiente línea, otro número natural p nos dice cuantos pares de nodos se van a proponer, y a continuación aparecen en líneas diferentes y separados por blancos todas estas parejas.
Salida: Para cada uno de los casos propuestos, el fichero de salida contendrá una línea indicando el caso de que se trata en la forma Grafo # con el símbolo # sustituido por el número del caso. Las siguientes m líneas contendrán la lista de adyacencias del grafo en la forma:
No.delnodo Nodoadyacente pesodeleje Nodoadyacente Pesodeleje...
siempre separando con blancos y con los nodos adyacentes en orden creciente de número. A continuación, p líneas que resuelven las p parejas de nodos planteadas, componiendo cada línea en la forma:
Pesodelcamino... ...nodosintermedios... ...nodofinal...
Ejemplo de Entrada:
2
4 49
53 82 53
2
1 2
1 3
8 14728196
81 48 30 64 71 13 91 10 65
3
2 1
4 1
8 1
Ejemplo de Salida:
Grafo 1
1 2 53
2 1 53 4 82
3 4 53
4 2 82 3 53
53 1 2
188 1 2 4 3
Grafo 2
1 4 81
2 6 48 7 30 8 64
3 4 71 6 13
4 1 81 3 71 8 91
5 6 10 7 65
6 2 48 3 13 5 10
7 2 30 5 65
8 2 64 4 91
213 2 6 3 4 1
81 4 1
172 8 4 1
Algoritmo de Dijkstra: Este algoritmo construye el árbol de caminos de longitud mínima entre un vértice fijado V y los restantes vértices en un grafo ponderado.
Observaciones:
1. Los pesos de las aristas deben ser no negativos.
2. El algoritmo de Dijkstra NO proporciona un árbol generador mínimo.
Ordenación Topológica:
Hasta recientemente todos los trabajos sobre Topología (Digital principalmente) se basaban en un enfoque de Teoría de Grafos. Este enfoque presenta, sin embargo, el problema de determinar la relación de adyacencia más razonable en Zn. Actualmente existen enfoques alternativos basados en nociones de Topología General. En este caso haremos una introducción a algunos de estos enfoques.
Topología definición:
1) Rama de la matemática que estudia las propiedades del espacio que son invariantes por homeomorfismos. Se trata de propiedades no métricas, es decir, de propiedades cualitativas, y no cuantitativas, lo que la distingue de la geometría común. Se la suele denominar "geometría débil" o "geometría del caucho". Por ejemplo, una circunferencia es topológicamente equivalente a un cuadrado, por más que sus propiedades métricas sean diferentes
2) Una topología en un conjunto X es una familia de subconjuntos de X que satisface ciertos axiomas (ver espacio topológico).
En esta sección estudiaremos las diferentes estrategias que se han planteado principalmente motivadas por problemas en el área del reconocimiento de formas para dotar a la digitalización D de un conjunto, de una estructura, no necesariamente explícitamente topológica, en términos de la cual formular propiedades de D relacionadas con las propiedades de la imagen original.
Las imágenes 2-dimensionales son las mas ampliamente estudiadas, aunque últimamente las 3-dimensionales están siendo muy utilizadas. También se utilizan imágenes 4-dimensionales para representar imágenes 3-dimensionales en movimiento.
De las estrategias planteadas, la primera y las más utilizada es la introducida por Azriel Rosenfeld en 1970. Se basa en la noción de adyacencia entre puntos de Zn (además de Zn también considera en ocasiones los centros de una teselación del plano por hexágonos). Su enfoque descansa principalmente en nociones de Teoría de Grafos.
Desde entonces la Topología Digital ha proporcionado los fundamentos teóricos para importantes operaciones de procesamiento de imagen, como recuento de objetos, adelgazamiento de imágenes, detección de bordes y relleno de contornos. El adelgazamiento de imágenes es una operación de preprocesamiento en reconocimiento de formas. Su objetivo es reducir el conjunto de puntos de la imagen sin alterar la topología de la misma.
Ordenación topológica:
Suponga que S es un grafo tal que cada nodo vi de S representa una tarea y cada arista ( u, v ) significa que la finalización de la tarea u es un pre-requisito para que comience la tarea v. Suponga que tal grafo S contiene un ciclo tal que:
P=( u, v, w, u )
Esto significa que no podemos empezar v hasta completar u, no podemos empezar w hasta terminar v y no podemos empezar u hasta completar w. Así no podemos completar ninguna tarea del ciclo. Por tanto, un grafo S así, que representa tareas y relaciones de precedencia, no puede tener ciclos.
Ahora suponga que S es un grafo sin ciclos, considere la relación < sobre S definida como sigue:
u < v si existe un camino de u a v
Esta relación tiene las siguientes tres propiedades:
1. Para cada elemento u de S, tenemos que u < u. ( Irreflexivilidad )
2. Si u < v, entonces v < u. ( Asimetría )
3. Si u < v y v < w, entonces u < w. ( Transitividad )
Tal relación < sobre S se llama ordenación parcial de S, y S con tal ordenación se llama conjunto parcialmente ordenado o conjunto po. Así, un grafo S sin ciclos se puede considerar un conjunto parcialmente ordenado.
Por lo tanto, puede también suponer que si S es un conjunto parcialmente ordenado con la ordenación parcial denotada por <, entonces S se puede considerar un grafo cuyos nodos son los elementos de S y cuyas aristas están definidas como sigue:
( u, v ) es una arista en S si u < v
más aun, se puede demostrar que un conjunto S parcialmente ordenado, considerado como un grafo, no tiene ciclos.
Como ejemplo podemos plantear que: sea S el grafo de la figura, observe que S no tiene ciclos. Así S se puede considerar un conjunto parcialmente ordenado. Note que G < C, ya que existe un camino desde G hasta C. Similarmente, B < F y B < C. Por otro lado B no es menor que A, ya que no existe camino de B a A, al igual que A no es menor que B.
Por lo tanto; sea S un grafo dirigido sin ciclos (o conjunto parcialmente ordenado). Una ordenación topológica T de S es una ordenación lineal de los nodos de S que preserva la ordenación parcial de S original, o sea, que si u < v en S (si hay un camino de u a v en S), entonces u va delante de la v el la ordenación lineal T, este se muestra en la siguiente figura, donde se incluyen las aristas para indicar que concuerdan con la dirección de la ordenación lineal.
Información adicional sobre Topología:
Topología combinatoria:
Rama de la topología que reduce el estudio de curvas y superficies a ciertos esquemas determinados por polígonos curvilíneos, evitando de esta forma pensarlas como conjuntos de puntos, como lo hace la topología conjuntista. El tratamiento combinatorio es más cercano al álgebra, y reduce el concepto de homeomorfismo a unas pocas reglas que permiten decidir cuándo dos esquemas combinatorios son equivalentes.
Topología inducida:
Dado un subconjunto A de un espacio topológico X, se llama topología inducida a la topología definida en A que toma como abiertos a todos los conjuntos de la forma U Ç A, en donde U es un abierto de X. En estas condiciones, se dice que A es un subespacio de X.
Topología usual:
La topología usual del espacio n–dimensional (Rn) tiene como abiertos básicos a las bolas n–dimensionales (abiertas). Es decir, un conjunto de Rn es abierto si y sólo si es unión de cierto número de bolas abiertas. Equivalentemente, diremos que A es abierto si y sólo si para todo punto x Î A existe una bola B contenida en A tal que x Î B (A es entorno de x).
Toro:
Se llama así a la superficie de revolución engendrada por la rotación de una circunferencia en torno a un eje que no la toque en ninguno de sus puntos. Si bien esta definición es geométrica, las propiedades topológicas del toro son de gran importancia. En especial, la propiedad de tener un asa, o agujero, que determina que existan en el toro lazos no reducibles. Un importante teorema de la topología combinatoria asegura que toda superficie cerrada y orientable es un toro con n agujeros. El caso n = 0 corresponde obviamente a la esfera, si se la piensa como un "toro sin agujeros", y el caso n = 1 es el toro usual. Si bien la definición habitual del toro lo presenta como una superficie sumergida en el espacio tridimensional, es fácil ver que es homeomorfo al producto cartesiano de dos circunferencias, sumergido en R4 (espacio cuatridimensional). Es decir, la definición topológica del toro es: T2 = S1 ´ S1. Esto permite generalizar, y definir al toro n–dimensional como el producto cartesiano de n circunferencias, es decir: Tn = S1 ´ ... ´ S1.
En la topología combinatoria, el toro bidimensional se define identificando dos a dos los lados opuestos de un rectángulo, como muestra la figura:
Algoritmo de ordenación topológica:
El siguiente algoritmo encuentra una ordenación topológica T de un grafo S sin ciclos.
1. Encontrar el grado de entrada GraEnt(N) de cada nodo N de S (se puede hacer recorriendo cada lista de adyacencia)
2. Poner en una cola todos los nodos con grado de entrada nulo.
3. Repetir los pasos 4 y 5 hasta que la cola esté vacía.
4. Quitar el nodo N al frente de la cola (haciendo Frente:=Frente + 1)
5. Repetir lo siguiente para cada vecino M de N:
Hacer GraRnt(M):= GraEnt(M) – 1 (esto elimina la arista de N a M)
si GraEnt(M)=0, entonces: Añadir M al final de la cola.
[ fin de bucle paso 5 ]
[ fin de bucle paso 3 ]
6. Salir.
nota: tomado del libro Estructura de datos, serie schaum Mcgraw-Hill,
pagina: 340, capitulo: 8 Grafos y sus aplicaciones, autor: Seymour Lipschutz
A N E X O
TEMAS AFINES Y
COMPLEMENTARIOS
Caminos y Conexión: Un camino en un grafo es una sucesión de vértices y aristas de la forma v0 a1 v1 a2...vk-1 ak vk donde la arista ai une los vértices vi-1 y vi. Éste es un camino de v0 a vk, de longitud k, siendo v1,...,vk-1 los vértices interiores del camino. Si v0=vk decimos que el camino es cerrado. Un ciclo es un camino cerrado con todas sus aristas distintas y con todos sus vértices distintos (salvo, claro es, los extremos v0=vk).
Propiedades:
1. El nº de caminos de longitud k de vi a vj es el elemento ij de la matriz M(G)k.
2. Un grafo G es bipartido Û G no tiene ciclos de longitud impar.
3. Se llama distancia entre dos vértices u y v, a la longitud mínima de un camino que conecta dichos vértices y se designa por d(u,v).
4. Se llama diámetro de G a la máxima distancia entre dos vértices de G, diam(G).
Un grafo es conexo si para cada par de vértices u y v existe un camino de u a v. Si G es un grafo no conexo (o disconexo), cada uno de sus subgrafos conexos maximales se llama componente conexa de G.
Un vértice v se llama vértice-corte (o punto de articulación) de G si el grafo G-{v} tiene más componentes conexas que G.
Una arista a de un grafo G se llama puente si G-{a} tiene más componentes conexas que G.
Conexo: un espacio topológico X se dice conexo si no contiene ningún subconjunto abierto y cerrado, excepto Æ y X. Intuitivamente, un conjunto es conexo cuando no está compuesto por dos o más partes separadas. Una definición mucho más fácil de entender es la de conjunto arcoconexo. Sin embargo, se puede probar que ambas nociones no coinciden: todo conjunto arcoconexo es conexo, pero la recíproca es falsa. En la topología usual, todo abierto conexo es también arcoconexo.
Espacio n–dimensional: se llama espacio n–dimensional usual al conjunto Rn, construido como el producto cartesiano R ´ ... ´ R (n veces), en donde R es el conjunto de los números reales. Los elementos de Rn se piensan como vectores de n coordenadas. El vector nulo es aquel cuyas coordenadas son todas 0, y se lo llama "origen" o "centro de coordenadas". Por ejemplo, el plano R2 es el conjunto de todos los pares ordenados (x,y) en donde sus dos coordenadas x, y son números reales cualesquiera, y su origen es el vector (0,0). A este espacio se le suele asignar una topología, conocida como topología usual de Rn.
Espacio topológico: se llama espacio topológico a un conjunto X provisto de una topología, es decir, una familia de subconjuntos de X, llamados abiertos, que satisfacen los siguientes axiomas:
1.Æ y X son conjuntos abiertos 2.La intersección de un número finito de conjuntos abiertos es un conjunto abierto 3.La unión de cualquier número de conjuntos abiertos es un conjunto abierto
Se desprende de la definición que en cualquier espacio topológico X los conjuntos Æ y X son a la vez abiertos y cerrados (ver también: topología usual)
Función continua: dados dos espacios topológicos X e Y, la función f:X® Y se dice continua en un punto a Î X si dado un entorno V del punto f(a) Î Y, existe un entorno U de a tal que f(U) Ì V, es decir, f(x) Î V para todo x Î U. Esto puede expresarse mediante la noción de límite: f es continua en a si
En la topología usual, la noción de continuidad en a equivale a la propiedad de que si {xn} es cualquier sucesión en X que converge a a, entonces la sucesión {f(xn)} converge a f(a). Intuitivamente, podemos decir: "cuanto más se acerca xn a a, más se acerca f(xn) a f(a) ". f se dice continua cuando es continua en todos sus puntos. Equivalentemente, f es continua si y sólo si la imagen inversa de un abierto cualquiera es un conjunto abierto.
Grupo fundamental: dado un espacio topológico X, se puede formar el conjunto de todos los lazos en X que salen de un cierto punto, considerando como equivalentes a dos lazos que se puedan superponer mediante una homotopía (es decir, tales que se pueda deformar a uno de ellos en forma continua hasta obtener el otro). A dicho conjunto se le asigna una estructura (algebraica) de grupo, lo que determina el llamado grupo fundamental de X. Se trata de un invariante topológico muy útil. Por ejemplo, el grupo fundamental de una circunferencia es Z, el conjunto de los números enteros (Z = {..., - 3, - 2, - 1, 0, 1, 2, 3, ...}), hecho que resulta claro pues todo lazo cerrado sobre la circunferencia está determinado unívocamente por la cantidad de vueltas, y el sentido en que se las recorre. El grupo fundamental de un toro es Z ´ Z, pues en este caso deben tenerse en cuenta las vueltas dadas "alrededor" del agujero, y también "a través" del mismo. Este resultado es, claro está, coherente con el hecho de que el toro puede pensarse como el producto cartesiano de dos circunferencias (ver: toro).
Homeomorfismo: se llama homeomorfismo entre dos espacios topológicos X e Y a una función f: X® Y que resulte biunívoca y bicontinua, es decir:
f es "uno a uno" (biunívoca), lo que significa que para cada elemento x Î X existe un único y Î Y tal que f(x) = y y viceversa. Esto permite definir la función inversa, f-1:Y® X
f y f-1 son continuas (f es bicontinua)
La noción de homeomorfismo responde a la idea intuitiva de "deformación", y determina cierta clase de equivalencia: dos espacios homeomorfos tienen las mismas propiedades topológicas.
Homología: invariante topológico que asocia a cada espacio topológico una estructura algebraica llamada "complejo". Como invariante, tiene mayor precisión que el grupo fundamental, aunque su definición y cálculo resultan más complicados.
Homotopía: dados dos espacios topológicos X e Y, una homotopía es una función continua h:X ´ [ a,b] ® Y, en donde [ a,b] es un intervalo cerrado. Por comodidad, siempre supondremos que [ a,b] es el intervalo [ 0,1] . Se puede interpretar intuitivamente la noción de homotopía pensando al [ 0,1] como un intervalo de tiempo, y en consecuencia h representa una cierta deformación a partir del instante inicial t = 0, hasta llegar a t = 1 pasando por cada instante t fijo.
Identificar: operación topológica que responde a la noción intuitiva de "pegar". Consiste en definir alguna relación de equivalencia entre puntos de un espacio topológico X, lo que permite definir el espacio cociente. Por ejemplo, si se identifican uno a uno los puntos de dos lados opuestos de un rectángulo, se obtiene una superficie tubular similar a un "cinturón", o una porción de cilindro. En cambio, si esta identificación se efectúa orientando a los dos lados en sentidos opuestos, se obtiene una Banda de Möbius.
Interior: dado un conjunto A, si llama interior de A al mayor abierto contenido en A. Notación: Aº = interior de A . Por definición, es claro que un conjunto es abierto si y sólo si coincide con su interior. El interior de A se puede pensar como el conjunto de puntos de A que no pertenecen a su frontera, es decir: Aº = A - Fr(A).
Intervalo: dados dos números reales a < b, se llama intervalo entre a y b al conjunto de puntos de la recta contenidos entre a y b. Caben cuatro posibilidades, según se incluya o no a cada uno de los extremos:
1. (a,b) = { x Î R / a < x < b } (intervalo abierto)
2. [a,b) = { x Î R / a £ x < b } (intervalo semiabierto)
3. (a,b] = { x Î R / a < x £ b } (intervalo semiabierto)
4. [a,b] = { x Î R / a £ x £ b } (intervalo cerrado)
También se definen los siguientes intervalos no acotados: ( a,+ ¥ ), [ a,+ ¥ ),
( – ¥ , b ), (– ¥ , b ] . Por ejemplo, ( a, + ¥ ) = { x Î R / x > a }. Los símbolos + ¥ y
– ¥ responden únicamente a una mayor simplicidad en la escritura, ya que no se trata de números reales. Por esa razón, todo intervalo no acotado es abierto en su "extremo infinito". Obviamente, el intervalo (– ¥ ,+ ¥ ) equivale a toda la recta R. Es fácil ver que cualquier intervalo abierto es homeomorfo a R.
Invariante: se llama invariante topológico a aquellas propiedades de un espacio topológico que permanecen cuando se le aplica un homeomorfismo. Algunos invariantes muy conocidos son la compacidad, la conexión, el grupo fundamental, la homología, etc. En general, cada teoría matemática tiene sus propios invariantes: así, los invariantes geométricos son las propiedades que conserva una figura cuando se le aplica una rotación o una traslación (movimientos rígidos).
Matrices: la matriz de adyacencia de un grafo G con n vértices {v1,...,vn} es la matriz nxn , M(G)=(aij), donde aij es el nº de aristas que unen vi con vj. La matriz de incidencia de un grafo simple G con n vértices {v1,...,vn} y k aristas {e1,...,ek} es la matriz nxk, I(G)=(bij), donde bij=1 si vi es incidente con ej y bij=0 en caso contrario.
Plano proyectivo: espacio definido en geometría proyectiva, de acuerdo con la idea intuitiva de agregar al plano euclidiano un "horizonte", de modo tal que dos rectas paralelas determinen un (único) punto. Las rectas resultan entonces cerradas, es decir, homeomorfas a una circunferencia, hecho relacionado además con la propiedad que tiene el plano proyectivo de ser compacto. Al horizonte, que también es una recta, se lo suele llamar "recta impropia", pues está compuesta de puntos impropios, también llamados puntos "del infinito".
En la geometría proyectiva los conceptos de "punto" y "recta" son duales, puesto que pueden intercambiarse. Por ejemplo, el enunciado: "Dos puntos determinan una única recta" se transforma en su dual "Dos rectas determinan un único punto", que también es válido, aunque no lo es en la geometría euclidiana.
Poliedro topológico: generalización de la noción geométrica de poliedro. Consiste en un sistema formado por un número finito de polígonos topológicos sujetos a ciertas condiciones, entre las cuales se tiene, por ejemplo, que dos polígonos distintos no tienen puntos interiores comunes, que los lados de los polígonos del sistema coinciden dos a dos, etc.
Polígono topológico: generalización de la noción geométrica de polígono. Consiste en tomar cierto número finito n > 1 de puntos en una circunferencia. Los arcos así determinados serán los lados, y los puntos se llamarán vértices del polígono. El polígono estará formado entonces, por el conjunto de lados y la región interior a la circunferencia.
Recorridos en un Grafo: Un camino euleriano en un grafo es un camino que contiene a todas las aristas del grafo exactamente una vez. Un grafo es euleriano si contiene un camino euleriano cerrado.
Teorema: Un grafo conexo G es euleriano Û Todos los vértices de G tienen grado par.
Consecuencia: Un grafo conexo G tiene un camino euleriano no cerrado Û G tiene, exactamente, dos vértices de grado impar.
Algoritmo de Fleury (para construir un camino euleriano cerrado en un grafo euleriano).
Paso 1.- Se comienza en un vértice cualquiera v0 .
Paso 2.- Si se ha construido el camino v0 a1 v1 a2...vk-1 ak vk con aristas distintas, se elige la arista siguiente ak+1 con las condiciones: (1) ak+1 incidente con vk y (2) no ser puente en el grafo G- {a1,a2,...,ak} (salvo que no haya alternativa).
Paso 3.- Se sigue hasta que el camino contenga todas las aristas.
Un camino hamiltoniano en un grafo es un camino que contiene a todos los vértices del grafo exactamente una vez (salvo v0=vn, si el camino es cerrado). Un grafo hamiltoniano es aquel que contiene un ciclo hamiltoniano.
Propiedad: Un grafo bipartido G=(V1 È V2 , A) con ½ V1½ ¹ ½ V2½ no es hamiltoniano.
Teorema: Sea G un grafo simple de n vértices. Si para todo par de vértices x e y no adyacentes se cumple que d(x)+d(y) ³ n , entonces G es hamiltoniano.
Teorema: Si G es un grafo hamiltoniano entonces, para todo SÌ V se cumple que el número de componentes conexas de G - S, es menor o igual que ½ S½ .
Observación: NO hay caracterización para los grafos hamiltonianos.
Grafos
Definición
Un grafo es un objeto matemático que se utiliza para representar circuitos, redes, etc. Los grafos son muy utilizados en computación, ya que permiten resolver problemas muy complejos.
Imaginemos que disponemos de una serie de ciudades y de carreteras que las unen. De cada ciudad saldrán varias carreteras, por lo que para ir de una ciudad a otra se podrán tomar diversos caminos. Cada carretera tendrá un coste asociado (por ejemplo, la longitud de la misma). Gracias a la representación por grafos podremos elegir el camino más corto que conecta dos ciudades, determinar si es posible llegar de una ciudad a otra, si desde cualquier ciudad existe un camino que llegue a cualquier otra, etc.
El estudio de grafos es una rama de la algoritmia muy importante. Estudiaremos primero sus rasgos generales y sus recorridos fundamentales, para tener una buena base que permita comprender los algoritmos que se pueden aplicar.
Glosario
Un grafo consta de vértices (o nodos) y aristas. Los vértices son objetos que contienen información y las aristas son conexiones entre vértices. Para representarlos, se suelen utilizar puntos para los vértices y líneas para las conexiones, aunque hay que recordar siempre que la definición de un grafo no depende de su representación.
Un camino entre dos vértices es una lista de vértices en la que dos elementos sucesivos están conectados por una arista del grafo. Así, el camino AJLOE es un camino que comienza en el vértice A y pasa por los vértices J,L y O (en ese orden) y al final va del O al E. El grafo será conexo si existe un camino desde cualquier nodo del grafo hasta cualquier otro. Si no es conexo constará de varias componentes conexas.
Un camino simple es un camino desde un nodo a otro en el que ningún nodo se repite (no se pasa dos veces). Si el camino simple tiene como primer y último elemento al mismo nodo se denomina ciclo. Cuando el grafo no tiene ciclos tenemos un árbol (ver árboles). Varios árboles independientes forman un bosque. Un árbol de expansión de un grafo es una reducción del grafo en el que solo entran a formar parte el número mínimo de aristas que forman un árbol y conectan a todos los nodos.
Según el número de aristas que contiene, un grafo es completo si cuenta con todas las aristas posibles (es decir, todos los nodos están conectados con todos), disperso si tiene relativamente pocas aristas y denso si le faltan pocas para ser completo.
Las aristas son la mayor parte de las veces bidireccionales, es decir, si una arista conecta dos nodos A y B se puede recorrer tanto en sentido hacia B como en sentido hacia A: estos son llamados grafos no dirigidos. Sin embargo, en ocasiones tenemos que las uniones son unidireccionales. Estas uniones se suelen dibujar con una flecha y definen un grafo dirigido. Cuando las aristas llevan un coste asociado (un entero al que se denomina peso) el grafo es ponderado. Una red es un grafo dirigido y ponderado.
Representación de grafos
Una característica especial en los grafos es que podemos representarlos utilizando dos estructuras de datos distintas. En los algoritmos que se aplican sobre ellos veremos que adoptarán tiempos distintos dependiendo de la forma de representación elegida. En particular, los tiempos de ejecución variarán en función del número de vértices y el de aristas, por lo que la utilización de una representación u otra dependerá en gran medida de si el grafo es denso o disperso.
Para nombrar los nodos utilizaremos letras mayúsculas, aunque en el código deberemos hacer corresponder cada nodo con un entero entre 1 y V (número de vértices) de cara a la manipulación de los mismos.
Representación por matriz de adyacencia
Es la forma más común de representación y la más directa. Consiste en una tabla de tamaño V x V, en que la que a[i][j] tendrá como valor 1 si existe una arista del nodo i al nodo j. En caso contrario, el valor será 0. Cuando se trata de grafos ponderados en lugar de 1 el valor que tomará será el peso de la arista. Si el grafo es no dirigido hay que asegurarse de que se marca con un 1 (o con el peso) tanto la entrada a[i][j] como la entrada a[j][i], puesto que se puede recorrer en ambos sentidos.
int V,A;
int a[maxV][maxV];
void inicializar()
{
int i,x,y,p;
char v1,v2;
// Leer V y A
memset(a,0,sizeof(a));
for (i=1; i<=A; i++)
{
scanf("%c %c %dn",&v1,&v2,&p);
x=v1-'A'; y=v2-'A';
a[x][y]=p; a[y][x]=p;
}
}
En esta implementación se ha supuesto que los vértices se nombran con una letra mayúscula y no hay errores en la entrada. Evidentemente, cada problema tendrá una forma de entrada distinta y la inicialización será conveniente adaptarla a cada situación. En todo caso, esta operación es sencilla si el número de nodos es pequeño. Si, por el contrario, la entrada fuese muy grande se pueden almacenar los nombres de nodos en un árbol binario de búsqueda o utilizar una tabla de dispersión, asignando un entero a cada nodo, que será el utilizado en la matriz de adyacencia.
Como se puede apreciar, la matriz de adyacencia siempre ocupa un espacio de V*V, es decir, depende solamente del número de nodos y no del de aristas, por lo que será útil para representar grafos densos.
Representación por lista de adyacencia
Otra forma de representar un grafo es por medio de listas que definen las aristas que conectan los nodos. Lo que se hace es definir una lista enlazada para cada nodo, que contendrá los nodos a los cuales es posible acceder. Es decir, un nodo A tendrá una lista enlazada asociada en la que aparecerá un elemento con una referencia al nodo B si A y B tienen una arista que los une. Obviamente, si el grafo es no dirigido, en la lista enlazada de B aparecerá la correspondiente referencia al nodo A.
Las listas de adyacencia serán estructuras que contendrán un valor entero (el número que identifica al nodo destino), así como otro entero que indica el coste en el caso de que el grafo sea ponderado. En el ejemplo se ha utilizado un nodo z ficticio en la cola (ver listas, apartado cabeceras y centinelas).
struct nodo
{
int v;
int p;
nodo *sig;
};
int V,A; // vértices y aristas del grafo
struct nodo *a[maxV], *z;
void inicializar()
{
int i,x,y,peso;
char v1,v2;
struct nodo *t;
z=(struct nodo *)malloc(sizeof(struct nodo));
z->sig=z;
for (i=0; i<V; i++)
a[i]=z;
for (i=0; i<A; i++)
{
scanf("%c %c %dn",&v1,&v2,&peso);
x=v1-'A'; y=v2-'A';
t=(struct nodo *)malloc(sizeof(struct nodo));
t->v=y; t->p=peso; t->sig=a[x]; a[x]=t;
t=(struct nodo *)malloc(sizeof(struct nodo));
t->v=x; t->p=peso; t->sig=a[y]; a[y]=t;
}
}
En este caso el espacio ocupado es O(V + A), muy distinto del necesario en la matriz de adyacencia, que era de O(V2). La representación por listas de adyacencia, por tanto, será más adecuada para grafos dispersos.
Hay que tener en cuenta un aspecto importante y es que la implementación con listas enlazadas determina fuertemente el tratamiento del grafo posterior. Como se puede ver en el código, los nodos se van añadiendo a las listas según se leen las aristas, por lo que nos encontramos que un mismo grafo con un orden distinto de las aristas en la entrada producirá listas de adyacencia diferentes y por ello el orden en que los nodos se procesen variará. Una consecuencia de esto es que si un problema tiene varias soluciones la primera que se encuentre dependerá de la entrada dada. Podría presentarse el caso de tener varias soluciones y tener que mostrarlas siguiendo un determinado orden. Ante una situación así podría ser muy conveniente modificar la forma de meter los nodos en la lista (por ejemplo, hacerlo al final y no al principio, o incluso insertarlo en una posición adecuada), de manera que el algoritmo mismo diera las soluciones ya ordenadas.
Exploración de grafos
A la hora de explorar un grafo, nos encontramos con dos métodos distintos. Ambos conducen al mismo destino (la exploración de todos los vértices o hasta que se encuentra uno determinado), si bien el orden en que éstos son "visitados" decide radicalmente el tiempo de ejecución de un algoritmo, como se verá posteriormente.
En primer lugar, una forma sencilla de recorrer los vértices es mediante una función recursiva, lo que se denomina búsqueda en profundidad. La sustitución de la recursión (cuya base es la estructura de datos pila) por una cola nos proporciona el segundo método de búsqueda o recorrido, la búsqueda en amplitud o anchura.
Suponiendo que el orden en que están almacenados los nodos en la estructura de datos correspondiente es A-B-C-D-E-F... (el orden alfabético), tenemos que el orden que seguiría el recorrido en profundidad sería el siguiente:
A-B-E-I-F-C-G-J-K-H-D
En un recorrido en anchura el orden sería, por contra:
A-B-C-D-E-G-H-I-J-K-F
Es decir, en el primer caso se exploran primero los verdes y luego los marrones, pasando primero por los de mayor intensidad de color. En el segundo caso se exploran primero los verdes, después los rojos, los naranjas y, por último, el rosa.
Es destacable que el nodo D es el último en explorarse en la búsqueda en profundidad pese a ser adyacente al nodo de origen (el A). Esto es debido a que primero se explora la rama del nodo C, que también conduce al nodo D.
En estos ejemplos hay que tener en cuenta que es fundamental el orden en que los nodos están almacenados en las estructuras de datos. Si, por ejemplo, el nodo D estuviera antes que el C, en la búsqueda en profundidad se tomaría primero la rama del D (con lo que el último en visitarse sería el C), y en la búsqueda en anchura se exploraría antes el H que el G.
Búsqueda en profundidad
Se implementa de forma recursiva, aunque también puede realizarse con una pila. Se utiliza un array val para almacenar el orden en que fueron explorados los vértices. Para ello se incrementa una variable global id (inicializada a 0) cada vez que se visita un nuevo vértice y se almacena id en la entrada del array val correspondiente al vértice que se está explorando.
La siguiente función realiza un máximo de V (el número total de vértices) llamadas a la función visitar, que implementamos aquí en sus dos variantes: representación por matriz de adyacencia y por listas de adyacencia.
int id=0;
int val[V];
void buscar()
{
int k;
for (k=1; k<=V; k++)
val[k]=0;
for (k=1; k<=V; k++)
if (val[k]==0) visitar(k);
}
void visitar(int k) // matriz de adyacencia
{
int t;
val[k]=++id;
for (t=1; t<=V; t++)
if (a[k][t] && val[t]==0) visitar(t);
}
void visitar(int k) // listas de adyacencia
{
struct nodo *t;
val[k]=++id;
for (t=a[k]; t!=z; t=t->sig)
if (val[t->v]==0) visitar(t->v);
}
El resultado es que el array val contendrá en su i-ésima entrada el orden en el que el vértice i-ésimo fue explorado. Es decir, si tenemos un grafo con cuatro nodos y fueron explorados en el orden 3-1-2-4, el array val quedará como sigue:
val[1]=2; // el primer nodo fue visto en segundo lugar
val[2]=3; // el segundo nodo fue visto en tercer lugar
val[3]=1; // etc.
val[4]=4;
Una modificación que puede resultar especialmente útil es la creación de un array "inverso" al array val que contenga los datos anteriores "al revés". Esto es, un array en el que la entrada i-ésima contiene el vértice que se exploró en i-ésimo lugar. Basta modificar la línea
val[k]=++id;
sustituyéndola por
val[++id]=k;
Para el orden de exploración de ejemplo anterior los valores serían los siguientes:
val[1]=3;
val[2]=1;
val[3]=2;
val[4]=4;
Búsqueda en amplitud o anchura
La diferencia fundamental respecto a la búsqueda en profundidad estriba en el cambio de estructura de datos: una cola en lugar de una pila. En esta implementación, la función del array val y la variable id es la misma que en el método anterior.
struct tcola *cola;
void visitar(int k) // listas de adyacencia
{
struct nodo *t;
encolar(&cola,k);
while (!vacia(cola))
{
desencolar(&cola,&k);
val[k]=++id;
for (t=a[k]; t!=z; t=t->sig)
{
if (val[t->v]==0)
{
encolar(&cola,t->v);
val[t->v]=-1;
}
}
}
}
6. Grafos
6.1 Fundamentos y terminología básica
Un grafo, G, es un par, compuesto por dos conjuntos V y A. Al conjunto V se le llama conjunto de vértices o nodos del grafo. A es un conjunto de pares de vértices, estos pares se conocen habitualmente con el nombre de arcos o ejes del grafo. Se suele utilizar la notacion G = (V, A) para identificar un grafo.
Los grafos representan un conjunto de objetos donde no hay restricción a la relación entre ellos. Son estructuras más generales y menos restrictivas. 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.
Ejemplos de grafos (dirigidos y no dirigidos):
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:
Los grafos permiten representar conjuntos de objetos arbitrariamente relacionados. Se puede asociar el conjunto de vértices con el conjunto de objetos y el conjunto de arcos con las relaciones que se establecen entre ellos.
Los grafos son modelos matemáticos de numerosas situaciones reales: un mapa de carreteras, la red de ferrocarriles, el plano de un circuito eléctrico, el esquema de la red telefónica de una compañia, etc.
El número de distintos pares de vértices (v(i), v(j)), con v(i) <> v(j), en un grafo con n vértices es n*(n-1)/2. Este es el número máximo de arcos en un grafo no dirigido de n vértices. Un grafo no dirigido que tenga exactamente n*(n-1)/2 arcos se dice que es un grafo completo. En el caso de un grafo dirigido de n vértices el número máximo de arcos es n*(n-1).
Algunas definiciones básicas en grafos:
· Orden de un grafo: es el número de nodos (vértices) del grafo.
· Grado de un nodo: es el número de ejes (arcos) que inciden sobre el nodo
· Grafo simétrico: es un grafo dirigido tal que si existe la relación entonces existe , con u, v pertenecientes a V.
· Grafo no simétrico: es un grafo que no cumple la propiedad anterior.
· Grafo reflexivo: es el grafo que cumple que para todo nodo u de V existe la relación (u, u) de A.
· Grafo transitivo: es aquél que cumple que si existen las relaciones (u, v) y (v, z) de A entonces existe (u, z) de A.
· Grafo completo: es el grafo que contiene todos los posibles pares de relaciones, es decir, para cualquier par de nodos u, v de V, (u <> v), existe (u, v) de A.
· Camino: un camino en el grafo G es una sucesión de vértices y arcos: v(0), a(1), v(1), a(2), v(2), ... , a(k), v(k); tal que los extremos del arco a(i) son los vértices v(i-1) y v(i).
· Longitud de un camino: es el número de arcos que componen el camino.
· Camino cerrado (circuito): camino en el que coinciden los vértices extremos (v(0) = v(k)).
· Camino simple: camino donde sus vértices son distintos dos a dos, salvo a lo sumo los extremos.
· Camino elemental: camino donde sus arcos son distintos dos a dos.
· Camino euleriano: camino simple que contiene todos los arcos del grafo.
· Grafo euleriano: es un grafo que tiene un camino euleriano cerrado.
· Grafo conexo: es un grafo no dirigido tal que para cualquier par de nodos existe al menos un camino que los une.
· Grafo fuertemente conexo: es un grafo dirigido tal que para cualquier par de nodos existe un camino que los une.
· Punto de articulación: es un nodo que si desaparece provoca que se cree un grafo no conexo.
· Componente conexa: subgrafo conexo maximal de un grafo no dirigido (parte más grande de un grafo que sea conexa).
6.2 Representación de grafos
Existen tres maneras básicas de representar los grafos: mediante matrices, mediante listas y mediante matrices dispersas. Cada representación tiene unas ciertas ventajas e inconvenientes respecto de las demás, que comentaremos más adelante.
Representación mediante matrices: matrices de adyacencia
Un grafo es un par compuesto por dos conjuntos: un conjunto de nodos y un conjunto de relaciones entre los nodos. La representación tendrá que ser capaz de guardar esta información en memoria.
La forma más fácil de guardar la información de los nodos es mediante la utilización de un vector que indexe los nodos, de manera que los arcos entre los nodos se pueden ver como relaciones entre los índices. Esta relación entre índices se puede guardar en una matriz, que llamaremos de adyacencia.
Const MAX_NODOS = ??;Type Indice = 1..MAX_NODOS; Valor_Nodo = ??; Valor_Arco = ??; Arco = Record Info: Valor_Arco; (* información asociada a cada arco *) Existe: Boolean; end; Nodo = Record Info: Valor_Nodo; (* información asociada a cada nodo *) Existe: Boolean; end; Grafo = Record Nodos: Array[Indice] of Nodo; Arcos: Array[Indice, Indice] of Arco; end;
Con esta representación tendremos que reservar al menos del orden de (n^2) espacios de memoria para la información de los arcos, y las operaciones relacionadas con el grafo implicarán, habitualmente, recorrer toda la matriz, con lo que el orden de las operaciones será, en general, cuadrático, aunque tengamos un número de relaciones entre los nodos mucho menor que (n^2).
En cambio, con esta representación es muy fácil determinar, a partir de dos nodos, si están o no relacionados: sólo hay que acceder al elemento adecuado de la matriz y comprobar el valor que guarda.
Ejemplo:
Supongamos el grafo representado en la figura anterior. A partir de ese grafo la información que guardariamos, con esta representación, sería:
Representación mediante punteros: listas de adyacencia
En las listas de adyacencia se intenta evitar justamente el reservar espacio para aquellos arcos que no contienen ningún tipo de información. El sustituto obvio a los vectores con huecos son las listas.
En las listas de adyacencia lo que haremos será guardar por cada nodo, además de la información que pueda contener el propio nodo, una lista dinámica con los nodos a los que se puede acceder desde él. La información de los nodos se puede guardar en un vector, al igual que antes, o en otra lista dinámica. Si elegimos la representación en un vector para los nodos, tendríamos la siguiente definición de grafo en Pascal:
Const MAX_NODOS = ??;Type Indice = 1..MAX_NODOS; Valor_Nodo = ??; Valor_Arco = ??; Punt_Arco = ^Arco; Arco = Record Info: Valor_Arco; (* información asociada a cada arco *) Destino: Indice; Sig_Arco: Punt_Arco; end; Nodo = Record Info: Valor_Nodo; (* información asociada a cada nodo *) Existe: Boolean; Lista_Arcos: Punt_Arco; end; Grafo = Record Nodos: Array[Indice] of Nodo; end;
En general se está guardando menor cantidad de elementos, sólo se reservará memoria para aquellos arcos que efectivamente existan, pero como contrapartida estamos guardando más espacio para cada uno de los arcos (estamos añadiendo el índice destino del arco y el puntero al siguiente elemento de la lista de arcos).
Las tareas relacionadas con el recorrido del grafo supondrán sólo trabajar con los vértices existentes en el grafo, que puede ser mucho menor que (n^2). Pero comprobar las relaciones entre nodos no es tan directo como lo era en la matriz, sino que supone recorrer la lista de elementos adyacentes perteneciente al nodo analizado.
Además, sólo estamos guardando realmente la mitad de la información que guardábamos en el caso anterior, ya que las relaciones inversas (las relaciones que llegan a un cierto nodo) en este caso no se guardan, y averiguarlas supone recorrer todas las listas de todos los nodos.
Representación mediante punteros: matrices dispersas
Para evitar uno de los problemas que teníamos con las listas de adyacencia, que era la dificultad de obtener las relaciones inversas, podemos utilizar las matrices disperas, que contienen tanta información como las matrices de adyacencia, pero, en principio, no ocupan tanta memoria como las matrices, ya que al igual que en las listas de adyacencia, sólo representaremos aquellos enlaces que existen en el grafo.
Const MAX_NODOS = ??;Type Indice = 1..MAX_NODOS; Valor_Nodo = ??; Valor_Arco = ??; Punt_Arco = ^Arco; Arco = Record Info: Valor_Arco; (* información asociada a cada arco *) Origen: Indice; Destino: Indice; Sig_Arco_Salida: Punt_Arco;