APLICACIONES DE GRAFOS

Objetivo:

Mostrar la aplicación de la teoría de grafos dentro de los márgenes de diseño en la vida real y los diferentes programas utilizados, ya sea en estructuras de comunicación, y dirigidos a la ejecución de programas.

1. Generalidades

Gracias a la teoría de grafos se pueden resolver diversos problemas como por ejemplo la síntesis de circuitos secuenciales, contadores o sistemas de apertura. Se utiliza para diferentes áreas por ejemplo, Dibujo computacional, en todas las áreas de Ingeniería. Los grafos se utilizan también para modelar trayectos como el de una línea de autobús a través de las calles de una ciudad, en el que podemos obtener caminos óptimos para el trayecto aplicando diversos algoritmos como puede ser el algoritmo de Floyd. Para la administración de proyectos, utilizamos técnicas como PERT en las que se modelan los mismos utilizando grafos y optimizando los tiempos para concretar los mismos. La teoría de grafos también ha servido de inspiración para las ciencias sociales, en especial para desarrollar un concepto no metafórico de red social que sustituye los nodos por los actores sociales y verifica la posición, centralidad e importancia de cada actor dentro de la red.

LISTAS Y MATRICES

Lista de adyacencia

En esta estructura de datos la idea es asociar a cada vertice i del grafo una lista que contenga todos aquellos vértices j que sean adyacentes a él. De esta forma sóllo reservará memoria para los arcos adyacentes a i y no para todos los posibles arcos que pudieran tener como origen i. El grafo, por tanto, se representa por medio de un vector de n componentes (si |V|=n) donde cada componente va a ser una lista de adyacencia correspondiente a cada uno de los vertices del grafo. Cada elemento de la lista consta de un campo indicando el vértice adyacente. En caso de que el grafo sea etiquetado, habrá que añadir un segundo campo para mostrar el valor de la etiqueta. 

Matriz de adyacencia

Se trata de una matriz cuadrada de n filas *n columnas (siendo n el número de vértices del grafo).

Para construir la matriz de adyacencia, cada elemento a ij vale {{1}} cuando haya una arista que una los vértices i y j En caso contrario el elemento a ij vale 0.

La matriz de adyacencia, por tanto, estará formada por ceros y unos.

Una lista de adyacencia invertida almacena para cada vértice la lista de adjuntos
desde otros vértices.

Con la estructura de puede calcular el grado de entrada de cualquier vértice
solamente contando el numero de nodos de la lista del vértice requerido.

CARACTERIZACIÓN DE GRAFOS

Grafos Simples Un grafo es simple si a lo más sólo 1 arista une dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es el único que une dos vértices específicos. Un grafo que no es simple se denomina complejo. 

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. 

Grafos Completos 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.

Grafos Bipartitos 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.

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. 

Cibergrafia :

http://campus.cva.itesm.mx/nazira/Tc1003/PDF/TODO/0701_Tc1003_TODO_Grafos.pdf

GRAFOS ISOMORFOS

Se dirá que dos grafos G y G' son isomorfos entre sí, si: 

1. Existe una función biyectiva .
2. Si dos vértices vi, vj son adyacentes en V(G), es decir, viRvj, entonces las correspondientes imágenes de dichos vértices también son adyacentes pero en V(G'), dicho de otra forma,; y viceversa.

Ejemplo: En la siguiente figura, tenemos que G es isomorfo a G'.

Donde V(G) = {1,2,3,4} y V(G') = {A,B,C,D} y como debe cumplirse quef:V(G)  V(G') es una biyección, entonces f(1) = D, f(2) = B, f(3) = C, f(4) = A. Observar que 1R4 en G, entonces, D R A en G'.

Tenemos otra función que también define un isomorfismo entre G y G'.

f(1) = B, f(2) = D, f(3) = C y f(4) = A.

Observar, igualmente, que para este caso 1 R 4 en G, entonces, B R A en G'.

La relación de isomorfismo preserva las vecindades de cada vértice.

La relación de isomorfismo de dos grafos G y G' se denota de la siguiente manera, 

Corolario: Si , entonces:

/V(G) /= /V(G')/

/E(G) /= /E(G') /

Si tiene vi tiene "k" vértices vecinos vi1, vi2, vi3, ... , vik, entonces, f(vi) tiene los siguientes "k" vértices vecinos f(vi1), f(vi2), f(vi3), ... , f(vik).

vi y f(vi) tienen la misma valencia.

Cibergrafía:

http://teoriadegrafos.blogspot.com.co/2007/03/isomorfismo-de-grafos.html

GRAFOS EULERIANOS Y HAMILTONIANOS

Existen todavía algunas familias de grafos que se derivan del concepto de grafos conexos. Este es el caso de los grafos eulerianos y los grafos hamiltonianos. Estas familias de grafos nos permiten resolver el famoso problema de los puentes de Königsberg:

¿cuándo es posible hacer un recorrido de una figura (en este caso de un grafo múltiple) sin pasar dos veces por la misma línea o por el mismo vértice?

Tenemos dos grafos G1 y G2; es posible recorrer uno de ellos sin repetir ninguna línea, pero el otro no. ¿Cuál es cuál? Es evidente que el grafo G1 no puede ser recorrido sin repetir alguna de sus líneas, mientras que el grafo G2 sí.       

                           

Grafos Eulerianos

Recorrido cerrado

Cubre todas las líneas de un grafo, comenzando y terminando en un mismo vértice, recorriendo sin repetición y en forma continua todas las líneas de un grafo G cualquiera. Cuando tal recorrido existe, se denomina eulerianoy un grafo que se puede trazar mediante un recorrido euleriano se llamagrafo euleriano. En la fig. 3.11, G1 es obviamente un grafo euleriano; G2 no lo es, a pesar de que se puede trazar continuamente, ya que el recorrido comienza y termina en vértices distintos; finalmente, G3 no es un grafo euleriano, porque no se puede trazar continuamente.

                                

Diremos que un grafo G es la unión disjunta de ciclos, si podemos descomponer a G como la unión de ciclos que no tienen líneas en común, aunque se permite que tengan, al menos, un vértice en común.

En la figura el grafo se puede descomponer como la unión disjunta de los ciclos C = v1v2v3v4v5v6v1; C' = v1v7v5v1; C'' = v2v7v4v2; C''' = v3v8v9v3 y el recorrido euleriano para el grafo G viene dado por la secuencia de sus líneas 1, 2,..., 15.

OBSERVACION : Esta descomposición por lo general no es única. El grafo de la fig. 3.11 admite otra descomposición como unión disjunta de ciclos, por ejemplo, C = v1v2v7v1; C' = v3v4v2v3; C'' = v3v8v9v3; C''' = v7v4v5v7; C'''' = v5v1v6v5 .

Recíprocamente, supongamos que G es una unión disjunta de ciclos. Sea C un ciclo cualquiera en G. Si entonces G es un ciclo y por lo tanto euleriano. Si existe un ciclo C' en G que tiene un vértice v en común con C (por hipótesis). Si G es la unión de C y C', entonces, comenzando en v trazamos C y luego C', obteniendo así un recorrido euleriano de G. Si la unión de C y C' no es todo G, existe un ciclo C'' que tiene algún vértice v' en común con C o con C', digamos por ejemplo con C'. Si G es la unión de C, C' y C'', entonces comenzando en v trazamos C, luego trazamos C' hasta llegar a v' y luego trazamos C'' hasta completar C', luego regresamos a v como ilustra el diagrama de la fig. 3.13.

Así, obtenemos un recorrido euleriano de G. Si la unión de C, C' y C'' no es todo G, continuamos con este procedimiento hasta obtener un recorrido euleriano de G.

COROLARIO 2: Un grafo conexo es euleriano si y sólo si todos sus vértices tienen valencia par. (Este teorema rige también para multigrafos).

Demostración:

En un recorrido euleriano, cuando visitamos un vértice, necesitamos al menos dos líneas distintas adyacentes al vértice (una para llegar al vértice y otra para salir de él), incluyendo al vértice inicial, porque tenemos que regresar a él para concluir el recorrido. Esto significa, que cada vértice contribuye con un número par de líneas y, por lo tanto, su valencia es par.

Grafos Hamiltonianos

Definición: Un circuito o ciclo hamiltoniano es un ciclo simple que contiene todos los vértices de G. Un circuito hamiltoniano es una trayectoria que empieza y termina en el mismo vértice y pasa por cada vértice una sola vez. 

Ejemplos: ¿Cuál de los grafos siguientes admite un circuito hamiltoniano? 

Solución 

(a) No admite circuitos hamiltonianos. El razonamiento es el siguiente: Si se empieza en v1, v2, v3, v4 y si se está en los demás vértices, en el v5 se estará dos veces. Si se empieza en v5, para luego ir a los vértices v1 o v4 ó a v3 o v2 respectivamente, se tendrá que pasar de nuevo por v5 (puesto que se empezará en v5). Para completar el circuito, se debe regresar a v5, por lo que se pasa tres veces por él.

(b) Un ciclo hamiltoniano es: v1 e1 v2 e2 v3 e3 v4 e4 v1 Teorema. Sea G un grafo conexo con n vértices, donde n≥3. 

Si la suma de los grados de cada par de vértices no adyacentes es mayor o igual a n, entonces G tiene un circuito hamiltoniano. 

Cibergrafia:

http://campus.cva.itesm.mx/nazira/Tc1003/PDF/TODO/0702_Tc1003_TODO_Euler_Hamilton.pdf

http://teoriadegrafos.blogspot.com.co/2007/03/grafos-eulerianos-y-hamiltonianos.html

CICLOS Y CIRCUITOS DE GRAFOS

Ciclo, es una cadena simple, cuyos dos vértices extremos, inicial y terminal, coinciden (no tiene en cuenta la orientación). Si queremos describir la orientación en un ciclo designamos como: u+ = {ui : ui orientada en el sentido del ciclo} u- = {ui : ui orientada en el sentido contrario al ciclo} 

Ciclo elemental, es un ciclo donde no se repite ningún vértice (salvo el primero que coincide con el último). Lo notamos uE = (u1,...,un). 

Propiedad 1: Todo ciclo uC es una suma de ciclos elementales sin aristas comunes. 

Propiedad 2: Un ciclo es elemental si y solo si es un ciclo minimal (es decir que no se pueden deducir otros ciclos por supresión de aristas).

Seudociclo, es una cadena donde los extremos coinciden pero que una misma arista puede figurar más de una vez (también consecutivamente). 

Cociclo del conjunto de vértices A, es el conjunto de aristas incidentes a A, del tipo I(A) no vacío y particionado en dos clases I+(A) y I-(A). 

Ciclo Euleriano es aquel que incluye todas las aristas del grafo una sola vez, conteniendo cada vértice por lo menos una vez. 

Cadena Euleriana, es aquella que recorre todas las aristas una sola vez ( = simple) tocando todos los vértices del grafo. 

Todo multigrafo que posee un ciclo Euleriano es conexo y todos sus vértices tienen grado par . 

A partir del siguiente ejemplo daremos una idea del mecanismo utilizado por Euler para demostrar que la conexidad y el grado par de todos los vértices de un multigrafo, son condiciones necesarias y suficientes para garantizar la existencia de un ciclo Euleriano. Tenemos este grafo que es conexo y sus vértices tienen grado par.

1) Primero se comienza por trazar un camino simple desde un vértice, p. ej a. Supongamos que recorremos a-d-j-n-o-k-l-h-f-e-b-a. Volvimos a a.

La propiedad del grado par, significa que siempre podemos abandonar cada vértice al que entramos, exepto a. Es decir que cualquier cadena que trazemos desde a debe volver a a, formando un ciclo.

2) Las restantes aristas del grafo inicial , conforman un grafo no conexo, pero todos sus vértices mantienen el grado par, ya que al retirar el ciclo encontrado, se redujo cada grado en una cantidad par . Cada subgrafo conexo posee un ciclo Euleriano: d-c-i-j-k-e-d y h-g-m-h

. 3) Estos dos ciclos pueden ser insertados en el ciclo encontrado en 2) en los vértices comunes d y h respectivamente, originando un ciclo Euleriano a-d-c-i-j-k-e-d-j-n-o-kl-h-g-m-h-f-e-b-a, en el grafo original.

Cibegrafía:

https://www.fing.edu.uy/inco/grupos/bioinf/bioinfo1/teorico/grafos.pdf

CLASIFICACIÓN DE LOS GRAFOS

Multigrafo: Es un grafo no orientado con múltiples aristas entre pares de nodos.

Grafo simple: Es un grafo sin bucles, sin múltiples aristas entre pares de vértices.

Grafo completo Para todo par de vértices de G, existe por lo menos una arista que los une. Por lo tanto, un grafo completo de n vértices es aquel que tiene sus n vértices mutuamente adyacentes. n-clique, es un grafo completo simple de n vértices. Se nota Kn.

Subgrafo de G = (X,U) engendrado por el conjunto A ⊂ X, es un grafo cuyos vértices pertenecen al conjunto A y cuyas aristas son aquellas de G que tienen las dos extremidades en A. 

Grafo parcial de G = (X,U) engendrado por V ⊂ U, es el grafo G' = (X,V) cuyos vértices son los mismos de G y cuyas aristas son las que conforman el conjunto V ⊂ U. 

Subgrafo parcial de G, es un subgrafo de un grafo parcial de G

Grafo bipartito: Es un grafo cuyo conjunto de vértices puede ser particionado en dos clases X1 y X2 de tal forma que dos vértices de la misma clase no sean jamás adyacentes. Se nota G = (X1,X2,U)

Grafo bipartito completo, es aquel en el que para todo elemento de X1 y todo elemento de X2 existe por lo menos un arco que los liga.

Un grafo simple bipartito completo con p elementos en X1 y q elementos en X2 se nota Kp,q.

Grafo Regular: es aquel en el que todos sus vértices tienen el mismo grado.

Grafo Ponderado G = (X, U, W) donde (X, U,) es un grafo y W es una función W: U → Z+ (Z+: enteros positivos) . Si u ∈ U, w(u) es llamado el peso de la arista u. Estos pesos corresponden, según la aplicación, a costos, capacidades u otras propiedades de las aristas o arcos. Cuando se desea asignar valores negativos o reales a los pesos de las aristas, se debe tener especial cuidado en la elección de los algoritmos ya que la correctitud de los mismos puede depender de la restricción a Z+.

Grafo Conexo: es aquel en el que para cada par de vértices de G, existe una cadena que los une. En grafos orientados se definen 2 conceptos:

1.  Débilmente conexo: si existe una cadena (sin tener en cuenta la orientación) que une cada par de nodos distintos. 
2.  Fuertemente conexo: si para cada par ordenado de nodos x e y, existe un camino que va de x a y. 

Una componente conexa de un grafo G, es un subgrafo de G engendrado por los vértices que pueden unirse a un vértice xi dado, mediante una cadena (puede ser todo el grafo G).

Cibergrafía:

https://www.fing.edu.uy/inco/grupos/bioinf/bioinfo1/teorico/grafos.pdf