Programación de estructuras de datos

Lista Circular

2020-09-19T13:46:00.002-07:00

Lista Circular

Una lista circular es una lista donde el último elemento apunta hacia la primera posición. Existen varias variantes de de este tipo de lista:

La Circular Simplemente Enlazada está compuesta por elementos llamados nodos, donde cada nodo almacena un dato y la referencia a el elemento siguientes. El último nodo tiene referencia al primer nodo. Teóricamente en lo único que se diferencia a la lista Simplemente enlazada es en esta última posición ya que no contienen en esta posición referencia nula.

La Circular Doblemente Enlazada está compuesta por elementos llamados nodos, donde cada nodo almacena un dato, la referencia al elemento siguiente y al elemento anterior. El último nodo tiene referencia al primer nodo y el primer nodo tiene de referencia como nodo anterior al último nodo. Teóricamente este tipo de lista se diferencia a la lista Doblemente Enlazada en la última posición ya que no contienen referencia nula al siguiente nodo y en la primera posición que no contiene referencia anterior nula.

Operaciones Básicas de la Lista.

Al igual que los otros tipos de listas, la lista circular implementa los métodos básicos: adicionar, insertar, eliminar, obtener, etc.

Lista Circular Simplemente Enlazada.

A continuación, se muestra la declaración de la clase ListaSECircular (Escrita en lenguaje Java):

public class ListaSECircular<T> implements ILista<T>

{

private NodoSE<T> primero;

// Constructor ......

public ListaSECircular() {

}

// Metodos ......

}

Esta clase al igual que la lista simplemente enlazada tiene un atributo llamado primero que es un nodo simplemete enlazado el cual contiene un dato y la referecia a otros nodo. A continuacion veremos la representación e implementación del mismo:

Representación:

Implementación (Escrita en lenguaje Java):

1 public class NodoSE<T> {

3 private T dato;

4 private NodoSE<T> siquiente;

6 public NodoSE(T dat, NodoSE<T> sig) {

7 dato = dat;

8 siquiente = sig;

9 }

10 public NodoSE(T dat) {

11 dato = dat;

12 }

14 public T getDato() {

15 return dato;

16 }

18 public void setDato(T dato) {

19 this.dato = dato;

20 }

22 public NodoSE<T> getSiquiente() {

23 return siquiente;

24 }

26 public void setSiquiente(NodoSE<T> siquiente) {

27 this.siquiente = siquiente;

28 }

¿Cómo recorrer la Lista Circular Simplemente Enlazada?

Para llegar a un elemento en particular o al último nodo de la lista Circular Simplemente Enlazada, es necesario recorrerla. Como los enlaces en la lista simplemente enlazada solo van hacia adelante hay que comenzar por la única referencia conocida: el primer nodo (atributo primero).

El gráfico siguiente muestra como llegar al último nodo de la Lista Circular Simplemente Enlazada, a través de una referencia a los Nodos llamado cursor:

El código siguiente (Escrito en lenguaje Java) recorre la lista hasta el final:

1 NodoSE<T> cursor = primero; // inicializacion de cursor

2 while (!cursor.getSiquiente().equals(primero)) // condicion de parada

3 {

4 cursor = cursor.getSiquiente(); // pasando al siguiente elemento

5 }

Línea 1: Se inicializa un objeto de tipo NodoSE llamado cursor que apunta en el nodo primero.

Línea 2: Comienza un ciclo repetitivo con el objetivo de recorrer la lista a través del objeto cursor. La condición de que no se llegue al final no es más que la referencia al siguiente nodo sea el primero (definición de Lista Circular)

Línea 4: En esta línea se hace apuntar cursor al siguiente nodo.

Implementación del método: Adicionar (Escrita en lenguaje Java).

1 public void Adicionar(T dato)

2 {

3 if (primero == null) // caso 1 ......

4 {

5 primero = new NodoSE<T>(dato); // construir un nodo con el dato entrado

6 primero.setSiquiente(primero); // referencia al primer elemento

7 }

8 else // caso 2 ......

9 {

10 NodoSE<T> cursor = primero; // paso 1

11 while (!cursor.getSiquiente().equals(primero)) // paso 1

12 {

13 cursor = cursor.getSiquiente(); // paso 1

14 }

16 NodoSE<T> aux = new NodoSE<T>(dato, primero); // paso 2

17 cursor.setSiquiente(aux); // paso 3

18 }

19 }

Cuando vamos a adicionar un nuevo elemento hay dos posibles estados en los que puede encontrarse la lista circular:

Caso 1: la lista está vacía. El primer elemento que no es mas que el atributo primero es nulo es decir: primero = null.

public void Adicionar(T dato)

{

// caso 1 ......

if (primero == null)

{

//......

En este caso:

Linea 5: Se construye un nuevo elemento y se coloca en la primera posición.

5 primero = new NodoSE<T>(dato); // construir un nodo con el dato entrado

Linea 5: Se le da como referencia siguiente al primer elemento que a la vez es el último la del él mismo.

6 primero.setSiquiente(primero); // referencia al primer elemento

Posible error que se puede cometer en este caso 1:

Se podría pensar que se pueden hacer estos 2 pasos en uno solo:

primero = new NodoSE<T>(dato,primero); // unico paso

Es decir pasar directo el dato y la referencia de primero al construir el nuevo nodo. Error garrafal ya que hasta que no se iguale primero con el nuevo nodo que se construye, este poseerá referencia nula, es decir que cuando pasamos por parámetro en el constructor de nodo a primero este todavía es nulo. Lo que resultaría si lo hacemos así es lo siguiente:

Caso 2: la lista contiene al menos 1 elemento. El atributo primero no es nulo.

1 public void Adicionar(T dato)

2 {

3 if (primero == null) // caso 1 ......

4 {

5 primero = new NodoSE<T>(dato); // paso 1

6 primero.setSiquiente(primero); // paso 2

7 }

8 else // caso 2 ......

9 {

En este caso:

Línea 10: se inicializa una variable de tipo NodoSE en el nodo primero.

Línea 11: Comienza un ciclo repetitivo mientras no se llegue a la posición final. La condición de que no se llegue al final no es más que el siguiente nodo sea primero (definición de Lista Circular)

Línea 21: En esta línea se pasa a apuntar cursor al siguiente nodo.

En el paso 1: se busca el nodo que se encuentra en el final, esto se hace a través de un nodo temporal que recorrer la lista de nodos desde el primero hasta que encuentra el último que apunta nuevamente al primero nodo.

8 else // caso 2 ......

9 {

10 NodoSE<T> cursor = primero; // paso 1

11 while (!cursor.getSiquiente().equals(primero)) // paso 1

12 {

13 cursor = cursor.getSiquiente(); // paso 1

14 }

En el paso 2: se construye el nuevo nodo a adicionar, pasándole el dato entrado por parámetro y como referencia siguiente el primer nodo.

16 NodoSE<T> aux = new NodoSE<T>(dato, primero); // paso 2

En el paso 3: el último nodo se le pasa por referencia siguiente el nuevo nodo creado en el paso 2. Este es el último paso, el código completo se ve a continuación:

17 cursor.setSiquiente(aux); // paso 3

Implementación del método Eliminar.

El método Eliminar, es capaz de eliminar el elemento de la listas en una posición deseada la cual debe ser válida.

1 public void Eliminar(int pos) throws ListaVacia, PosicionNoValida

2 {

3 if (primero == null) // caso 1 ......

4 throw new ListaVacia();

5 // caso 2 ......………………………………………….

6 int longitud = Longitud(); // Paso 1

7 if (pos < 0 || pos > longitud) // Paso 1

8 throw new PosicionNoValida();// Paso 1

10 if (pos == 0) // Paso 2

11 {

12 if (longitud == 1) // paso 2.1

13 {

14 primero = null; // paso 2.1

15 }

16 else // paso 2.2

17 {

18 // buscando la última posición

19 NodoSE<T> cursor = primero; //paso 2.2

20 while (!cursor.getSiquiente().equals(primero)) //paso 2.2

21 {

22 cursor = cursor.getSiquiente(); //paso 2.2

23 }

24 primero = primero.getSiquiente(); //paso 2.2

25 aux.setSiquiente(primero); //paso 2.2

26 }

27 }

28 else // Paso 3

29 {

30 NodoSE<T> cursor = primero; // Paso 3.1

31 for (int i = 0; i < pos - 1; i++) // Paso 3.1

32 {

33 cursor = cursor.getSiquiente(); // Paso 3.1

34 }

36 cursor.setSiquiente(cursor.getSiquiente().getSiquiente()); // Paso 3.2

37 }

38 }

Cuando vamos a eliminar un elemento hay dos posibles estados en los que puede encontrarse la lista circular:

Caso 1: El primer elemento es nulo, la lista está vacía, es decir: primero = null. En este caso no se puede eliminar elemento alguno, y estaremos en presencia de un error que debe ser tratado.

1 public void Eliminar(int pos)throws ListaVacia, PosicionNoValida

2 {

3 if (primero == null) // caso 1 ......

4 throw new ListaVacia();

5 // caso 2 ...... ………………………………………….

Caso 2: El primer elemento no es nulo, por lo tanto la lista contiene al menos 1 elemento.

En este caso:

En el paso 1: se verifica que la posición entrada por parámetro este en el rango de 0 a la longitud que posee la lista. En caso de no cumplirse esta premisa se lanza una excepción.

1 public void Eliminar(int pos) throws ListaVacia, PosicionNoValida

2 {

3 if (primero == null) // caso 1 ......

4 throw new ListaVacia();

5 // caso 2 ......………………………………………….

6 int longitud = Longitud(); // Paso 1

7 if (pos < 0 || pos > longitud) // Paso 1

8 throw new PosicionNoValida(); // Paso 1

En el paso 2: se pueden se verifica que la posición a eliminar es 0:

10 if (pos == 0) // Paso 2

En el paso 2.1: se verifica que la longitud de la lista sea 1, en este caso se elimina el primer elemento y queda vacía la lista.

10 if (pos == 0) // Paso 2

11 {

12 if (longitud == 1) // paso 2.1

13 {

14 primero = null; // paso 2.1

15 }

En el paso 2.2: la longitud de la lista es mayor a 1, en este caso se elimina el primer elemento y se actualiza la referencia siguiente del último elemento.

16 else // paso 2.2

17 {

18 // buscando la última posición

19 NodoSE<T> cursor = primero; //paso 2.2

20 while (!cursor.getSiquiente().equals(primero)) //paso 2.2

21 {

22 cursor = cursor.getSiquiente(); //paso 2.2

23 }

24 primero = primero.getSiquiente(); //paso 2.2

25 cursor.setSiquiente(primero); //paso 2.2

26 }

27 }

De la línea 18 a la 23 a través de un nodo auxiliar se busca el nodo de la última posición de la lista.

En la línea 24 se hace a apuntar el primer nodo al siguiente, con el propósito de eliminar el primero.

En la línea 25 se hace a apuntar el último nodo al primero y con esto queda todo listo.

En el paso 3: la longitud de la lista es mayor a 1 y la posición del elemento a eliminar es mayor que 0.

En el paso 3.1: se hace apuntar a un nodo auxiliar en la posición anterior a la que se desea eliminar.

28 else // Paso 3

29 {

30 NodoSE<T> cursor = primero; // Paso 3.1

31 for (int i = 0; i < pos - 1; i++) // Paso 3.1

32 {

33 cursor = cursor.getSiquiente(); // Paso 3.1

34 }

En el paso 3.2: se cambia la referencia siguiente del nodo auxiliar, al elemento siguiente del que se desea eliminar. Con esto concluye el método eliminar:

36 cursor.setSiquiente(cursor.getSiquiente().getSiquiente()); // Paso 3.2

37 }

38 }

Implementación del método Longitud.

El método Longitud, es capaz de consultar todos los nodos y hacer un conteo que permite saber la cantidad de elementos de la lista.

1 public int Longitud()

2 {

3 // caso 1 ............

4 if (primero==null)

5 return 0;

6 // caso 2 ............

7 NodoSE<T> cursor = primero;

8 int cant = 1;

9 while(!cursor.getSiquiente().equals(primero))

10 {

11 cursor = cursor.getSiquiente();

12 cant++;

13 }

14 return cant;

15 }

Cuando vamos a consultar la longitud dos posibles estados en los que puede encontrarse la lista circular:

Caso 1: El primer elemento es nulo, la lista está vacía, es decir: primero = null. En este caso la longitud es 0 por supuesto.

1 public int Longitud()

2 {

3 // caso 1 ............

4 if (primero==null)

5 return 0;

Caso 2: El primer elemento no es nulo, la lista posee al menos un nodo. En este caso la para calcular la longitud se recorren todos los nodos a travez de un nodo temporal nombrado cursor.

1 // caso 2 ............

2 NodoSE<T> cursor = primero; // Inicializacion de cursor

3 int cant = 1; // contandor en valor 1 contando el primero

4 while(!cursor.getSiquiente().equals(primero)) // condicion de recorrido

5 {

6 cursor = cursor.getSiquiente(); // pasando al siguiente nodo

7 cant++; // contando los nodos

8 }

9 return cant; // retornando el valor

10 }

En este caso:

Línea 17: se inicializa una variable de tipo NodoSE en el nodo primero.

Línea 18: Luego se inicializa un contador en 1 pues ya estaría contando que hay un elemento en la primera posición.

Línea 19: Comienza un ciclo repetitivo mientras no se llegue a la posición final. La condición de que no se llegue al final no es más que el siguiente nodo sea primero (definición de Lista Circular)

Línea 21: En esta línea se pasa a apuntar cursor al siguiente nodo.

Línea 22: Se va incrementando la cantidad de nodos.

Línea 24: Finalmente se retorna la cantidad.

Estructuras de datos para la representación de grafos

2010-12-10T16:26:00.000-08:00

Existen 2 estructuras de datos muy conocidas para la representación de grafos. Estas son:
Lista de vértice – Matriz de adyacencia y Lista vértices – Lista de adyacencia

1- Lista de vértice – Matriz de adyacencia

1.1- Grafo no dirigido y no ponderado.

La forma más sencilla de representar un grafo es usando una lista de vértices que almacena los vértices y una matriz que almacena las aristas.

Fig. 1 Grafo no dirigido no ponderado

Para mostrar de una forma sencilla como es la representación hagámoslo con el grafo de la figura 1.

La lista de vértices del grafo es L = {a,b,c,d,e,f}
La matriz de adyacencia estaría compuesta por una tabla de 6x6, la dimensión de la matriz es el número de vértices del grafo. Gráficamente se vería como muestra en la figura 2.

Fig.2 Matriz de adyacencia

Esta matriz contiene las aristas del grafo, el ejemplo de la figura 1 es de tipo No ponderado, No dirigido. Los ceros indican que no existen aristas entre las componentes Fila – Columna, por ejemplo en la intersección del vértice a – c hay un cero pues no hay arista entre a y c ; pero también hay un cero en la intercepción c - a . Recordemos que cuando el grafo no es dirigido no hay diferencia entre un arco de la forma <a,b> y <b,a>
Cuando existe un arco entre 2 vértices entonces se coloca el valor 1. Ejemplo <a,b> y <b,a>

1.2- Grafo no dirigido, ponderado

Fig. 3 Grafo no dirigido ponderado

En el caso de un grafo ponderado lo único que cambia es que en vez de colocar un 1 en las intercepciones de aristas, se coloca el peso que posee dicha arista.

La lista de vértices de este grafo L = {a,b,c,d,e,f}
La matriz de adyacencia se vería como muestra en la figura 4.

Fig.4 Matriz de adyacencia para grafo ponderado

1.3- Grafo dirigido, no ponderado.

Fig.5 Grafo dirigido no ponderado

En un Grafo dirigido hay que tener en cuenta el orden de las aristas, para este grafo de la figura 5 , existe la arista formada por el par <a,b>; pero no existe <b,a> . Por lo tanto en la matriz se debe colocar un 1 solo en el par <a,b> y un cero en el par <b,a>. Ver en la figura 6 que existe el valor uno (1) en la intercepción fila (a) y columna (b); sin embargo en la intercepción fila (b) y columna (a) hay un cero (0)

La lista de vértices de este grafo L = {a,b,c,d,e,f}
La matriz de adyacencia se vería como muestra en la figura 6.

Fig.6 Grafo dirigido no ponderado

1.4- Grafo dirigido, ponderado.

Ya debes imaginar cómo representar un Grafo dirigido y ponderado. Simplemente igual al Grafo dirigido y no ponderado, solo cambia el uno (1) por el peso de las aristas en los valores de la matriz. Ver el ejemplo de la figura 7 representado en tabla

Fig.7 Grafo dirigido ponderado

La lista de vértices de este grafo L = {a,b,c,d,e,f}
La matriz de adyacencia se vería como muestra en la figura 8.

Fig.8 Matriz de adyacencia en el grafo dirigido ponderado

2- Lista de vértice – Lista de adyacencia

Otra estructura de datos que se utiliza para los grafos es la Lista de vértice – Lista de adyacencia. En esta se estructura se utiliza una lista de vértices al igual que en Lista de vértice – Matriz de adyacencia; pero no se utiliza una matriz sino una lista de listas de vértices en la que se almacenan las relaciones entre vértices que como ya sabemos son los arcos o aristas.

En esta representación con Lista de adyacencia solo veremos los ejemplos de grafos no dirigidos, no ponderado y no dirigido ponderado ya que las otras 2 combinaciones son en esencia iguales. Lo diferencia solo la da si el grafo es ponderado o no pues esta condición como se verá adelante cambia la estructura de dato, no siendo así con si es dirigido o no dirigido.

2.1- Grafo no dirigido y no ponderado.

Fig. 9 Grafo no dirigido no ponderado

Veamos como resultaría la estructura para el grafo de figura 9.

En la figura 10 de abajo, vemos la representación grafica de la lista de vértices, pero hemos en este caso representado también las posiciones de cada vértice en la lista, pues esta posición tendrá mucha importancia en la lista de adyacencia. Las posiciones comienzan en 0 ya que por lo general todas las listas que se usan en cualquier lenguaje de programación comienzan en posición 0, aunque en teóricamente en muchos libros la primera posición es 1. Por consenso siempre asumo que las listas comienzan en 0 para no chocar en la práctica con otra realidad. Esto ha sido causa de muchas discusiones entre mis colegas; pero yo soy más práctico que teórico.

Fig.10 Lista de vértices y sus posiciones

En la figura 11 vemos la representación de la lista de adyacencia, la explico en detalles a continuación:
Una lista de adyacencia es una lista de lista, es decir una lista donde cada elemento posee otro listado con los vértices adyacentes.
Como ya vimos en la figura 10 cada vértice tiene asociado una posición en la lista de vértices, por lo tanto el vértice (a) tiene posición cero (0) , el (b)=> (1) y así sucesivamente.
Ahora sigue con la vista la figura 11, lo que ves es una lista de listas , la primera fila o la lista que está en posición (0) contiene los vértices que poseen arista con el vértice (a) recordemos que el vértice (a) en la Lista de vértices tiene posición (0) , veremos que en esa lista aparecen los siguientes números: (1),(3),(4) ; estos son las posiciones correspondientes a los vértices adyacentes (que tiene aristas) con el vértice (a) que son : (b) , (d) y (e).
Entonces de seguro ya te das cuenta cómo funciona esta estructura, la segunda lista contiene las posiciones los vértices adyacentes a al vértice (b) y así sucesivamente hasta el último vértice en la lista que el (f).

Fig.11 Lista de adyacencia

2.2- Grafo no dirigido y ponderado.

La representación del grafo ponderado en Lista de vértice – Lista de adyacencia, tiene una diferencia en cuanto a lo que almacenamos en la lista de lista o lista de adyacencia; la razón es muy simple y es que necesitamos almacenar también el peso de las aristas por lo que necesitaremos construir una estructura que sea capaz de hacer esto

Fig. 12 Grafo no dirigido ponderado

Pues la explicación en las misma que con el grafo anterior pero en vez de almacenar las posición de los vértices adyacente en la lista de lista, debemos crear un estructura que contenga la posición y el peso. Por ejemplo ahora los adyacentes al vértice (a) que es la posición (0) siguen siendo (1),(3),(4) es decir los vértices (b) ,(d), (e). Pero el peso con el vértice (1) es 2 por eso en la representación grafica de la figura 13, dividimos las celdas de la lista en dos partes la primera es la posición del vértice y la segunda en negro el peso.

Fig.13 Lista de adyacencia

Fig.14 Lista de vértices

Recorridos en grafos

2010-12-09T18:57:00.000-08:00

En este artículo vernos 2 recorridos distintos que se pueden realizar sobre los grafos. Los recorridos son algoritmos que se llevan a cabo sobre el grafo y que devuelven una lista de vértices con todos los vértices del grafo.

Estos recorridos pueden ser usados en distintos algoritmos para la solución de problemas particulares.

Recorrido en profundidad

Definición del método:RecorrerEnProfundidad (RP)

Para cada v que pertenece a la lista de vértices; marcar v como no visitado
Para cada v que pertenece a la lista de vértices hacer:
Si v no está visitado

               Entonces BPP(v)
Luego el método BPP realiza las siguientes acciones:

Adicionar al recorrido
Marcar v como visitado
Para cada vértice w adyacente a v hacer:

Si w no está visitado entonces BPP(w) // esta es al recursividad

A continuación un ejemplo de este recorrido sobre el grafo de la figura 1.

Fig. 1 Grafo ejemplo

Árbol de las llamadas recursivas al método Búsqueda en Profundidad del Primero BPP(v).

Fig. 2 Gráfico del recorrido en profundidad del grafo de la figura 1

En la siguiente tabla se muestran las llamadas recursivas del ejercicio, en la primera columna las llamadas recursivas del método BPP, en la segunda columna los vértices adyacentes del vértice que llamamos en el método BPP y noten que se pintan en rojo los que ya están marcado, es decir lo que ya están en el recorrido que se muestra en la tercera columna:

Tabla de que representan las llamadas recursivas.

De las llamadas recursivas se forman y o varios árboles en dependencia del grafo donde el nodo padre es el vértice que estamos llamando en el método BPP y los subArboles o hijos son los vértices adyacentes al padre y que no están marcados aun , es decir no están aun en el recorrido . Y curiosamente la unión de los recorridos en preOrden, forman el recorrido en profundidad del grafo:

Fig. 2 Árboles de llamadas BPP

Recorridos PreOrden de los arboles:

a) a, b, c, f
b) e

Y al unir los recorridos comenzando por el primero nos queda: a, b, c, f, d, e. El recorrido en profundidad del grafo.

Recorrido a lo ancho

Definición del método: RecorrerAncho (RP)

   Paso 1 (Inicialización):
                Para cada vértice (v) que pertenece a la lista de vértices (V)

Marcar a v como no visitado.

Paso 2 (Recorrido):
               Para cada v pertenece a V,

Si v no está visitado entonces

Hacer la Búsqueda del Primero a lo Ancho (BPA) partiendo por v.
El algoritmo de la BPA es un algoritmo que recibe como parámetro un vértice v del grafo. No es recursivo, y para su ejecución se auxilia de una instancia del TDA Cola, que sería una cola de vértices. El algoritmo BPA(v) presenta los siguientes pasos:

Paso 1: Inicializar Cola vacía
Paso 2: Marcar v como visitado.
Paso 3: Adicionar v a Cola.
Paso 4: Mientras Cola no es vacía hacer
4.1) Extraer un vértice de Cola. Sea u el vértice extraído.
4.2) Para cada w adyacente a u hacer
4.2.1) Si w no está visitado entonces
4.2.1.1) Marcar w como visitado
4.2.1.2) Adicionar w a Cola.

En la figura 3 se muestra la representación de un recorrido a la ancho de un grafo mostrando paso por paso el estado de la cola en las llamadas al método BPA.

Fig. 3 Recorrido a lo ancho

Definición y orígenes de los grafos

2010-12-09T14:40:00.000-08:00

En múltiples problemas computacionales y de la vida práctica también se necesitaran establecer relaciones que sean simétricas y que provoquen ciclos en la estructura. Por ejemplo "X es amigo de Y". Ver fig. 1

Fig.1 Relación de amistad

Primer Registro Histórico de del origen de los grafos

Se dice que el primero en trabajar con de grafos fue el famoso matemático Leonhard Euler en 1736.

En la ciudad de Kaliningrado (antigua Königsberg) había siete puentes sobre el río Pregel. Estos se conectaban como se muestra en la figura 2.
Euler se preguntó si sería posible comenzar un paseo desde cualquier punto y atravesar cada puente una y sólo una vez, regresando al punto departida.

Al final de este artículo vernos la solución de que Euler encontró a este problema, por medio de un grafo.

Fig.2 Los puentes de Königsberg

Definición de grafo
Un grafo G es un par G = (V, A) donde V es un conjunto finito de elementos que se denominan Vértices y A es un conjunto de pares no ordenados <x,y>, donde x pertenece a V y y pertenece a V, denominados Aristas o Arcos.

Fig.3 Ejemplo de grafo

Definición de Grafo Dirigido
Un grafo dirigido G es un par G = (V, A) donde V es un conjunto finito de elementos que se denominan Vértices y A es un conjunto de pares ordenados <x,y>, donde x pertenece a V y y pertenece a V, denominados Aristas o Arcos dirigidos.

Para los grafos dirigidos tiene relevancia el orden en que se enuncian los vértices para describir una arista. Es decir, los pares <x,y> y <y,x> se refieren a aristas distintas. En la figura 4 se muestra un grafo dirigido.

Fig.4 Ejemplo de grafo dirigido

¿Qué es un Grafo Ponderado?

Un grafo ponderado G es un par G = (V, A) donde V es un conjunto finito de elementos que se denominan Vértices, A es un conjunto de pares no ordenados <x,y>, donde x pertenece a V , y pertenece a V, denominados Aristas o Arcos, donde a cada elemento de A (a cada arista) se le asocia un valor real positivo. En la figura 5 se muestra un grafo ponderado.

Fig.5 Ejemplo de grafo ponderado

El peso asociado a cada arista puede interpretarse como el costo de trasladarse de un vértice a otro. Dicho costo puede ser costo en tiempo, distancia, costo en algún determinado recurso, etc.

Terminologías utilizadas en los grafos

Vértices Adyacentes:

En un grafo G = (V, A), un vértice y es adyacente a otro vértice x si el par <x,y> es una arista del grafo G.

Fig.6 Ejemplo vértices adyacentes y no adyacentes

Camino:
En un grafo G = (V, A) un camino de longitud N (N >= 0) es una sucesión de vértices V0, V1, …, Vn donde cada vértice Vk es adyacente Vk-1 para 1 <= k <= N. En este caso se dice que el camino va de V0 a Vn.

Fig.7 Ejemplo de camino

Camino simple:
Un camino es simple si los vértices que lo componen son distintos excepto posiblemente el primero y el último.

Fig.8 Ejemplo de camino simple

Longitud de un camino:

La longitud de un camino es el número de arcos que lo componen. El camino en amarillo de la figura 8 tiene longitud 5.

Ciclo (o circuito):

Es un camino que empieza y acaba en el mismo vértice. Los ciclos de longitud 1 se denominan bucles.

Fig.9 Ejemplo de ciclos

Grafo conexo (conectado):

Un grafo es conexo si existe al menos un camino de cualquier vértice a cualquier otro.

Fig.10 Grafo conexo.

Solución de Euler a los puentes de Königsberg

Al convertir los puentes de Königsberg en un grafo queda como se muestra en la figura 11. Los puentes son las aristas y los vértices son las zonas de tierra.

Euler inteligentemente se percató de que el camino sin pasar 2 veces por una misma arista en un grafo (camino Euleriano) solo es posible cuando los vértices del grafo, salvo a lo más en dos, converjan un números pares de aristas. La razón es muy simple: al llegar a un vértice se necesita poder salir por una arista distinta a la que se llega, por lo tanto el número de aristas que convergen en un vértice debe ser par; pero esto no es necesario en el vértice inicial y el vértice final.

En el grafo formado por los puentes de Königsberg , a cada uno de los nodos concurre un número impar de aristas (3, 5, 3, 3). Por lo tanto es imposible realizar el paseo que Euler deseaba hacer en dichos puentes.

Fig. 11 Grafo que representa los puentes de Königsberg