Isomorfia

Un isomorfismo entre dos grafos R y S es una biyección f entre los conjuntos de sus vértices F :  V(R) --> V(S) que conserva la relación de adyacencia. Quiere decir que cualquier par de vértices u y v de R son adyacentes si y solo si lo son sus imágenes, f(u) y f(v), en S. 


Esto quiere decir que dando le nombres iguales a los nodos de los dos grafos, tienen que tener la misma cantidad de nodos vecinos y los mismos nodos.

Como se muestra en la imagen, ambos nodos a y A tiene dos vecinos, los cuales son b, e y B, E y viceversa.

A pesar de su distinta apariencia, los dos grafos son isomorfos.

El análisis de si dos grafos con el mismo número de vértices n y aristas m son isomorfos o no, es conocido como el problema del isomorfismo de grafos. El problema acepta un ataque por fuerza bruta que reclama comprobar si las n! biyecciones posibles conservan la adyacencia, aunque no se conoce un algoritmo eficiente.

A continuación les mostrare un ejemplo

Imágenes tomadas de las diapositivas de la dra. Schaeffer, las características principales de estos grafos es que tiene 15 aristas y 10 nodos por igual.

A continuación la demostración isomorfa en el grafo ROJO a VERDE y viceversa.

Grafo ROJO con nombres en sus nodos (A-J).

Grafo VERDE con nombres en sus nodos (A-J).

Podemos ver que los nombres asignados están alineados de manera isomorfa en ambos grafos.

Vecinos de A = B, E, G

Vecinos de B = A, C H

Vecinos de C = B, D, I

Vecinos de D = C, E, J

Vecinos de E = A, D, F

Vecinos de F = E, H, I

Vecinos de G = A, J, I

Vecinos de H = B, F, J

Vecinos de I = C, F, G

Vecinos de J = D, G, H

Ahora la demostración isomorfa en el grafo AZUL a ROJO y viceversa.

Grafo AZUL con nombres en sus nodos (A-J).

Grafo ROJO con nombres en sus nodos (A-J).

Podemos ver que los nombres asignados están alineados de manera isomorfa en ambos grafos.

Vecinos de A = B, C, H

Vecinos de B = A, E, I

Vecinos de C = A, D, G

Vecinos de D = C, E, J

Vecinos de E = B, D, F

Vecinos de F = G, H, E

Vecinos de G = C, F, I

Vecinos de H = A, F, J

Vecinos de I = B, G, J

Vecinos de J = I, H, D

A continuación la demostración isomorfa en el grafo VERDE a AZUL y viceversa.

Grafo VERDE con nombres en sus nodos (A-J).

Grafo AZUL con nombres en sus nodos (A-J).

Podemos ver que los nombres asignados están alineados de manera isomorfa en ambos grafos.

Vecinos de A = B, C, D

Vecinos de B = G, I, A

Vecinos de C = A, J, H

Vecinos de D = A, E, F

Vecinos de E = I, D, H

Vecinos de F = G, D, J

Vecinos de G = B, F, H

Vecinos de H = G, C, E

Vecinos de I = B, E, J

Vecinos de J = I, C, F

Bueno eso seria todo.

Referencias:

Grafos isomorfos
Diapositivas de la dra. Schaeffer

Complejidad computacional

La complejidad computacional es el campo de la teoría de la computación que estudia teóricamente la complejidad inseparable a la resolución de un problema. Los recursos que normalmente se estudian son:

• El tiempo: que por medio de una aproximación al número y patrón de pasos de ejecución de un algoritmo para solucionar algún problema.
• El espacio: que por medio de una aproximación a la cantidad de memoria que utilizamos para solucionar algún problema. 

Podemos estudiar al igual otros parámetros, así como el número de procesadores que necesitamos para solucionar el problema en equivalente. La teoría de la complejidad se distingue de la teoría de la computabilidad en que ésta se necesita de la posibilidad de manifestar problemas como algoritmos más efectivos sin tomar en cuenta los recursos necesarios para esto.

Los problemas que tienen una solución con orden de complejidad lineal son los problemas que se resuelven en un tiempo que se vincula linealmente con su tamaño.

Los problemas de decisión son clasificados en conjuntos de complejidad comparable llamados clases de complejidad.

Clases de complejidad

Una clase de complejidad es un conjunto de problemas de decisión de complejidad relacionada. Es el conjunto de problemas de decisión que se pueden resolver por una máquina turing utilizando O(f(n)) del recurso R, donde el tamaño n es la entrada.

Clase de complejidad P

Cuando el tiempo de ejecución de un algoritmo, es por cual se obtiene una solución al problema, es menor que el cierto valor calculado partiendo del número de variables incluidas, normalmente son variables de entrada, utilizando una fórmula polinómica, se puede decir que el problema lo podemos resolver en un tiempo polinómico.

La clase de complejidad de los problemas de decisión que se pueden resolver en tiempo polinómico al calcular partiendo de la entrada gracias a máquina de Turing determinista es llamada P.

Ejemplo de tiempo polinomial para generar números primos de forma aleatoria.

Algoritmo Obtención de un número primo aleatorio

/*Basado en el postulado de Bertrand*/

Entrada: Un número natural n.

Salida : P (el número primo aleatorio buscado).

1.-  P <--  Función Genera_numero_aleatorio_en_intervalo [n, 2n]

2.-  Mientras P no sea un número primo haga lo siguiente:

   1.-  P <-- P + 1

   2.-  Si (P = 2n) entonces:

      1.-  P <-- n

3.-  Retorne P

Clase de complejidad NP

¿Qué es NP?, NP son las siglas en inglés de nondeterministic polynomial time ("tiempo polinomial no determinista"). Es el conjunto de problemas que se pueden resolver en tiempo polinómico por una máquina de Turing no determinista.

La importancia de esta clase de problemas de decisión es que tiene muchos problemas de búsqueda y de optimización, los cuales se desea saber si existe una especifica solución o si existe una mejor solución que las que ya conocemos.

Por la importancia que tiene, con muchos esfuerzos han tratado de encontrar algoritmos que decidan algún problema de NP en tiempo polinómico. Aunque, parezca que para algunos problemas de NP (los del conjunto NP-completo) no se puede encontrar un algoritmo mejor que solamente realizar una búsqueda profunda.

Ejemplo de NP, el problema del viajante

El problema del viajante es un ejemplo que muestra y analiza la problemática que esta debajo de algunos tipos de problemas matemáticos que antes parecen tener una solución relativamente fácil, y en la práctica presentan un gran problema.

Se conoce la respuesta al problema o bueno, la forma de resolverlo, pero sólo en teoría, en la práctica la solución no se aplica debido al tiempo que computacionalmente se necesita para conseguir su resultado.

El también conocido como problema del viajante de comercio o por sus siglas en inglés TSP: Travelling Salesman Problem, es de los problemas más famosos y tal vez el mejor estudiado en el campo de la optimización combinatoria computacional. A pesar de la aparente sencillez de su planteamiento, es uno de los más complejos de resolver y existen demostraciones que visten la complejidad de su solución a la de otros problemas aparentemente mucho más complejos que han retado a los matemáticos.

Imagen que representa este problema, ¿cual es la ruta más optima que se debe tomar para visitar todas las ciudades?

Ejemplo de recorrido del problema del viajante (vídeo que encontré).

Esquema del problema del viajante para m rutas (m-TSP) que consiste en obtener el recorrido mínimo para ''m'' vehículos que tienen que pasar por n puntos a partir de un punto origen.

NP-Completo

Un NP-completo es el sub-conjunto de los problemas de decisión en NP por esto todo problema en NP se puede transformar en cada uno de los problemas de NP-completo. Podemos decir que los problemas de NP-completo son los problemas con mayor dificultad de NP y es muy probable que no puedan formar parte de la clase de complejidad P.

Un problema de decisión C es NP-completo si se cumple lo siguiente:

• C es un problema NP.
• Todo problema de NP se puede transformar polinómicamente en C.

Podemos demostrar que C es NP comprobando que un aspirante a solución de C puede ser examinado en tiempo polinómico.

Una transformación polinómica de L en C es un algoritmo confirmando que transforma instancias de l ∈ L en instancias de c ∈ C, por esto la respuesta a c es positiva si y sólo si la respuesta a l lo es.
Como resultado de esta descripción, si tenemos un algoritmo en P para C, tendríamos una solución en P para todos los problemas de NP.

Ejemplo de NP-completo, problema de la clique

Una clique en un grafo, un conjunto de vértices dos a dos adyacentes. 

Los vértices 1, 2 y 5 forman una clique porque cada uno tiene un arco que le une a los otros. En cambio, los vértices 2, 3 y 4 no, dado que 2 y 4 no son adyacentes.

El problema de la clique es un problema de optimización para definir cuándo un grafo tiene una clique de por lo menos tamaño k. Cuando tengamos k o más vertices que forman una clique, es trivial verificar que lo son, por esto es un problema NP. El problema que corresponde de optimización, consiste en hallar una clique de tamaño máximo en un grafo. Este problema se puede expresar como un problema de decisión si la pregunta que se hace es saber si existe una clique de tamaño k en el grafo.

Algoritmo para resolver este problema

Algoritmo de fuerza bruta

La búsqueda por fuerza bruta, búsqueda combinatoria, búsqueda exhaustiva o simplemente fuerza bruta, es una técnica trivial de las más usadas, consiste en enumerar ordenadamente todos los posibles aspirantes para la solución de un problema, su fin es el de reconocer si dicho aspirante satisface la solución al mismo.

Un ejemplo de esto, es cuando registramos todos los sub-conjuntos de vértices y comprobamos cada uno si forman una clique. 

Funcionamiento del algoritmo de fuerza bruta, cuando realiza la búsqueda combinatoria. 

Referencias:

Complejidad computacional
Complejidad P
Complejidad NP
NP-completo

Algoritmos de caminos mínimos en grafos

A continuación les mostrare otros dos algoritmos para poder encontrar el camino corto en un grafo.

Una sucesión de aristas adyacentes que empieza en v y termina en w es un camino de v a w.

Mientras G=(V,A) un grafo ponderado, u, v vértices de G. Le encontramos distancia de u a v, d(u,v), a la mínima longitud de los caminos que unen u con v. Cuando no existe camino de u a v se dice que d(u,v)= infinito.

Dado un grafo ponderado y dos vértices s y t queremos encontrar d(s,t) y el camino con dada longitud.

Si el vértice u se encuentra en un camino C de longitud mínima entre los vértices s y z entonces, la parte de C comprendida entre los vértices s y u es un camino de longitud mínima entre s y u. Por lo tanto, el conjunto de caminos mínimos desde s a los restantes vértices del grafo G es un árbol, llamado el árbol de caminos mínimos desde s.

Algoritmo de Dijkstra

La idea principal de este algoritmo consiste en: Si P es un camino de longitud mínima s--z y P contiene al vértice v, entonces la parte s--v de P es también camino de longitud mínima de s a v. Esto indica que si queremos determinar el camino óptimo de s a cada vértice z de G, podremos hacerlo en orden creciente de la distancia d(s,z).

'                                                        Imagen que representa la ejecución del algoritmo de Dijkstra.

Características del algoritmo
Entrada: Un grafo ponderado, un vértice s que pertenece a V. El peso de la arista uv indicada por w(uv), colocando w(uv)= infinito si uv no es arista. (Las aristas no tienen pesos negativos).

Clave: Mantener el conjunto T de vértices para el camino más corto y incrementar T hasta que T=V. Para esto etiquetamos cada vértice z con t(z) que es la longitud del camino más corto ya encontrado. Así mantenemos un conjunto A de vértices que se encuentran en el árbol de búsqueda pero no en el árbol de camino mínimo y que son alcazables desde los vértices de T.

Inicialización: Sea A={s}, T{}, t(s)=d(s,s)=0, t(z)= infinito para z diferente de s.

Iteración: Elegimos el vértice v que pertenece a A con etiqueta mínima. Añadimos v a T. Designamos v como "vértice actual" y eliminarlo de A.

Analizar cada arista vz con z no perteneciente de T y actualizamos la etiqueta de z a min{t(z), t(v)+w(vz)}. Y añadimos z a A.

La iteración continua hasta que T=V(G) o hasta que t(z)= infinito para cada vértice z no perteneciente a T

En cualquier caso la etiqueta de cada vértice z en T será la distancia de s a z. En el segundo caso los vértices que no están en T no son alcanzable desde s.

Análisis asintótico

Complejidad del algoritmo: O(|V|2+|E|) = O(|V|2) sino utilizamos cola de prioridad, O((|E|+|V|) log |V|) cuando utilizamos la cola de prioridad (ejemplo un montículo).

Podemos apreciar la complejidad computacional del algoritmo de Dijkstra en términos de sumas y comparaciones. El algoritmo realiza a lo más n-1 iteraciones, ya que en cada iteración se agrega un vértice al conjunto señalado. Para apreciar el número total de operaciones tenemos que valorar  el número de operaciones llevadas a cabo en cada iteración. Podemos identificar el vértice con la menor etiqueta entre los que no están en Sk realizando n-1 comparaciones o menos. Después hacemos una suma y comparamos para actualizar la etiqueta de cada uno de los vértices que no están en Sk. Por lo tanto, en cada iteración se realizan 2(n-1) operaciones, ya que no puede haber más de n-1 etiquetas faltantes de actualizar en cada iteración. Si no se realizan más de n-1 iteraciones, cada una de las cuales supone a lo más 2(n-1) operaciones, hemos llegado al siguiente teorema. 

Indica que el Algoritmo de Dijkstra realiza O(n2) operaciones (sumas y comparaciones) para poder  determinar la longitud del camino más corto entre dos vértices de un grafo ponderado simple, conexo y no dirigido con n vértices.

Pseudocódigo ejemplo (encontrado).

DIJKSTRA (Grafo G, nodo_fuente s)       

       para u ∈ V[G] hacer

           distancia[u] = INFINITO

           padre[u] = NULL

       distancia[s] = 0

       Encolar (cola, grafo)

       mientras que cola no es vacía hacer

           u = extraer_minimo(cola)

           para v ∈ adyacencia[u] hacer

               si distancia[v] > distancia[u] + peso (u, v) hacer

                   distancia[v] = distancia[u] + peso (u, v)

                   padre[v] = u

                   Actualizar(cola,distancia,v)

Algoritmo de Ford-Fulkerson

Es una variante del algoritmo de Dijkstra que permite asignar pesos negativos en las aristas, aunque no permite la existencia de ciclos de peso negativo en el grafo.

Algoritmo de etiquetado de Ford y Fulkerson sirve para el cálculo del flujo máximo de una red.

Características del algoritmo
Entrada: Un grafo ponderado con pesos que no son negativos en las aristas, un vértice s que pertenece a V. El peso de la arista uv se indica por w(uv), colocando w(uv)= infinito si uv no es arista.

Salida: La distancia desde s a cada vértice del grafo.

Clave: Mejorar en cada paso las etiquetas de los vértices, t(u).

Inicialización: Sea T={s}, t(s)=d(s,s)=0, t(z)= infinito para z diferente de s.

Iteración: Mientras existan aristas e=xz para los que t(z)>t(x) + w(e) actualizaremos la etiqueta de z a min{t(z), t(x)+w(xz)}.

Análisis asintótico

Tenemos que observar que cada arista se puede considerar varias veces. Empezamos ordenando las aristas del grafo D siendo este el orden en que se considerarán las aristas en el algoritmo. Después de la primera pasada se repite el proceso hasta que en una pasada completa no se produzca ningún cambio de etiquetas. Si D no tiene ciclos negativos se puede demostrar que, si el camino mínimo s ---> u contiene k aristas entonces, después de k pasadas alcanzamos la etiqueta definitiva para u. Como k <= n y el nº de aristas es q, resulta que la complejidad del algoritmo de Ford es O(qn). Incluso de puede detectar un ciclo negativo si se produce una mejora en las etiquetas en la pasada número n.

Pseudocódigo ejemplo (encontrado)

Ford-Fulkerson(G,s,t)

 { 

  for (cada arco (u,v) de E) 

  { 

   f[u,v]= 0; 

   f[v,u]= 0; 

  } 

  while (exista un camino p desde s a t en la red residual Gf) 

  { 

    cf(p) = min{cf(u,v): (u,v) está sobre p};

    for (cada arco (u,v) en p) 

    { 

      f[u,v]= f[u,v] + cf(p); 

      f[v,u]= - f[u,v]; 

    }  

  } 

 }

Referencias:

Algoritmo de Dijkstra
Algoritmo de Ford-Fulkerson

Algoritmo de Floyd-Warshall

El algoritmo de Floyd-Warshall, explicado en 1959 por Bernard Roy, es un algoritmo de análisis de grafos para encontrar el camino mínimo en grafos dirigidos ponderados. El algoritmo encuentra el camino entre todos los pares de vértices en una única ejecución.

Trabaja con la matriz D inicializada con las distancias directas entre todo par de nodos. La iteración se realiza sobre nodos intermedios, es decir, para todo elemento de la matriz se prueba si lo mejor para ir de i a j es a través de un nodo intermedio elegido o como estaba antes, y esto lo probamos con todos los nodos de la red. Una vez probados todos los nodos de la red como nodos intermedios, la matriz resultante da la mejor distancia entre todo par de nodos.

Podemos definir caminoMinimo(i,j,k) de forma recursiva:

caminoMinimo(i,j,k) = min(caminoMinimo(i,j,k-1),caminoMinimo(i,k,k-1)+caminoMinimo(k,j,k-1));

caminoMinimo(i,j,0) = pesoArista(i,j);

Esta fórmula nos sirve como base del algoritmo Floyd-Warshall. Su funcion es ejecutar primero caminoMinimo(i,j,1) para todos los pares (i,j), así los usamos para después encontrar caminoMinimo(i,j,2) para todos los pares(i,j). El proceso continúa hasta que k = n, y que encontremos el camino más corto para todos los pares de vértices (i,j) usando algún vértice intermedio.

Pseudocódigo del algoritmo

Bueno aqui les dejo un pseudocódigo que vi en la internet y les quiero compartir.

/* Suponemos que la función pesoArista devuelve el coste del camino que va de i a j

    (infinito si no existe).

    También suponemos que n es el número de vértices y pesoArista(i,i) = 0

 */

 int camino[][];

 /* Una matriz bidimensional. En cada paso del algoritmo, camino[i][j] es el camino mínimo 

    de i hasta j usando valores intermedios de (1..k-1). Cada camino[i][j] es inicializado a 

    pesoArista(i,j)

 */

 procedimiento FloydWarshall ()

    para k: = 0 hasta n − 1

       para todo (i,j) en (0..n − 1)

          camino[i][j] = mín ( camino[i][j], camino[i][k]+camino[k][j]);

También les dejare estos vídeos que encontré donde te explica como encontrar las distancias mediante el algoritmo de Floyd-Warshall.

Esta es la primera parte

Esta es la segunda parte

Espero les sirva de ayuda estos vídeos como tutoriales, bueno esto sería todo.

Referencias:

Algoritmo de Floyd-Warshall

Grafos

Un grafo es una estructura de datos, específicamente es un tipo abstracto de datos (TAD), que consiste en un grupo de nodos a los cuales también le podemos llamar vértices y un grupo de aristas que establecen relaciones entre las vértices. El concepto de grafo TAD tiene su origen directamente del concepto matemático de grafo.

Se define como G = (V, E), siendo los elementos de V los vértices, y los elementos de E las aristas. Un grafo, G, es definido como un par ordenado, G = (V, E), donde V es un conjunto n finito de vértices u, v, w que pertenecen a V y E es un conjunto m de aristas que consta de dos elementos de V.

Representación visual de grafos.

Le llamamos orden del grafo G a su número de vértices, | V |.
El grado de un vértice o nodo V es igual al número de vértices E que encontramos en él.
Un bucle es una arista que conecta un vértice consigo mismo, es decir, una arista donde el nodo inicial y el nodo final coinciden.

El complemento o inverso de un grafo G = (V,E) es un grafo G' =(V,E'), con el mismo conjunto de vértices y tal que dos vértices de G' son adyacentes si solo si no son adyacentes en G. Para conseguir el complemento de un grafo, debemos completar todas las aristas que faltan para hacerlo completo, y quitar todas las aristas del grafo G original. 

Imagen que representa un grafo de Petersen (izquierda) y grafo complemento (derecha).

Tipos de grafos

Un grafo es plano cuando se puede dibujar en dos dimensiones, cuando ninguna arista cruza con otra.

Grafo no dirigido

Un grafo no dirigido o grafo propiamente dicho es un grafo G = (V,E) donde:

es un conjunto de pares no ordenados de elementos de V.

   Un par no ordenado es un conjunto de la forma {a,b}, de manera que {a,b} = {b,a}.

Representación visual de un grafo no dirigido.

Para grafos simples no dirigidos se define la densidad de grafo de la siguiente forma:

D = 2 | E | / | V | ( | V | - 1 )

El número máximo de aristas es ½ |V| |V−1|, de tal manera que la densidad máxima es 1 para un grafo completo y la densidad mínima es de 0.

Grafo dirigido

Un grafo dirigido o digrafo es un grafo G = (V,E) donde:

 es un grupo de pares ordenados de elementos de V.

Dada una arista (a,b), a es su nodo inicial y b su nodo final. Con esto llegamos a que los grafos dirigidos no contienen bucles.

Representación visual de un grafo dirigido.

Pseudografo

Un pseudografo dirigido es un grafo G = (V,E) donde:

es un conjunto de pares ordenados y etiquetados de elementos de V.

Es decir, un pseudografo es un grafo no dirigido que acepta bucles en E.

Representación visual de pseudografo.

Pseudografo dirigido  

Un pseudografo dirigido es un grafo G = (V,E) donde:

 es un conjunto de pares ordenados y etiquetados de elementos de V.

Es decir, un pseudografo dirigido es un grafo dirigido que acepta bucles en E.

Formas de representación

Existen distintas formas de poner en funcionamiento del tipo grafo: con una matriz de adyacencias (forma acotada) y con listas y multilistas de adyacencia (no acotadas).

Matriz de adyacencias: se liga cada fila y cada columna a cada nodo del grafo, siendo los elementos de la matriz la relación entre los mismos, se toma los valores de 1 si existe la arista y 0 en caso contrario.

Representación de una matriz de adyacencias.

Lista de adyacencias: se liga a cada nodo del grafo una lista que tenga todos aquellos nodos que sean adyacentes a él.

Representación de una lista de adyacencias.

Grafo bipartito

Un Grafo bipartito se denomina a un grafo cuyos vértices se pueden separar en dos conjuntos disjuntos V₁ y V₂ y las aristas siempre unen vértices de un conjunto con vértices de otro:

Los dos conjuntos U y V se pueden pensar como un coloreo del grafo teniendo dos colores, si pintamos los vértices en U de azul y los vértices de V con verde obtendremos un grafo de dos colores donde cada arista tiene un vértice azul y el otro verde. Sin embargo, si un gráfico no tiene la propiedad de que se puede colorear con dos colores no es bipartito.

Representación visual de un grafo bipartito.

Algo más

Aquí una imagen que demuestra el agrupamiento espectral.

Referencias:

Grafos
Estructura de grafo
Teoría de grafos