Introducción

Como ya sabemos, las computadoras fueron diseñadas o ideadas como una herramienta mediante la cual podemos realizar operaciones de cálculo complicadas en un lapso de mínimo tiempo.

Pero la mayoría de las aplicaciones de este fantástico invento del hombre, son las de almacenamiento y acceso de grandes cantidades de información.

La información que se procesa en la computadora es un conjunto de datos, que pueden ser simples o estructurados.

Los datos simples son aquellos que ocupan sólo un localidad de memoria, mientras que los estructurados son un conjunto de casillas de memoria a las cuales hacemos referencia mediante un identificador único.

Debido a que por lo general tenemos que tratar con conjuntos de datos y no con datos simples (enteros, reales, booleanos, etc.) que por sí solos no nos dicen nada, ni nos sirven de mucho, es necesario tratar con estructuras de datos adecuadas a cada necesidad.

Las estructuras de datos son una colección de datos cuya organización se caracteriza por las funciones de acceso que se usan para almacenar y acceder a elementos individuales de datos.

Una estructura de datos se caracteriza por lo siguiente:

· Pueden descomponerse en los elementos que la forman.

· La manera en que se colocan los elementos dentro de la estructura afectará la forma en que se realicen los accesos a cada elemento.

· La colocación de los elementos y la manera en que se accede a ellos puede ser encapsulada

Grafo

El origen de la palabra grafo proviene de la lengua griego y su significado etimológico es "trazar".

Aparece con gran frecuencia como respuesta a problemas de la vida cotidiana, algunos ejemplos pueden ser los siguientes: un gráfico de una serie de tareas a realizar indicando su secuenciación o también un organigrama, los grafos matemáticos que representan las relaciones binarias, una red de carreteras, la red de enlaces ferroviarios o aéreos o la red eléctrica de una ciudad (Fig. 1).

En cada caso, es conveniente representar gráficamente el problema dibujando un grafo como un conjunto de puntos o vértices con líneas conectándolos (arcos).

Un grafo es básicamente un objeto geométrico aunque sea un objeto combinatorio, es decir, un conjunto de puntos y un conjunto de líneas tomado de entre el conjunto de líneas que une cada par de vértices.

Debido a su generalidad y a la diversidad de formas, resulta complejo tratar con todas las ideas relacionadas con un grafo.

Los grafos son estructuras de datos no lineales que tienen una naturaleza dinámica. Su estudio podría dividirse en dos grandes bloques:

· Grafos Dirigidos: Los arcos en el grafo tienen una dirección asociada. El primer elemento del arco es el origen y el segundo es considerado el destino

· Grafos no Dirigidos (pueden ser considerados un caso particular de los anteriores): Los arcos en el grafo no tienen una dirección particular, es decir, son bidireccionales.

Un grafo es una estructura de datos que almacena datos de dos tipos:

· Vértices o nudos, con un valor almacenado.

· Aristas o arcos: cada una conecta a un vértice con otro, y puede tener un valor almacenado.

Una arista es un par de vértices (v,w).

Si el par está ordenado, se dice que el grafo es dirigido o que es un dígrafo.

Un grafo está formado por un conjunto de nodos o vértices y un conjunto de arcos. Cada arco en un grafo se especifica por un par de nodos.

El conjunto de nodos es {A, B, C, D, F, G, H} y el conjunto de arcos {(A, B), (A, D), (A, C), (C, D), (C, F), (E, G), (A, A)} para el siguiente grafo.

Su Terminología

· Al número de nodos del grafo se le llama orden del grafo.

· Un grafo nulo es un grafo de orden 0 (cero).

· Dos nodos son adyacentes si hay un arco que los une.

· En un grafo dirigido, si A es adyacente de B, no necesariamente B es adyacente de A

· Camino es una secuencia de uno o más arcos que conectan dos nodos.

· Un grafo se denomina conectado cuando existe siempre un camino que une dos nodos cualesquiera y desconectado en caso contrario.

· Un grafo es completo cuando cada nodo está conectado con todos y cada uno de los nodos restantes.

· El camino de un nodo así mismo se llama ciclo.

Lazo o bucle

Un lazo o bucle en un grafo es un enlace cuyos puntos finales son el mismo nodo. Un grafo se dice simple si no tiene lazos y existe como mucho un enlace entre cada par de nodos (no hay enlaces en paralelo).

Un lazo o bucle o también llamado “Composición iterativa” permite ejecutar múltiples veces unas instrucciones. La cantidad de veces se puede establecer mediante:

· Una condición:

o Se comprueba al principio: las instrucciones del lazo se hacen cero o más veces.

o Se comprueba al final: las instrucciones del lazo se hacen una o más veces.

· Un número fijo de veces: se usa una variable de control.

Existen Tipos de Bucles:

Bucles Infinitos

Se observa que la flecha que se regresa hacia arriba nos está indicando que hay que volver a evaluar la expresión. Como el bucle es infinito, no se tiene una condición para terminar y se estará haciendo siempre.

Bucles Finitos

Bucles repetitivos

Existen tres diseños de estructuras cíclicas:

· Independientes: cuando los bucles se realiza uno primero hasta que se cumple la condición y solo se entra al bucle B.

· Aninados: Al entrar a una estructura de repetición, dentro de ella se encuentra otra. Se termina de realizar y se continúa con la externa hasta que la condición se cumple.

· Cruzados: Inicia un bucle y no se termina cuando empieza otro, luego se utiliza estructuras goto (saltos) para pasar al bucle externo y se quedan entrelazados.

Ocasiona que el programa pierda el control de lo que se está ejecutando y se puede obtener resultados erróneos.

Caminos

Un camino es una sucesión de vértices tal que de cada uno de sus vértices existe una arista hacia el vértice sucesor.

Un camino A es simple si no se repite ningún vértice en el. Dos caminos son independientes si no tienen ningún vértice excepto el primero y el último.

La longitud de un camino es el número de enlaces que tiene el camino. Por ejemplo: 1, 2, 5, 1, 2, 3 es un camino con longitud 5, y 5, 2, 1 es un camino simple de longitud 2.

Un camino de un grafo G = (V, R) es una secuencia de nodos de V en los que cada nodo es adyacente al siguiente mediante un arco de R, ejemplo:

V = {1, 2, 3, 4, 5, 6}

R = {(1, 4), (1, 5), (1, 6), (2, 3), …, (5, 1), (6, 2)}

Caminos: {1, 6, 2, 3}, {5, 1, 4}, …

Existen diferentes tipos de caminos:

· Camino simple: Es el camino que no recorre el mismo arco dos veces. b, d y g es un camino simple, pero b, d, g y b no es un camino simple.

Es un camino en el que todos los nodos contenidos son diferentes, con la posible excepción del primero y el último, que podrían ser el mismo.

· Camino cerrado: Es el camino que no visita un mismo nodo más de una vez. b y d es un camino elemental, pero b, d y g no lo es.

Ciclos

Cuando los dos extremos de un camino son iguales, el camino se llama circuito o ciclo pero que no tenga aristas repetidas.

Un ciclo es una cadena finita donde el nodo inicial de la cadena coincide con el nodo terminal de la misma. Es un camino de longitud de al menos uno que empieza y acaba en el mismo vértice. Se dice que se le puede llamar un ciclo a un circuito simple si no existen vértices repetidos excepto el primero y el último.

Un ciclo por decir de otra forma, es un camino en el cual el primer y el último vértice son iguales. Se llama ciclo simple si el camino es simple. En grafos no dirigidos es necesario que las aristas sean diferentes.

Dados dos vértices (V, W) se dice que están conectados si existe un camino de V a W

Existen diferentes tipos de ciclos:

· Ciclo Simple: Es el ciclo que a su vez es una cadena simple. Es un camino de longitud mayor o igual a 1, el cual comienza y termina en el mismo vértice.

· Ciclo de Euler: es un ciclo que pasa exactamente una vez por cada uno de los arcos. Es un camino euleriano que comienza y termina en el mismo vértice. Un grafo que admite un ciclo euleriano se dice que es un grafo euleriano

· Ciclo Hamiltoniano: es un ciclo que pasa exactamente una vez or cada uno de los vértices del grafo.

Grafo Conexo

Un grafo es conexo si cualquier vértice V le pertenece al conjunto de vértices y es alcanzable por algún otro.

Otra definición es que es un grafo no dirigido de tal modo que para cualquier par de nodos existe al menos un camino que los une.

Un grafo no dirigido es conexo si existe un camino entre cualquier par de nodos que forman el grafo. Ejemplo:

Grafo conexo Grafo no conexo con dos componentes conexas

Un grafo es doblemente conexo si para cada par de vértices está conectado por al menos dos caminos disjuntos, es decir, se dice que es conexo y no existe un vértice tal que al sacarlo el grafo resultante sea disconexo.

Tema opcional: Un grafo es completo si existen aristas uniendo todos los pares posibles de vértices, es decir, si para todo par de vértices (a, b) debe tener una arista e que los une.

Existe también llamado Grafo fuertemente conexo que es un grafo dirigido tal que para cualquier par de nodos existe un camino que los une.

Arbol

Un árbol es un tipo de grafo que no contiene ciclos, es decir es un grafo acíclico, pero a su vez es conexo. La diferencia entre los dos grafos es que en donde se puede notar que ninguno de los dos contiene repeticiones o ciclos.

Un árbol consta de un conjunto finito de elementos, llamados nodos y de un conjunto finito de líneas dirigidas, llamadas ramas, que conectan los nodos. El número de ramas asociado con un nodo es el grado del nodo.

Su importancia radica en que los árboles son grafos que conectan todos los vértices utilizando el menor número posible de aristas.

Un importante campo de esta aplicación es el análisis filogenético, que se aplica a la averiguación del parentesco entre especies, aunque se ha usado también, por ejemplo, en el estudio del parentesco entre lenguas.

Un árbol es un conjunto de uno o más nodos tales que:

1. Hay un nodo diseñado especialmente llamado raíz

2. Los nodos restantes se dividen en n >= 0 conjuntos distintos, T1 … Tn, tal que cada uno de estos conjuntos es un árbol. A T1 … Tn se les denomina subárboles del raíz

Si un árbol no está vació, entonces el primer nodo se llama raíz

Características y propiedades de los árboles.

· Todo árbol que no es vacío, tiene un único nodo raíz.

· Un nodo X es descendiente directo de un nodo Y, si el nodo X es apuntado por el nodo Y. en este caso es común utilizar la expresión X es hijo de Y.

· Un nodo X es antecesor directo de un nodo Y, si el nodo X apunta al nodo Y. en ese caso es común utilizar la expresión X es padre de Y.

· Todos los nodos que son descendientes directos (hijos) de un mismo nodo (padre), son hermanos.

· Todo nodo que no tiene ramificaciones (hijos), se conoce con el nombre de terminal u hoja.

· Todo nodo que no es raíz, ni terminal u hoja se conoce con el nombre de interior.

· Grado es el número de descendientes directos de un determinado nodo. Grado del árbol es el máximo grado de todos los nodos del árbol, es decir, el grado más alto entre todos los nodos.

· Nivel es el número de arcos que deben ser recorridos para llegar a un determinado nodo. Por definición la raíz tiene nivel 1.

· Altura del árbol es el máximo número de niveles de todos los nodos del árbol.

RECORRIDOS DE UN ÁRBOL.

En una estructura lineal resulta trivial establecer un criterio de movimiento por la misma para acceder a los elementos, pero en un árbol esa tarea no resulta tan simple.

Existen distintos métodos útiles en que podemos sistemáticamente recorrer todos los nodos de un árbol. Los tres recorridos más importantes se denominan prefijo, infijo y posfijo, aunque hay otros recorridos como el recorrido por niveles.

Si consideramos el esquema general de un árbol tal como muestra la figura siguiente, los recorridos se definen como sigue:

En “prefijo” viaja a través del árbol binario desplegando el contenido en la raíz, después viaje a través del nodo izquierdo y después a través del nodo derecho.

El listado en prefijo es:

Si el árbol tiene un único elemento, dicho elemento es el listado en prefijo.

Si el árbol tiene más de un elemento, el listado en prefijo es listar el nodo raíz seguido del listado en prefijo de cada uno de los subárboles hijos de izquierda a derecha.

El “infijo” viaja a través del árbol binario desplegando el contenido en el nodo izquierdo después la raíz y finalmente viaja a través del nodo derecho.

El listado en infijo es:

Si el árbol tiene un único elemento, dicho elemento es el listado en infijo.

Si el árbol tiene una estructura, el listado en infijo es listar el subárbol A1 en infijo y listar el nodo raíz seguido del listado en infijo de cada uno de los subárboles hijos de izquierda a derecha restantes.

El “posfijo” viaja a través del árbol binario desplegando el contenido en el nodo izquierdo después el nodo derecho y finalmente viaja a través de la raíz.

El listado en posfijo es:

Si el árbol tiene un único elemento, dicho elemento es el listado en posfijo.

Si el árbol tiene una estructura, el listado en posfijo es listar en posfijo cada uno de los subárboles hijos de izquierda a derecha seguidos por el nodo raíz.

Tema opcional: Los bosques de árboles son un caso similar a los árboles, son acíclicos, pero no son conexos.

Tema opcional: Los Árboles Binarios son árboles ordenados de grado dos. En un árbol binario cada nodo puede tener como máximo dos subárboles y estos se distinguen entre sí como el subárbol izquierdo y el subárbol derecho, según su ubicación con respecto al nodo raíz.

Los árboles binarios tienen múltiples aplicaciones. Por ejemplo: para representar la solución de un problema, en el cual existen dos posibles alternativas; para representar un árbol genealógico, un árbol binario de búsqueda y un árbol binario que represente expresiones.

Existen tres tipos de árboles binarios

· Árboles binarios distintos: Cuando en sus estructuras la distribución de nodos y arcos son diferentes.

· Árboles binarios similares: Cuando sus estructuras son idénticas, pero la información que contienen sus nodos difiere entre sí.

· Árboles binarios equivalentes: Son aquellos que son similares y además los nodos contienen la misma información.

Grafo Completo

Se dice que un grafo es completo si el vértice v del otro vértice G es adyacente de los otros vértices de G.

Un Grafo Completo es un grafo no direccionado donde existe un arco entre cada par de vértices cualesquiera del mismo.

Un grafo completo es un grafo simple en el que todo el par de nodos está unido por una arista y se representa con Kn.

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

Según el número de aristas que contiene, un grafo será completo si cuenta con todas las aristas posibles, es decir, si todos los nodos están conectados con todas las aristas.

Un grafo es disperso si tiene relativamente pocas aristas y si el grafo es denso si le faltan pocas para ser completo.

El número máximo de arcos que puede tener un grafo de n vértices es n(n-1)/2.

Grafo Etiquetado

Un grafo etiquetado es la asignación de etiquetas representado mediante enteros, a las aristas o vértices o ambos de un grafo.

El término grafo etiquetado generalmente se refiere a un grafo con vértices etiquetados con todas las etiquetas distintas.

Los grafos puede ser equivalentemente etiquetado mediante enteros consecutivos desde 1 hasta n, donde n es el número de vértices en el grafo.

Para muchas aplicaciones, a las aristas y los vértices le corresponden etiquetas que tienen un significado en el dominio asociado.

Existen 3 tipos de etiquetado:

· Etiquetado elegante

La figura muestra un etiquetado elegante. Las etiquetas de los vértices están en negro, las etiquetas de las aristas en rojo.

Un grafo es llamado etiquetado elegante cuando sus vértices son etiquetados desde 0 a ||E||, el tamaño del grafo, y este etiquetado induce un etiquetado de aristas desde 1 a ||E||.

Para cualquier arista e, las etiquetas de e son la diferencia positiva entre dos vértices incidentes con “e”.

Si “e” es incidente con los vértices etiquetados “k” y “j”, e será etiquetado como ||k - j||. Así un grafo “G”: = (V, E) es elegante si y sólo si existe una inyección que induce una bisección de E a los enteros positivos hasta ||E||.

· Etiquetado armonioso

Un grafo armonioso es un grafo con “k” aristas que permiten una inyección de los vértices de “G” al grupo de enteros modulo “k” que induce una bisección entre las aristas de “G” y los enteros positivos hasta ||E||.

Para cualquier arista e, los etiquetados de e son la suma de las etiquetas de dos vértices incidentes con “e”.

· Coloración de grafos

La coloración de grafos es un caso muy especial para los grafos etiquetados, los vértices adyacentes y las aristas coincidentes deben tener diferentes etiquetas.

Multigrafo

Un Multígrafo es cuando se acepta más de un arco uniendo dos vértices. En términos formales, no son grafos. Un multígrafo es un grafo que consta de segmentos múltiples y lazos.

Otra definición similar es que un multígrafo es un grafo en el que hay pares de vértices unidos por más de una arista, es decir, que tiene aristas múltiples.

La imagen muestra un multígrafo con múltiples aristas en rojo y tres bucles en azul. No todos permiten multígrafos con bucles.

Esta imagen es un multígrafo con dos pares de aristas

Esto resulta sencillo transformar un pseudografo o un multígrafo en un grafo añadiendo un vértice en medio de cada lazo o de algunas aristas múltiples. En las siguientes figuras, añadiendo vértices y uniéndolos mediante aristas, se han convertido el pseudografo y el multígrafo en grafos.

Este es un grafo generado a partir de un Pseudografo de 3 lazos

Este es un grafo generado a partir de un Multígrafo con dos pares de aristas

Un multígrafo M se dice que es finito si tiene un número finito de nodos y de aristas.

Observe que un grafo G con un número finito de nodos debe automáticamente un número finito de aristas y por tanto debe ser finito.

Pero esto no es cierto para un multígrafo “M”, ya que “M” puede tener múltiples aristas.

A menos que se indique lo contrario, los grafos y multígrafos de este texto siempre serán finitos.

Tema original: Un multígrafo es un grafo dirigido que está diseñado para tener aristas múltiples, es decir, para tener aristas con los mismos nodos iniciales y finales.

Un multígrafo G es un par ordenado de G = (V,A) donde:

· “V” es un conjunto de vértices o nodos

· “A” es un multiconjunto de pares ordenados de nodos, llamados aristas dirigidas, arcos o flechas.

Un pseudografo es un grafo en el que hay aristas o lazos que tienen el mismo extremo.

Un dígrafo es un grafo donde a cada arista se le indica un sentido mediante una flecha.

Los multidigrafos o pseudomultidigrafos son combinaciones de los otros tipos de grafos. Un multidigrafo mixto G = (V, E, A) tiene la misma definición que un grafo mixto, es decir, tiene la capacidad de poseer al mismo tiempo las aristas dirigidas “A” y las aristas no dirigidas “E”.