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:

PRINCIPIO = 1, NDISP = 5

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:

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:

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.

   estado al de procesado (ESTADO=3).

4. Sacar el nodo N en la cima de la pila. Procesar el
   nodo N y cambiar su

   preparados (ESTADO=1) y cambiar su estado a
   estado de espera

   (ESTADO=2).

   [ fin de bucle del paso 3 ]

5. Meter en la pila todos los vecinos de N que
   estén en estado de
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.

   estado a procesado (ESTADO=3).

4. Quitar el nodo del principio de la cola, N.
   Procesar N y cambiar su

   preparados (ESTADO=1) y cambiar su estado al de
   espera

   (ESTADO=2).

   [ fin del bucle del paso 3 ]

5. Añadir a COLA todos los vecinos de N que
   estén en estado de
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. si A[ I, J ]=0, entonces: hacer P[ I, J
   ]:=0;

   si no: hacer P[ I, J ]:=1.

   [ fin de bucle ]

2. [ Inicializar P ] repetir para I, J =1, 2, …
   M:
3. [ Actualizar P ] repetir paso 3 y 4 para K=1, 2,
   …, M:
4. repetir paso 4 para I=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. repetir para J=1, 2, …, M:
6. 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. si W [ I, J ] = 0, entonces: hacer Q [ I, J ]:=
   INFINITO;

   si no: hacer Q [ I, J ] := W [ I, J
   ].

   [ fin de bucle ]

2. [ Inicializar Q ] repetir para I, J=1, 2, . . .,
   M:
3. [ Actualizar Q ] repetir pasos 3 y 4 para K=1, 2,
   . . ., M:
4. repetir paso 4 para I = 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. repetir para J = 1, 2, . . ., M:
6. 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:

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:

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:

2. Los pesos de las aristas deben ser no
   negativos.
3. 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)

   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 ]

5. Repetir lo siguiente para cada vecino M de
   N:
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:   

2. El nº de caminos de longitud k de vi a vj es el
   elemento ij de la matriz M(G)k.
3. Un grafo G es bipartido Û G no tiene ciclos de
   longitud impar.
4. 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).
5. 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:

2. (a,b) = { x Î R / a < x < b }
   (intervalo abierto)
3. [a,b) = { x Î R / a £ x < b }
   (intervalo semiabierto)
4. (a,b] = { x Î R / a < x £ b }
   (intervalo semiabierto)
5. [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.

Bibliografia:

1. Balabaniam, N.: Circuitos
   Eléctricos. MacGraw Hill. 1994. 127 –
   135.
2. Balabaniam, N.; Bickart, T.A.; Seshu, S.:
   Teoría de Redes Eléctricas.
   Reverté, 1972. 200 – 204.
3. Budak, A. Passive and Active Network Analysis and
   Synthesis. Houghton Mifflin, 1974. 97 – 140.
4. Lipschults, Seymour: Estructura de Datos
   teoría y problemas.
   Schaum-McGraw-Hill. 1988. 315 – 357.
5. Folk, M y Zoellick, B.: Estructura de Archivos,
   Addison-Wesley, Reading, MA, 1992. 420 – 423.
6. Cormen, Leiserson, Rivest: Introducción a la
   Algoritmica, The MIT Press-Mc Graw Hill, 1990. 199 –
   215.
7. A.Giraldo, Topología Digital, Prepublicaciones
   del Departamento de Matemática Aplicada, FIM/2/DMA/97,
   Facultad de Informática, UPM, 1997.
8. A.Giraldo, Digitizations preserving shape, Vision
   Geometry VI, Proc. of the 1997 SPIE Conference on Vision
   Geometry, San Diego, 1997.
9. G.T.Herman, Análisis de la Imagen en
   Aplicación topológica, Visión de la
   Computadora, Procesando Gráficos e Imagen, 52, 1990,
   409-415.
10. E.Khalimsky, Topological structures in computer
    science, J. Appl. Math. Simulation, 1, 1987, 25-40.
11. T.Y.Kong, R.Kopperman y P.R.Meyer, A Topological
    Approach to Digital Topology, American Mathematical Monthly,
    98, 1991, 901-917.1.
12. T.Y.Kong, R.Kopperman y P.R.Meyer (eds.), Problema
    especial en Topología Digital, Topología y sus
    Aplicaciones, 46, 1992.
13. T.Y.Kong y A.Rosenfeld, Digital Topology:
    Introduction and Survey, Computer Vision, Graphics and Image
    Processing, 48, 1989, 357-393.
14. T.Y.Kong y A.Rosenfeld (eds.), Problema especial en
    Topología y Geometría en Visión de
    la
    Computadora, Periódico de Imagen Matemático y
    Visión, 6, 1996.
15. V.A.Kovalevsky, Finite Topology as Applied to Image
    Analysis, Computer Vision, Graphics and Image Processing, 46,
    1989, 141-161.
16. E.H.Kronhemeir, Alternativas topológicas
    Digitales, Topología y sus Aplicaciones, 46, 1992,
    269-277.
17. Knuth D.E.; Clasificación y búsqueda.
    El Arte de
    Programar Ordenadores Vol. III. Ed. Revert S.A.,
    1987.
18. Knuth D.E.; Algoritmos
    Fundamentales. El Arte de
    Programar Ordenadores Vol. I. Ed. Revert S.A.,
    1980.
19. Aho A. V., Hopcroft J.E., Ullman J.D.; Estructuras
    de Datos y Algoritmos.
    Ed. Addison-Wesley, 1988.
20. Deitel H.M., Deitel P.J.; C++ How To Program. Ed.
    Prentice Hall, 1994.

Autor:

Felipe Costales