UNIDAD 6 TEORIA 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 modelizar fenómenos discretos y son fundamentales para la comprensión de las estructuras de datos y el análisis de algoritmos. 



Un ingeniero de caminos debe revisar todas las rutas que están entre las ciudades mostradas.
Puede entrar al complejo caminero por alguna de las tres ciudades marcadas y salir del mismo por cualquiera de todas las ciudades.
Por razones de economía conviene que pase sólo una vez por cada una de todas las rutas entre las ciudades.
¿Por cuál ciudad deberá entrar para lograrlo?
¿En cuál ciudad terminará su trayecto y saldrá?
¿Por cuáles ciudades fue pasando en este caso?
          Grafos Simples.-
Son en los que hay una arista o lado entre vértices como máximo, y en los que no hay loops o lazos que conectan algùn vértice consigo mismo.
El problema del ingeniero permite ser analizado mediante un grafo simple.
El grado de un nodo de un grafo simple es la cantidad de aristas o lados que concurren a èl.
            
Trayectorias y Circuitos.-


Si en un grafo simple se van recorriendo sucesivamente sus aristas de modo tal que dos sucesivas sean adyacentes, es decir que concurran al mismo vèrtice por el que se pasa de una a la otra, se está recorriendo o determinando una trayectoria o
camino.
Cuando cierta trayectoria comienza y termina en el mismo nodo decimos que es un circuito.
Cuando una trayectoria pasa sólo una vez por todas y cada una de las aristas o lados se dice que la trayectoria es semi- euleriana, y si esta trayectoria fuera un circuito se la denomina circuito euleriano.
En el problema del ingeniero de caminos necesitamos saber si hay trayectorias semi-eulerianas y por qué vértices pueden comenzar y terminar.


                 


No existe un grafo simple con un sólo nodo de grado impar.
Esto refiere entre otros temasa las paridades de los nodos de un grafo simple, es decir cuántos nodos pares e impares tiene.
Dado cierto grafo, al agregarle una arista, a cada nodo de los extremos de esta arista se le suma una unidad a su grado.
Es decir, que si alguno de esos nodos de los extremos tenían grado impar, pasan a tener grado par y viceversa.
Analizando las posibles combinaciones de paridades de estos nodos de los extremos del nuevo vértice:
                                      i) par-par,
                                     ii) par-impar,
                                    iii)impar-impar,
se nota que la cantidad de nodos con grados impares resulta:
i)o aumentada en dos unidades,
ii)o inalterada,
iii)o reducida en dos unidades.
Para mostrar esto se toma un cierto conjunto de puntos del plano sin vértices que los conecten, y se lo considera un grafo sin vértices. Claramente todo nodo en este caso tiene grado cero.

Cualquier grafo simple puede entonces obtenerse partiendo de unir los nodos de un grafo sin vértices, agregando sucesivamente sus aristas, hasta completarlo.
A partir de esto puede afirmarse que todo grafo simple tiene o ningún nodo de grado impar o por lo menos dos nodos de grado impar.
Es decir, no existe un grafo simple con un sólo nodo de grado impar. 
          ---------------------------------------------------------------------- Paridad de nodos y trayectorias semi-eulerianas.-
La teoría de grafos nos garantiza la existencia de una trayectoria semi- euleriana cuando sólo dos nodos tengan grado impar.
Queda claro que si hubiese más nodos impares ya tendrían que ser comienzos o fines y no existen trayectorias que pasen por todas las aristas con varios comienzos y fines.
Notemos que en el problema del ingeniero serán estos nodos impares los de inicio y final de la trayectoria que pasará por todos las aristas.


EJEMPLO



ANÁLISIS DEL PROBLEMA DE CRUCE  
MEDIANTE LA TEORÍA DE GRAFOS

esquemas de estados de viajeros
en ambas orillas

 

 

TIPOS DE GRAFOS

Grafos simples

Un grafo es simple si a lo más existe una 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 que no es simple se denomina multigrafo.

Grafos conexos

Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b.

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

Es posible determinar si un grafo es conexo usando un algoritmo Búsqueda en anchura (BFS) o Búsqueda en profundidad (DFS).

En términos matemáticos la propiedad de un grafo de ser (fuertemente) conexo permite establecer con base en él una relación de equivalencia para sus vértices, la cual lleva a una partición de éstos en "componentes (fuertemente) conexas", 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. 

Grafos completos

Un grafo 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 , siendo  el grafo completo de n vértices.

Un , es decir, grafo completo de n vértices tiene exactamente  aristas.

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

Grafos bipartitos

Un grafo G es bipartito si puede expresarse como  (es decir, sus vértices son la unión de dos grupos de vértices), bajo las siguientes condiciones:

V1 y V2 son disjuntos y no vacíos.

Cada arista de A une un vértice de V1 con uno de V2.

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

Bajo estas condiciones, el grafo se considera bipartito, y puede describirse informalmente como el grafo que une o relaciona dos conjuntos de elementos diferentes, como aquellos resultantes de los ejercicios y puzzles en los que debe unirse un elemento de la columna A con un elemento de la columna B.

ARBOLES

Un grafo que no tiene ciclos y que conecta a todos los puntos, se llama un árbol. En un grafo con n vértices, los árboles tienen exactamente n - 1 aristas, y hay n^n-2 árboles posibles. 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 aplicación de su estudio se encuentra en el Análisis filogenético, el de la filiación de entidades que derivan unas de otras en un proceso evolutivo, que se aplica sobre todo a la averiguación del parentesco entre especies; aunque se ha usado también, por ejemplo, en el estudio del parentesco entre lenguas.

Nomenclatura sobre árboles

 

Mediante un diagrama encolumnado:

a
  b
    d
  c
    e
    f

- Raíz: es aquel elemento que no tiene antecesor; ejemplo: a.
- Rama: arista entre dos nodos.
- Antecesor: un nodo X es es antecesor de un nodo Y si por alguna de las ramas de X se puede llegar a Y.
- Sucesor: un nodo X es sucesor de un nodo Y si por alguna de las ramas de Y se puede llegar a X.
- Grado de un nodo: el número de descendientes directos que tiene. Ejemplo: c tiene grado 2, d tiene grado 0, a tiene grado 2.
- Hoja: nodo que no tiene descendientes: grado 0. Ejemplo: d
- Nodo interno: aquel que tiene al menos un descendiente.
- Nivel: número de ramas que hay que recorrer para llegar de la raíz a un nodo. Ejemplo: el nivel del nodo a es 1 (es un convenio), el nivel del nodo e es 3.
- Altura: el nivel más alto del árbol. En el ejemplo de la figura 1 la altura es 3.
- Anchura: es el mayor valor del número de nodos que hay en un nivel. En la figura, la anchura es 3.

Aclaraciones: se ha denominado a a la raíz, pero se puede observar según la figura que cualquier nodo podría ser considerado raíz, basta con girar el árbol. Podría determinarse por ejemplo que b fuera la raíz, y ay d los sucesores inmediatos de la raíz b. Sin embargo, en las implementaciones sobre un computador que se realizan a continuación es necesaria una jerarquía, es decir, que haya una única raíz.

Declaración de árbol binario

Se definirá el árbol con una clave de tipo entero (puede ser cualquier otra tipo de datos) y dos hijos: izquierdo (izq) y derecho (der). Para representar los enlaces con los hijos se utilizan punteros. El árbol vacío se representará con un puntero nulo.

RECORRIDO DE BÚSQUEDA CAMINO MAS CORTO

En la Teoría de grafos, el problema de los caminos más cortos es el problema que consiste en encontrar un camino entre dos vértices (o nodos) de tal manera que la suma de los pesos de las aristas que lo constituyen es mínima. Un ejemplo es encontrar el camino más rápido para ir de una ciudad a otra en un mapa. En este caso, los vértices representan las ciudades, y las aristas las carreteras que las unen, cuya ponderación viene dada por el tiempo que se emplea en atravesarlas.

 

os algoritmos de los caminos más cortos se aplican para encontrar direcciones de forma automática entre localizaciones físicas, tales como direcciones en mapas callejeros.

Si un algoritmo representa una máquina abstracta no determinista como un grafo, donde los vértices describen estados, y las aristas posibles transiciones, el algoritmo de los caminos más cortos se usa para encontrar una secuencia óptima de opciones para llegar a un cierto estado final o para establecer límites más bajos en el tiempo, necesario para alcanzar un estado dado. Por ejemplo, si los vértices representan los estados de un puzzle como el Cubo de Rubik, cada arista dirigida corresponde a un simple movimiento o giro. El algoritmo de los caminos más cortos se usa para encontrar la solución que utiliza el mínimo número posible de movimientos.

En el argot de las telecomunicaciones, a este algoritmo es también conocido como el problema del mínimo retraso, y con frecuencia se compara con el problema de los caminos más anchos.

Una aplicación más coloquial es la teoría de los "Seis grados de separación", a partir de la cual se intenta encontrar el camino más corto entre dos personas cualesquiera.

Otras aplicaciones incluyen la Investigación de operaciones, instalaciones y facilidad de diseño, robótica, transporte y VLSI de diseño.

Ejemplo

Una persona tiene que desplazarse a diario de un pueblo 1 a otro 7. Está estudiando cual es el trayecto más corto usando un mapa de carreteras. Las carreteras y sus distancias están representadas en la figura siguiente:

Se determinan las variables de decisión, en este caso:

• Xij: acción de desplazarse del pueblo i al j (0 indica que no hay desplazamiento y 1 que sí hay desplazamiento)

Se determinan las restricciones y se expresan como ecuaciones o inecuaciones de las variables de decisión. Dichas restricciones se deducen del balance entre los posibles caminos que parten desde cada pueblo y los que llegan hasta él (obviando los caminos que nos devuelvan al punto de partida y los que provengan del punto de destino):

• Balance de caminos del pueblo 1: X12 + X13 = 1
• Balance de caminos del pueblo 2: X24 + X25 - X12 - X42 - X52 = 0
• Balance de caminos del pueblo 3: X34 + X36 - X13 - X43 - X63 = 0
• Balance de caminos del pueblo 4: X42 + X43 + X45 - X24 - X34 - X54 = 0
• Balance de caminos del pueblo 5: X52 + X54 + X57 - X25 - X45 = 0
• Balance de caminos del pueblo 6: X63 + X67 - X36 = 0
• Balance de caminos del pueblo 7: - X57 - X67 = -1

Se expresan todas las condiciones implícitamente establecidas por la naturaleza de las variables: que no puedan ser negativas, que sean enteras, que solo puedan tomar determinados valores, ... En este caso las restricciones son que las variables deben ser booleanas (0 no se toma el camino, 1 se toma), y por lo tanto no pueden ser negativas:

• Xij ≥ 0
• Xij es booleano

Se determina la función objetivo:

• Minimizar Z = 12·X12 + 4·X13 + 5·X24 + 3·X25 + 2·X34 + 10·X36 + 5·X42 + 2·X43 + 10·X45 + 3·X52 + 10·X54 + 2·X57 + 10·X63 + 4·X67

Una Búsqueda en profundidad (en inglés DFS oDepth First Search) es un algoritmo que permite recorrer todos los nodos de un grafo o árbol (teoría de grafos) de manera ordenada, pero no uniforme. Su funcionamiento consiste en ir expandiendo todos y cada uno de los nodos que va localizando, de forma recurrente, en un camino concreto. Cuando ya no quedan más nodos que visitar en dicho camino, regresa (Backtracking), de modo que repite el mismo proceso con cada uno de los hermanos del nodo ya procesado.

Análogamente existe el algoritmo de búsqueda en anchura (BFS o Breadth First Search).