Caminos y Circuitos

Circuito de Euler

Es aquel ciclo que recorre todos los vértices pasando por todos los lados solamente una vez.

Un grafo tiene un circuito de Euler si y sólo si es conexo y todos sus vértices tienen valencia par.

EI siguiente algoritmo de Fleury permite determinar un circuito de Euler:

1) Verificar que el grafo sea conexo y que todos los vértices tengan valencia par. Si no cumple con estas condiciones entonces el grafo no tiene circuito de Euler y finalizar.

2) Si cumple con la condición anterior, seleccionar un vértice arbitrario para iniciar el recorrido.

3) Escoger una arista a partir del vértice actual. Esa arista seleccionada no debe ser “lado puente”, a menos que no exista otra alternativa.

Lado puente es aquella arista que si se elimina, los grafos pierden la propiedad de ser conexos.

4) Desconectar los vértices que están unidos por la arista seleccionada.

5) Si todos los vértices del grafo ya están desconectados, ya se tiene el circuito de Euler y finalizar. De otra manera continuar con el paso 3.

EJERCICIO:

Solución

1) Se puede observar que, efectivamente, se trata de un grafo conexo y que todos sus vértices tienen valencia par.

2) Considérese que se inicia el recorrido en el vértice a.

3) Hay que escoger una arista a partir del vértice actual, y esa arista seleccionada no debe ser “lado puente" a menos que no exista otra alternativa.

Se puede seleccionar cualquiera de las dos aristas [a, b) o (a, c), ya que ninguna es puente. Supóngase que en este caso se escoge (a, b), indicada con línea punteada.

4) Regístrese como parte del circuito de Euler dicha arista. Circuito de Euler: {a, b).

5) Desconéctense los vértices que están unidos por la arista seleccionada. Después de eliminar la arista se tiene el siguiente grafo

Como en este caso todavía no están desconectados todos los vértices del grafo, se continúa desde el paso 3, obteniéndose las siguientes posiciones:

Como se ve en el siguiente grafo, del vértice actual b se puede seleccionar cualquiera de las aristas (Jb, c), (b, e) o (b, d), ya que ninguna es puente. Supóngase que se escoge (Jb, c) indicada con línea punteada. Circuito de Euler: (a, b, c).

Eliminando la arista seleccionada se obtiene el siguiente grafo:

Del vértice actual c se puede seleccionar cualquiera de las aristas (c, e) o (c, í), ya que ninguna es puente. Supóngase que se escoge (c, e) como se indica. Circuito de Euler: (a, Jb, c, e).

Eliminando la arista seleccionada se obtiene el siguiente grafo:

Del vértice actual e se puede seleccionar cualquiera de las aristas (e, b) o (e, d), pero no (e, í) porque se trata de un lado puente. Supóngase que se escoge (e, d) como se indica en el siguiente grafo. Circuito de Euler: (a, b, c, e, d).

Eliminando la arista seleccionada se obtiene el siguiente grafo:

En el vértice actual d solamente está el lado puente (d, b), pero como ya no existe otra arista se selecciona ésta. Circuito de Euler: (a, b, c, e, d, b)

Eliminado la arista seleccionada se obtiene el siguiente grafo:

Se continúa así hasta que todos los vértices queden desconectados. 

Finalmente se obtiene el circuito de Euler: (a, b, c, e, d, b, e, f, c, a).

Como se mencionó, con el circuito de Euler se puede dar solución al juego de La Firma del diablo al reconstruir el grafo, partiendo del nodo a, como lo muestra la numeración de las aristas: 

Circuito Hamilton

Se trata de un problema similar al del circuito de Euler, con la diferencia je que en lugar de pasar por todos los lados del grafo solamente una vez, en el circuito de Hamilton se pasa por cada vértice solamente una vez.

El problema surgió en el siglo XIX cuando Hamilton inventó un juego en donde estaban colocados nombres de ciudades en las esquinas de un dodecaedro. El juego consiste en iniciar en cualquier ciudad, viajar a lo largo de las aristas y visitar cada una de las ciudades exactamente una vez y regresar al punto de partida.

Respecto de un grafo se sabe que tiene un circuito de Euler si es conexo 7 todos sus vértices tienen valencia par, sin embargo no hay forma de saber con anticipación si un grafo tiene o no un circuito de Hamilton.

  

EJERCICIO:

 Determina si es posible un circuito de Hamilton en el siguiente grafo:

Solución. El circuito de Hamilton es como se indica en el grafo.

El circuito de Hamilton es {a, b, h, g, e, j, i, f, d, c, a}, la línea punteada.

EJERCICIO:

Considérese el siguiente grafo G:

a)¿Tiene un camino de Euler?
No tiene camino de Euler, por que no se puede pasar por todas la aristas ya que se pasaría por un vértice varias veces.

b)¿Tiene un circuito de Euler?
No hay circuito de Euler por que hay que pasar varias veces por un vértice y el circuito de Euler dice que el ciclo debe recorrer todos los vértices pasando por todos los lados solamente una vez. 

c)¿Tiene un circuito de Hamilton?
No tiene circuito de Hamilton por que pasa por un vértice varias veces

d)Obtener:

• Conjunto de vértices (V): V={1,2,3,4,5,6,7,8,9,10}
• Conjunto de aristas (A): A={a,b,c,d,e,f,g,h,i,j,k,l,m,n,ñ,o,p,q}
• Conjunto de lazos (L): L={3,10} ó L={f,p}
• Conjuntos de lados paralelos (P): P={1,3} ó {q,e}

e)Obtener matriz de adyacencia: n x n = 10 x10 =100

Representación de grafos

Representación Gráfica

Existen diferentes formas de representar un grafo (simple), además de la geométrica y muchos métodos para almacenarlos en una computadora. La estructura de datos usada depende de las características del grafo y el algoritmo usado para manipularlo. Entre las estructuras más sencillas y usadas se encuentran las listas y las matrices, aunque frecuentemente se usa una combinación de ambas. Las listas son preferidas en grafos dispersos porque tienen un eficiente uso de la memoria. Por otro lado, las matrices proveen acceso rápido, pero pueden consumir grandes cantidades de memoria.

Matemática.

Hay tres maneras de representar un grafo en un programa: mediante matrices, mediante listas y mediante matrices dispersas.

Representación mediante matrices: 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.

Representación mediante 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.

Mediante 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 dispersas, 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.

Estructura de lista

· Lista de incidencia - Las aristas son representadas con un vector de pares (ordenados, si el grafo es dirigido), donde cada par representa una de las aristas.5

· Lista de adyacencia - Cada vértice tiene una lista de vértices los cuales son adyacentes a él. Esto causa redundancia en un grafo no dirigido (ya que A existe en la lista de adyacencia de B y viceversa), pero las búsquedas son más rápidas, al costo de almacenamiento extra.

· Lista de grados - También llamada secuencia de grados o sucesión gráfica de un grafo no-dirigido es una secuencia de números, que corresponde a los grados de los vértices del grafo.

Estructuras matriciales

· Matriz de adyacencia - El grafo está representado por una matriz cuadrada M de tamaño N^2, donde N es el número de vértices. Si hay una arista entre un vértice x y un vértice y, entonces el elemento MXy es 1, de lo contrario, es 0.

· Matriz de incidencia - El grafo está representado por una matriz de A (aristas) por V (vértices), donde [vértice, arista] contiene la información de la arista (1 - conectado, 0 - no conectado).

Computacional.

Representación mediante matrices: 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.

Arreglos Unidimensionales: El arreglo unidimensional o de una dimensión está formado por un conjunto de elementos del mismo tipo de datos que se almacenan bajo un mismo nombre y se diferencia por la posición que tiene cada uno en el arreglo.

Hay métodos, en los que se puede iniciar un elemento en 1 hasta N, donde N es el número de elementos del arreglo; sin embargo, en lenguajes C, C++, Java y derivados, se inicia en 0, el segundo es 1, tercero 2, y así, hasta llegar al elemento N.

Definición del arreglo unidimensional.

Cuando se va a definir un arreglo, es necesario hacerlo como con una variable, y se hace de la siguiente manera: NombreVariable: Arreglo[Tamaño] TipoDeDato.

Donde: NombreVariable = Es el nombre de identificación de la variable.

Arreglo = Es la palabra reservada que indica que la variabl

e es un arreglo.

Tamaño = Es un numero entero que indica la cantidad de elementos que tendrá el arreglo.

TipoDeDato = Es el tipo de dato que tendrá el conjunto de elementos del arreglo que se está definiendo. Puede ser Real, Entero, Cadena, Char, etc.

Tipos de Grafos

Tipos de Grafos

Grafo Simple

Es aquel que acepta una sola arista uniendo dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos.

Un grafo simple G es una estructura maten ática que consta de un par ordenado de conjuntos (V, E), siendo V 6= ∅. Los elementos de V se llaman vértices y los elementos de E se llaman aristas. Notemos que en un grafo simple, una arista es un par {x, y} no ordenado de vértices diferentes.

Un ejemplo de un grafo G = (V, E) viene dado por los conjuntos

V = {1, 2, 3, 4}

E = {{1, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 4}}

Llamaremos orden al cardinal del conjunto de vértices V y tamaño a cardinal del conjunto de aristas E. Por lo tanto, G es un grafo de orden 4 y tamaño 5. 

Son aquellos grafos que no tienen lazos ni aristas paralelas. (ej-7.1)

Grafo completo

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

El conjunto de los grafos completos es denominado usualmente K, siendo el grafo completo de n vértices.

Un Kn, es decir, grafo completo de n vértices tiene exactamente n(n-1)/2 aristas.

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

Grafo bipartido

Un grafo G es bipartito si puede expresarse como G = {V1 + V2, A} (es decir,la unión de dos grupos de vértices), bajo las siguientes condiciones:

• V1 y V2 son distintos y tienen más de un elemento cada uno.

• Una arista en A une un vértice de V1 con uno de V2.

• No existen aristas uniendo dos elementos de V1; análogamente para V2.

Grafo plano

Un grafo G es plano si admite una representación en el plano de tal forma que las aristas no se cortan, salvo en sus extremos. A dicha representación se le denomina grafo plano. En teoría de grafos, un grafo plano (o planar según referencias) es un grafo que puede ser dibujado en el plano sin que ninguna arista se cruce (una definición más formal puede ser que este grafo pueda ser "incrustado" en un plano).

Grafos Conexos 

 Un grafo es conexo (más formalmente fuertemente conexo) si todos sus vértices están conectados por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b. Es posible determinar si un grafo es fuertemente conexo coleccionando la información de los grados de sus vértices al tiempo que se acumulan las diferentes rutas que salen de un vértice o llegan a él. En términos matemáticos la propiedad de un grafo de ser fuertemente conexo permite establecer en base a él una relación de equivalencia para sus vértices, la cual lleva a una partición de éstos en "componentes fuertemente conexos", es decir, porciones del grafo, que son fuertemente conexas cuando se consideran como grafos aislados. Esta propiedad es importante para muchas demostraciones en teoría de grafos.

En la gráfica de la figura 8.2.1,

es una trayectoria de longitud 4 del vértice 1 al vértice 2.

Una gráfica conexa es una gráfica en la que se puede ir de cualquier vértice a cualquier otro vértice por una trayectoria. A continuación se da la definición formal.

Una gráfica G es conexa si dados cualesquiera dos vértices v y w en G, existe una trayectoria de v a w.

La gráfica G de la figura 8.2.1 es conexa ya que, dados cualesquiera dos vértices v y w en G, existe una trayectoria de v a w.

La gráfica G de la figura 8.2.2 no es conexa ya que, por ejemplo, no hay trayectoria del vértice v2 al vértice v5.

Teoría de Grafos

Teoría de Grafos

La Teoría de Grafos juega un papel importante en la fundamentación matemática de las Ciencias de la Computación. Los grafos constituyen una herramienta básica para modelar fenómenos discretos y son fundamentales para la comprensión de las estructuras de datos y el análisis de algoritmos. En matemáticas y ciencias de la computación, la teoría de grafos estudia las propiedades de los grafos, que son colecciones de objetos llamados vértices (o nodos) conectados por líneas llamadas aristas (o arcos) que pueden tener orientación (dirección asignada). Típicamente, un grafo está diseñado por una serie de puntos (los vértices) conectados por líneas (las aristas).

El trabajo de Leonhard Euler, en 1736, sobre el problema de los puentes de Königsberg es considerado como uno de los primeros resultados de la teoría de grafos. También se considera uno de los primeros resultados topológicos en geometría (que no depende de ninguna medida). Este ejemplo ilustra la profunda relación entre la teoría de grafos y la topología. 

Grafo 

Un grafo es una pareja G = (V, A), donde V es un conjunto de puntos, llamados vértices, y A es un conjunto de pares de vértices, llamadas aristas. 

En teoría de grafos, sólo queda lo esencial del dibujo: la forma de las aristas no son relevantes, sólo importa a qué vértices están unidas. La posición de los vértices tampoco importa, y se puede variar para obtener un grafo más claro.

Generalmente, se considera que colocar los vértices en forma de polígono regular da grafos muy legibles. Prácticamente cualquier red puede ser modelada con un grafo: una red de carreteras que conecta ciudades, una red eléctrica o un alcantarillado. 

Aristas dirigidas y no dirigidas 

En algunos casos es necesario asignar un sentido a las aristas, por ejemplo, si se quiere representar la red de las calles de una ciudad con sus inevitables direcciones únicas. El conjunto de aristas será ahora un subconjunto de todos los posibles pares ordenados de vértices, con (a, b) ≠ (b, a). Los grafos que contienen aristas dirigidas se denominan grafos orientados, como el siguiente: Las aristas no orientadas se consideran bidireccionales para efectos prácticos (equivale a decir que existen dos aristas orientadas entre los nodos, cada una en un sentido). 

 Se considera la característica de "grado" (positivo o negativo) de un vértice, como la cantidad de aristas que llegan o salen de él; para el caso de grafos no orientados, el grado de un vértice es simplemente la cantidad de aristas que tocan este vértice. Por ejemplo, el grado positivo (salidas) de d es 3, mientras que el grado negativo (llegadas) de b es 1. 

La figura 8.1.4 muestra una gráfica dirigida. Las aristas dirigidas se indican por flechas. La arista e1 se asocia con el par ordenado de vértices (v2, v1) y la arista e7 se asocia con el par ordenado de vértices (v6, v6). La arista e1 se denota (v2, v1), y la arista e7 se denota (v6, v6).

La definición 8.1.1 permite que diferentes aristas se asocien con el mismo par de vértices. Por ejemplo, en la figura 8.1.5, las aristas e1 y e2 se asocian ambas con el par de vértices {v1, v2}. Estas aristas se llaman aristas paralelas. Una arista incidente en un mismo vértice se llama lazo. Por ejemplo, en la figura 8.1.5, la arista e3 =(v2, v2) es un lazo. Un vértice como v4 en la figura 8.1.5, que no incide en ninguna arista, se llama vértice aislado. Una gráfica sin lazos ni aristas paralelas se llama gráfica simple.

Se dará un ejemplo que muestra cómo se utiliza un modelo de gráficas para analizar un problema de manufactura.

Con frecuencia en la manufactura, es necesario hacer agujeros en hojas de metal (vea la figura 8.1.6). Luego se atornillan las componentes a estas hojas de metal. Los agujeros se perforan usando un taladro controlado por computadora. Para ahorrar tiempo y dinero, el taladro debe moverse tan rápido como sea posible. Se modelará la situación como una gráfica. Los vértices de la gráfica corresponden a los agujeros (figura 8.1.7). Cada par de vértices se conecta por una arista. En cada arista se escribe el tiempo para mover el taladro entre los hoyos correspondientes. Una gráfica con números en las aristas (como en la figura 8.1.7) se llama gráfica ponderada. 

Suponga que en este problema se requiere que la trayectoria comience en el vértice a y termine en el vértice e. Se puede encontrar la ruta de longitud mínima numerando todas las rutas posibles de a a e que pasan por todos los vértices justo una vez y eligiendo la menor (vea la tabla 8.1.1). Se ve que la ruta que visita los vértices a, b, c, d, e, en ese orden, tiene longitud mínima. Por supuesto, un par diferente de vértices de inicio y terminación produciría una ruta aún más corta.

EJERCICIO:

En un torneo, el Nieve venció a loa Faisanes  una vez, el Rascacielos venció al Tuna una vez, el Nieve venció al Rascacielos dos veces,  los Faisanes vencieron a el Tuna una vez, y los Faisanes vencieron al Rascacielos una vez,  en los ejercicios del 1 al 4, use una gráfica para modelar el torneo, los equipos son los vértices. Describa el tipo de gráfica usada, (no dirigida, dirigida, simple).

1.Hay una arista entre los equipos , si los equipos jugaron.

2.Hay una arista entre los equipos para cada juego jugado.

3.Hay una arista del equipo t-i al equipo t-j si t-i venció a t-j al menos una vez.

4.Hay una arista del equipo t-i al equipo t-j por cada victoria de t-j sobre t.