Matemáticas - Teoría de grafos

En 1964 Jan Černý propuso que dado un AFD (Autómata finito determinista) sincronizable de ${\displaystyle n}$ estados, exite una palabra de sincronización(o palabra de reinicio) de longitud a lo sumo de ${\displaystyle (n-1)^{2}}$.Este problema es uno de los más antiguos y famosos junto con Teorema del coloreo de carreteras en la teoría de Autómatas Finitos.

Por otro lado, se ha visto que una cota superior en la longitud de la palabra de reinicio es de tamaño cúbico en ${\displaystyle n}$, de donde la conjetura establecería que el tamaño de las cotas superiores de la longitud de dicha palabra, sería cuadrático (en ${\displaystyle n}$).

Autómata sincronizado con 4 estados

Introducción

El problema de la sincronización de un AFD arriva naturalmente, pues la sincronización hace que el comportamiento de un autómata sea "resistente" a errores de ingreso de órdenes dado que, después de la detección de un error, una palabra de sincronización puede reiniciar el autómata a su estado original, como si no hubiera ocurrido ningún error.

Un problema con una larga historia es el de la estimación de la longitud mínima de una palabra de sincronización para un AFD completo.Mejor conocido ahora como una conjetura de Černý, este problema fue propuesto independientimente por otros autores también. Jan Černý en 1964 encontró un AFD completo de ${\displaystyle n}$ estados con palabra mínima de sincronización de tamaño ${\displaystyle (n-1)^{2}}$ para un alfabeto de tamaño ${\displaystyle |\Sigma |=2}$. La conjetura de Černý establece que esta es una cota superior para la longitud de una palabra de sincronización de cualquier AFD con ${\displaystyle n}$ estados. Este problema puede ser reducido a autómatas con un grafo asociado fuernemente conexo.¹

La Conjetura²

Sea ${\displaystyle A=(Q,\Sigma )}$ un AFD con conjunto de entradas ${\displaystyle Q}$ sobre el alfabeto ${\displaystyle \Sigma }$. Una palabra ${\displaystyle w\in \Sigma ^{*}}$ es denominada una palabra de reinicio para ${\displaystyle A}$ si esta palabra envía todos los estados de ${\displaystyle A}$ a un único estado, esto es ${\displaystyle |Qw|=1}$. Un autómata que admite una palabra de reinicio se dice sincronizable.

Conjetura

Un autómata sincronizable de ${\displaystyle n}$ estados admite una palabra de reinicio de longitud a lo sumo de ${\displaystyle (n-1)^{2}}$.

Autómatas Sincronizables y la Conjetura de Černý.

Cotas Superiores de la Longitud de la Palabra de Sincronización

Inicialmente las cotas superiores encontradas para la longitud de las palabras de sincronización no alcanzaban a ser polinomiales; la más conocida de las cotas superiores ahora es ${\displaystyle {\dfrac {n^{3}-n}{6}}}$.

No hay ejemplos de autómatas tales que la longitud de la menor palabra de sincronización sea mayor que ${\displaystyle (n-1)^{2}}$ más aún, los ejemplos de autómatas con palabra de sincronización cuya longitud sea ${\displaystyle (n-1)^{2}}$ son poco frecuentes.³

Conjetura de Černý probabilística

Generalidades

Una manera natural de ver la conjetura de Černý desde un punto de vista probabilístico lleva a una forma de proponer la conjetura de Černý desde las siguientes preguntas:

Pregunta 1: ¿Un AFD es sincronizable con alta probabilidad?

Pregunta 2: ¿un AFD sincronizable de n estados admite una palabra de reinicio de longitud a lo sumo ${\displaystyle (n-1)^{2}}$ con alta probabilidad?

Entendiéndose en estas preguntas que al referisse a alta probabilidad significa"con probabilidad que tiende a ${\displaystyle 1}$ tanto como ${\displaystyle n}$ va al infinito"⁴

Resultados

AFD Sincronizables

Dado ${\displaystyle A}$, AFD aleatorio de ${\displaystyle n}$ estados y ${\displaystyle |\Sigma |=c}$ , hay una probabilidad de ${\displaystyle 1-O({\dfrac {1}{n^{0.5c}}})}$ de que sea sincronizable, para ${\displaystyle |\Sigma |=2}$ el rango de convergencia es bastante estrecho. Por otro lado si ${\displaystyle |\Sigma |=4}$, ${\displaystyle A}$ es sincronizable con una probabilidad ${\displaystyle p}$ para una constante específica ${\displaystyle p>0}$. Si además ${\displaystyle |\Sigma |\geq 72ln(n)}$ entonces, es casi seguro que ${\displaystyle A}$ sea sincronizable.⁵

Dándose así una respuesta afirmativa a la primera pregunta.

Probabilidad del tamaño de una palabra de reinicio en un AFD escogido aleatoriamente de manera uniforme

Al escoger un autómata de manera uniforme sobre el conjunto de AFD sincronizables de ${\displaystyle n}$ estados en un alfabeto de al menos dos letras ${\displaystyle (|\Sigma |\geq 2)}$ se tiene que, para cualquier ${\displaystyle \epsilon >0}$, la probabilidad de que un autómata aleatorio de ${\displaystyle n}$ estados, tenga una palabra de sincronización de tamaño menor que ${\displaystyle n^{1+\epsilon }}$ tiende a ${\displaystyle 1}$ cuando ${\displaystyle n}$ tiende a infinito.⁶

Dándose así respuesta afirmativa a la segunda pregunta.

 conjunto independiente o estable es un conjunto de vérticesen un grafo tal que ninguno de sus vértices es adyacente a otro. Es decir, es un conjunto V de vértices tal que para ningún par de ellos existe alguna arista que los conecten. En otras palabras, cada arista en el grafo contiene a lo más un vértice en V. El tamaño de un conjunto independiente es el número de vértices que contiene.

Un conjunto independiente maximal^{nota 1} es un conjunto independiente tal que añadiendo cualquier otro vértice al conjunto, éste deja de ser independiente.

El (inesperadamente asimétrico) conjunto de 9 vértices azules es un conjunto independiente maximal para este grafo de 24 vértices.

Dado un grafo G, un subconjunto de vértices H ⊂ V(G) se llama conjunto independiente si no hay dos vértices en S que sean adyacentes.

El número de independencia de G es el tamaño de un conjunto independiente más grande, y se denota por α(G).

El conjunto independiente máximo corresponde al mayor conjunto independiente definible sobre un grafo dado. El problema de encontrar un conjunto con estas características se llama problema del máximo conjunto independiente y es NP-completo, por lo cual es poco probable que exista un algoritmo que lo resuelva eficientemente.

El problema de decidir si un grafo dado tiene un conjunto independiente de un tamaño particular es el Problema del conjunto independiente, el cual es computacionalmente equivalente a decidir si un grafo tiene un clique de un tamaño particular. Esto porque, si un grafo tiene un conjunto independiente de tamaño k, luego su grafo complemento tendrá un clique de tamaño k. El problema de decisión del conjunto independiente (al igual que el problema del clique) también es NP-completo.

El corte de grafos es un método de segmentación de imágenes basado en regiones que puede ser utilizado para resolver de manera eficiente una amplia variedad de problemas de bajo nivel en la visión por computadora (visión artificial) como suavizar imágenes, el problema de correspondencia estereoscópica, y muchos otros que pueden ser formulados en términos de minimización de la energía.

Se basa en la teoría de grafos donde el problema de minimización de energía se puede reducir en términos del problema de flujo máximo de un grafo y, por consiguiente, gracias al teorema de flujo máximo corte mínimo se define un corte mínimo del grafo de forma que el tamaño del corte no es más grande en ningún otro corte. En la mayoría de las formulaciones de este tipo de problemas en la visión por computador, la solución de mínima energía corresponde a la estimación del máximo a posteriori de una solución.

Aunque muchos algoritmos de visión por computador impliquen cortar un grafo (por ejemplo, cortes normalizados), el término “cortes de grafos” se aplica específicamente a los modelos que utilizan optimización máximo flujo/ corte mínimo (otros algoritmos de corte de grafos pueden ser considerados como algoritmos departición gráfica).

Historia

La teoría de los cortes de grafos se aplicó por primera vez en la visión por computador en el trabajo de Greig, Porteus i Seheult de la Universidad de Durham. En el contexto de la estadística bayesiana de suavizar imágenes ruidosas (o dañadas), ellos mostraron como la estimación del máximo a posteriori de una imagen binaria se puede obtener exactamente al maximizar el flujo a través de una red de imágenes asociadas, que suponen la incorporación de una fuente y un pozo. El problema se muestra por lo tanto, por ser una solución eficaz.

Antes de estos resultados, técnicas aproximadas, como el algoritmo del recozido simulado (propuesto por los hermanos German), o los modelos de reiteración condicional (como el que sugiere Julian Besag) fueron utilizados para resolver problemas de suavizar imágenes. Aunque el problema general con k colores siga sin resolver-se para k>2, la aproximación de Greig, Porteous i Seheult se ha presentado por tener una amplia aplicación en los problemas generales de visión por computador. Las aproximaciones de Greig, Porteus i Seheult acostumbran a aplicarse de forma iterativa para una secuencia de problemas binarios, en general dando soluciones prácticamente óptimas.

Conceptos

• Segmentación de imágenes: División de una imagen en regiones conexas y disjuntas relacionadas con los objetos de la escena y que cumplen un cierto criterio de homogeneidad.

• Clasificación de regiones: Identificar cada una de las regiones de una partición como parte de una clase o categoría (segmentación con regiones no necesariamente conexas).

• Etiquetado de regiones: Asignar una etiqueta (un color) diferente a cada componente conexa

• Conectividad entre píxeles: Dos píxeles de un conjunto están conectados si existe un camino que une los dos píxeles, de tal forma que todos los píxeles del camino estén en el mismo conjunto.
  • Conectividad 4 (la utilizada en segmentación): Cada píxel tiene 4 vecinos, en vertical y horizontal
  • Conectividad 8: Cada píxel tiene 8 vecinos, en vertical, horizontal y diagonal

Procedimiento

Ejemplos de cortes en una red de flujo

La imagen se modela como una red de flujo donde un píxel o un grupo de píxeles se asocian con los nodos y los pesos de los arcos definen la similitud entre los píxeles vecinos. Esta red de flujo tiene dos vértices diferenciados S (Fuente) y T (Pozo), que se corresponden con las dos semillas de la inicialización, y las capacidades de cada arco.

Un flujo es una función que a cada arco le asigna un valor entre 0 y su capacidad, representando la ley de conservación (para cada vórtice, excepto la Fuente y el Pozo, el flujo que entra es igual al que sale). El valor de un flujo es el que entra en el Pozo y se busca un flujo de valor máximo.

• Un corte en la red es una partición de los vértices en dos subconjuntos disyuntos, C_1 y C_2 de tal manera que S ∈ C_1 y T ∈ C_2
• Los arcos del corte son los que van de C_1 a C_2
• El valor del corte es la suma de las capacidades de sus arcos. Buscamos un corte de valor mínimo
  • El flujo de la red a través del corte es la suma de todas las capacidades alrededor des de S a T menos la suma de todas las capacidades alrededor des de T a S
  • La capacidad del corte es la suma de todas la capacidades alrededor des de S a T
  • Un corte mínimo es un corte donde su capacidad es la mínima de todos los cortes del grafo

Los problemas binarios (como la eliminación de ruido de una imagen binaria) se pueden resolver exactamente con este enfoque, los problemas en que los píxeles se pueden etiquetar con más de dos etiquetas diferentes (por ejemplo, la correspondencia estereoscópica o la eliminación de ruido de una imagen en niveles de gris) no se pueden resolver con exactitud, pero las soluciones producidas son, en general, cerca del óptimo global.

Algoritmos para resolver el problema del flujo máximo

• Algoritmo Ford-Fulkerson: Propone buscar caminos en los que se pueda aumentar el flujo, hasta que se llegue al flujo máximo.
• Algoritmo Edmonds-Karp: Idéntico al de Ford-Fulkerson a excepción de que definimos el orden de búsqueda para encontrar los caminos no saturados.. El camino encontrado tiene que ser el más corto entre los que aún tienen capacidad disponible.
• Algoritmo Push-Relabel: Se ajusta la altura de los nodos para que el flujo pase a través de la red como el agua a través de un paisaje. El flujo a través de la red no es necesariamente un flujo legal a través de la ejecución del algoritmo

Métodos existentes

• Cortes de grafos estándares: optimizan la función de energía sobre la segmentación
• Cortes de grafos repetitivos:

1. Primero se optimizan los parámetros de color utilizando K-means

2. Después se aplica el algoritmo habitual de cortes de grafos

Estos dos pasos se repiten de forma recursiva hasta la convergencia

• Cortes de grafos dinámicos: Permiten volver a ejecutar el algoritmo mucho más rápido después de modificar el problema (por ejemplo, después de que nuevas semillas se hayan incluido por el usuario).

Crítica

Los métodos de cortes de grafos se han convertido en una alternativa popular a las aproximaciones de nivel basadas en conjuntos para optimizar la localización de un contorno. Aun así, las aproximaciones con cortes de grafos han estado criticadas por diversas cuestiones:

• Artefactos de conversión al sistema métrico: Cuando una imagen está representad por una red de conectividad 4, los métodos de cortes de grafos pueden exhibir artefactos no deseados en forma de block. Diversos métodos han estado propuestos para abordar esta cuestión, como el uso de valores adicionales o por la formulación del problema de flujo máximo en un espacio continuo
• Disminución del corte: Des de que los cortes de grafos encuentran un corte mínimo, el algoritmo puede tender a producir un contorno fino. Por ejemplo, el algoritmo no es muy adecuado para la segmentación de objetos delgados como los vasos sanguíneos.
• Diversas etiquetas: Los cortes de grafos solo son capaces de encontrar un óptimo global para los problemas de etiquetaje binario (es decir, dos etiquetas), como la segmentación de imágenes primer plano/fondo. Se han propuesto ampliaciones que pueden encontrar soluciones aproximadas para los problemas de cortes de grafos de multietiquetaje.
• Memoria: La utilización de memoria de los cortes de grafos aumenta rápidamente con el aumento del tamaño de la imagen.