Usuario:David Casas Torres/Taller

Grafos Observables

Ejemplo de grafo observable.

La idea de un grafo observable es un grafo dirigido y coloreado donde un agente se desplaza de vértice en vértice sobre las aristas (respetando la dirección de las aristas) y que solo es capaz de almacenar la secuencia de los colores de las aristas (o los vértices) en orden, pero a pesar de ello, luego de una cantidad T finita de aristas (o vértices) el agente sabe exactamente el vértice en el que está.

Definiciones previas

A continuación se presentaran algunas definiciones técnicas que permitirán dar una definición formal de lo que son los grafos observables y parcialmente observables.
Sea un grafo dirigido con aristas etiquetadas $G(V,E)$, sea $\Sigma$ un conjunto finito, a los elementos de $\Sigma$ les decimos sin distinción letras, etiquetas o colores que tendrán las aristas o los vértices según se especifique.

Llamamos palabra a $w=a_{1},\dots ,a_{n}$ una sucesión finita de letras. Denotamos $\Sigma ^{*}$ el conjunto de todas las palabras que se pueden formar con letras del conjunto $\Sigma$. Decimos que $w_{[i,j]}$ es la sub-palabra $w_{i}\dots w_{j}$ y por último $\left\vert w\right\vert$ es la longitud o número de letras que tiene la palabra $w$.
Un camino $P$ en $G$ es permitido por una palabra $w$ de $\Sigma$ si la arista $e_{i}$ del camino está etiquetada por $w_{i}$.

Ejemplo de grafo coloreado y caminos permitidos por una serie de colores.

En el ejemplo de la derecha si el color rojo se representa por la letra $R$ y el verde por $V$ tenemos que el camino $F-E-C-B$ está permitido por la palabra $RVR$ y que no existe ningún camino permitido por la palabra $RRV$.

Sea $S\subseteq V(G)$ un subconjunto de vértices y $\omega$ una palabra del conjunto $\Sigma$. Definimos $\delta _{\omega }(S)$ como el conjunto de vértices para los cuales existe una camino permitido por $\omega$ desde algún vértice de $S$. En otras palabras es el conjunto de nodos a los que podemos llegar si empezando por uno (nodo) de $S$ seguimos un camino con la palabra $\omega$.

Por lo tanto tendríamos que $\delta _{\omega }(V(G))$ como todos los vértices alcanzables en el grafo permitidos por la palabra $\omega$.

Un vértice de un grafo $G$ es asintóticamente alcanzable si puede ser alcanzado por un camino de longitud arbitraria.

Definición de grafos observables

Un grafo dirigido con aristas etiquetadas $G$, y sus etiquetas en $\Sigma$ es observable si existe un entero $T$ tal que para toda $\omega \in \Sigma ^{*}$, donde $\left\vert \omega \right\vert \geq T$, se tiene que $\left\vert \delta _{\omega }(V(G))\right\vert \leq 1$.

Ejemplo de grafo parcialmente observable.

El grafo se dice parcialmente observable si en las mismas condiciones anteriores existe un $1\leq t\leq T$ tal que $\left\vert \delta _{\omega [1,t]}(V(G))\right\vert \leq 1$.

En otras palabras es observable si para toda palabra suficientemente larga, o recorrido suficientemente largo, podemos determinar con exactitud en que nodo del grafo estará al final de tal recorrido. Y es parcialmente observable si podemos determinar con exactitud uno o más nodos que conforman el camino.

Con las secuencias ARR y RAR sabremos el lugar en dónde el agente se encuentra

Analicemos otro ejemplo (ver imagen ) que nos muestra como de una secuencia de colores podemos saber exactamente el lugar en donde se encuentra el agente. Si nos dan la secuencia $ARR$ entonces no hay otra opción para el agente que estar en $V_{4}$ o igualmente si nos dan $RAR$ el agente no tiene otra opción que estar en $V_{2}$. Por otro lado podemos tener una secuencia de colores emitida por el agente que camina sobre el mismo grafo en dónde no es posible saber el lugar en dónde se encuentra el agente por ejemplo consideremos la secuencia $RRA$ analizando el grafo podremos caer en cuenta que el agente puede estar ubicado en $V_{1}$ pero también en $V_{4}$.

Verificación de Observabilidad

Teorema

Un grafo $G$ de aristas etiquetadas es observable si y solo si:

• No existe una sucesión de caracteres $\omega$ perteneciente a dos ciclos diferentes

• Si no existe un vértice asintóticamente alcanzable del grafo $G$ del cual salgan dos aristas con el mismo carácter.

Demostración

→ Se probará la primera implicación por contradicción. Asumamos que $G$ es un grafo observable, sea $\omega$ una sucesión de caracteres que pertenece a dos ciclos diferentes y sea $v$ un vértice asintóticamente alcanzable del cual salgan dos aristas con el mismo carácter. Existe un entero $T$, tal que es posible encontrar un camino de medida $T-1$ que termina en el vértice $v$.

Ahora bien dado que del grafo $v$ salen dos aristas con el mismo carácter $c$ y se considera que dicho camino pertenece a la sucesión de caracteres $\omega$, entonces se obtiene una secuencia arbitraria de caracteres $\omega c$.

Consideremos el conjunto $\delta _{\omega c}(V(G))$, recordando que del vértice $v$ salen dos aristas con el mismo carácter, se obtiene que $\left\vert \delta _{\omega c}(V(G))\right\vert \leq 2$.
y esto contradice que sea observable.

← Sea el entero $T_{1}$ de tal forma que todo camino de medida mayor que $T_{1}$ tiene el ultimo vértice asintóticamente alcanzable, sea la sucesión de caracteres $\omega$ y considere dos caminos pertenecientes a $\omega$. La intensión es ver que estos caminos se intersectan entre $T_{1}$ y $T_{1}+({\hat {n}})^{2}$ donde ${\hat {n}}$ es el número de vértices asintóticamente alcanzables. Esto sucede pues si se supone lo contrario, es decir que estos dos caminos no se intersectan durante los últimos $({\hat {n}})^{2}$ pasos.

Lo que va a ocurrir es que ambos caminos van a pasar por cada uno de los demás vértices que faltan por alcanzar, hasta que finalmente se van a acabar los vértices y por el principio del palomar van a comenzar a repetir vértices. Sin embargo esto implica que existen dos ciclos con la misma sucesión de caracteres $\omega$ y esto contradice la hipótesis del teorema.

Corolario

En un grafo observable, son suficientes ${\frac {(n(n-1))}{2}}$ observaciones para localizar un agente.

Demostración

Si no fuera así implicaría que existe una sucesión de caracteres de tamaño ${\frac {(n(n-1))}{2}}$ tal que hay dos caminos pertenecientes a esta y que terminan en diferentes vértices.

Es decir hay ${\frac {(n(n-1))}{2}}+1$ pares de vértices en los cuales ambos caminos siguen siendo diferentes y usando el mismo argumento del teorema anterior, por el principio del palomar esto implica que el grafo no es observable. Por lo tanto se debe tener la afirmación anterior.

Diseñar grafos observables es NP-completo

Teorema

Dados $G$ un grafo y $k$ un entero positivo , el problema de hacer un grafo $G^{'}$ de $G$ observable con una coloración por vértices de $K$ Colores es NP-completo.

Ilustración

Tomemos un grafo $G$ y su conjunto de aristas $E$ y su conjunto de vértices $V$ podemos suponer una enumeración de $E$ como $e_{1},...,e_{n}$ y una de $V$ como $v_{1},...,v_{m}$ ahora construiremos un grafo $G^{'}$ con un nuevo conjunto de aristas $E^{'}$ y también de vértices $V^{'}$ de tal forma que $G$ es 3-Coloreable si y solamente si $G^{'}$ es Observable.

La razón por la cual el problema del diseño de grafos observables es un problema NP-completo es porque se reduce el problema principal al problema del 3-coloreo de grafos que ya es NP-completo en un tiempo polinomial. Comencemos por la construcción de $G^{'}$

Paso 1

Primer paso de la construcción

Este paso consiste en que dado un grafo escogemos una coloración por nodos de tal forma que dos nodos conectados con la misma arista de $E$ no tengan la misma coloración. Luego por cada $v_{i}\in E$ consideremos un $v_{i}^{'}\in E^{'}$ y por cada $e_{i}\in E$ consideremos un $v_{e_{i}}^{'}\in V^{'}$, además si $e_{i}=(v_{m},v_{n})\in E$ entonces $(v_{e_{i}}^{'},v_{m}),(v_{e_{i}}^{'},v_{n})\in E^{'}$ y los nuevos vértices los colorearemos todos de uno de los colores. En la figura de la derecha esta representado a mano derecha el grafo $G$ y a la izquierda se ve como se va formando el grafo $G^{'}$ y Coloreamos los nuevos vértices de azul. Notemos que en esta construcción se esta haciendo cuidando que de un vértice no salgan aristas a dos vértices con las mismas coloraciones lo cual llevaría a la posibilidad de que la condición de ser observable no se tenga.

Paso 2

Segundo paso de la contrucción

En este segundo paso lo que haremos es por cada $v_{e_{i}}^{'}$ consideraremos un $v_{e_{i}}^{''}$ en $E^{'}$ estos los colorearemos de un color distinto al color seleccionado para los $v_{e_{i}}^{'}$, además haremos que $(v_{e_{i}}^{''},v_{e_{i}}^{'})$ para todo $0<i<n+1$ y $(v_{e_{j}}^{''},v_{e_{j+1}}^{''})$ para $0<j<m$ estén en $E^{'}$. en la segunda imagen de la derecha está ilustrado este paso y usa como el color para los nuevos vértices el verde.

Paso 3

Tercer paso de la construcción

En este añadimos vértices de una forma tal que nos permita determinar la posición del agente. Para esto por cada uno de los $v_{i}^{'}$ añadimos dos vértices etiquetados con el color distinto al que utilizamos en los pasos anteriores llamemos $R_{1},R_{2}$ a ambos vértices a $E^{'}$ le añadimos las aristas $(v_{i}^{'},R_{1}),(R_{1},R_{2})$ y $(R_{2},v_{e_{1}}^{''})$. Notemos que esta es una manera de identificar de forma certera la posición en donde está ubicado el agente.

Esta construcción nos permite establecer el resultado deseado, en efecto si el grafo $G$ es 3-Coloreable entonces por la construcción anterior cuando el agente reciba una sucesión que termina con $...RRV$ (siguiendo las etiquetas dadas en el ejemplo ilustrativo) el agente sabrá que al recibir la $V$ ha pasado por $v_{e_{1}}^{''}$ luego de esto puede recibir solo azul o verde, en el caso en que salga azul entonces estará en $v_{e_{1}}^{'}$ y si recibe verde sabrá que está dirigiéndose hacia algún $v_{e_{i}}^{'}$, en algún momento se acabará esa secuencia de verdes y vendrá un azul, que dependiendo de la cantidad de verdes anteriores que hayan en la secuencia sabremos cual es, el único problema sería que existiera la posibilidad de que el $v_{e_{i}}^{'}$ estuviera conectado a dos vértices de colores iguales, ya que en ese caso el agente no podría identificar el vértice en el que está, pero por hipótesis el grafo $G$ es 3-coloreable y por al construcción no es posible que se dé ese caso. así que el grafo $G^{'}$ es observable. y el hecho de que $G^{'}$ sea observable obliga a que $G$ sea 3-coloreable por el mismo argumento.

Diseñar grafos parcialmente observables es NP-completo

Teorema

El problema de determinar para un grafo dado $G$ y un entero $k$, si $G$ puede ser parcialmente observable coloreando sus aristas con $k$ colores es NP-Completo.

La idea de la demostración es mostrar el problema como una reducción en tiempo polinomial del problema del Triángulo monocromático que se sabe es NP-completo. Para eso se partirá de un grafo arbitrario no dirigido $G$ y se creara ${\tilde {G}}$ que podrá ser coloreado con dos colores de tal forma que sea parcialmente observable si y solo si se puede colorear $G$ de tal forma que no exista un triángulo monocromático.

Demostración

Se sabe que se puede decidir en tiempo polinomial si un grafo dirigido y coloreado es parcialmente observable por tanto el problema es P.

Sea $G(E,V)$ un grafo no dirigido. Primero ordenamos sus aristas de cualquier manera $\{e_{1},e_{2},\dots ,e_{n}\}$, por cada arista en $e_{i}\in E$ en el grafo ${\tilde {G}}$ creamos una arista dirigida "real" $E_{i}$ que tendrá el mismo color que la arista $e_{i}$ en $G$.

Grafo que se usa para ilustrar la demostración.

Ahora considere todos los triángulos o 3-cliques $\{e_{a}-e_{b}-e_{c}:a<b<c\}$ en $G$ y ordenelos arbitrariamente $\{T_{1},T_{2},\dots ,T_{m}\}$, por cada triángulo en $G$ creamos en ${\tilde {G}}$ un nodo $T_{i}$ del cual salen aristas dirigidas a cada uno de los nodos iniciales de las aristas reales que representan sus componentes. e.g. el nodo que corresponde al triángulo $\{e_{a}-e_{b}-e_{c}:a<b<c\}$ tiene una arista dirigida al primer nodo de $E_{a}$, una a al primero de $E_{b}$ y una al de $E_{c}$.

Parte del grafo generado.

Después en ${\tilde {G}}$ creamos un árbol binario con los nodos $T_{i}$ como sus hojas. Este árbol tendrá $N=\lceil \log _{2}(S)\rceil$, el número de triángulos en el grafo y hojas del árbol.
Este no es el grafo terminado, pero vamos a probar que existe una forma de 2-colorear las aristas del grafo hasta ahora generado tal que todos los caminos desde la raíz hasta los últimos nodos de las aristas reales tienen una secuencia de colores diferente si y solo si el grafo $G$ puede ser coloreado con dos colores de tal forma que cualquier triángulo tiene tiene dos aristas con colores diferentes, llamamos a esta propiedad ser triángulo coloreable.

Supongamos que $G$ no puede ser triángulo coloreado. Sin importar que color se le asigne a cada arista en $G$ siempre tendrá un triángulo monocromático. Para un coloreo en especial llamemos éste triángulo $T$. Del nodo en ${\tilde {G}}$ que corresponde a $T$ salen tres aristas hacia las aristas reales, sin importar que colores se le asignen a estas aristas salientes siempre habrán dos con el mismo color que llegarán a aristas reales del triángulo $T$ que tienen el mismo color. Por tanto existen por lo menos dos caminos diferentes desde la raíz del árbol hasta los nodos terminales que tienen la misma secuencia de colores probando así por contra reciproca que si existe un 2-coloreo que distingue diferentes rutas, $G$ puede ser triángulo coloreado.

Ahora supongamos que $G$ puede ser triángulo coloreado. Coloreamos el árbol binario de tal forma que desde la raíz hasta las hojas cada camino tenga una secuencia de colores diferente. A las aristas reales, como se había dicho antes se colorean de la misma forma que en el grafo $G$ y por último las aristas que conectan los nodos-triángulos con las aristas reales como habíamos mencionado antes sin importar como se asignen los colores siempre habrán dos con el mismo color, las aristas con el mismo color serán aquellas que van a aristas reales con colores diferentes (que siempre existen por la hipótesis). Así se ha coloreado lo que llevamos de ${\tilde {G}}$ de tal forma que dos caminos diferentes siempre tengan secuencias de colores diferentes.

Ahora completamos ${\tilde {G}}$. Del árbol antes creado generamos $2S+1$ copias, todas conectadas a las aristas reales por las hojas de la misma forma que el primer árbol. De cada uno de los nodos finales de las aristas reales salen tres aristas hacia tres nodos cada uno de estos nodos que hacen parte de un grafo bipartito completo $K_{3,3}$ cada trío de nodos representa un nivel, de estos hacemos $N+3$ niveles. Finalmente cada uno de los nodos del último nivel se les conecta con las raíces de los árboles creados anteriormente.

Grafo con apenas una copia de las cinco que se deben generar.

Ahora vamos a probar que $G$ puede ser triángulo coloreado si y solo si ${\tilde {G}}$ puede ser 2-coloreado en sus aristas de tal forma que sea parcialmente observable.
Si $G$ es un grafo triángulo coloreable. Coloreamos ${\tilde {G}}$ de la siguiente manera: Las estructuras de árbol, las aristas que salen de los nodos y las aristas reales las coloreamos como se había hecho anteriormente.

Las que quedan se colorean de la siguiente forma: Un color $x$ para los que salen de los nodos finales de las aristas reales y los que entran en las raices de los árboles. Para las demás, las aristas que conforman los niveles bipartitos, se colorean del color $y$ que queda.

Grafo finalmente generado.

Si en un recorrido se reportan $N+3$ aristas del color $y$ y luego una de color $x$ sabemos que estamos en una raíz de una árbol pero no en cuál, igual si se sigue un camino y hasta una arista real, se sabrá exactamente cuál es, por eso el grafo ${\tilde {G}}$ es parcialmente observable.

Si $G$ no es triángulo coloreable para cualquier coloreo de $G$ existe un triángulo monocromático digamos $T$. Si consideremos en cada uno de los árboles los caminos que van desde la raíz hasta el nodo que representa $T$ cada camino representa una secuencia de colores como hay a lo más $S$ de tales secuencias y $2S+1$ árboles por principio del palomar habrá un secuencia que se repita en dos caminos diferentes lo que permite concluir que si completamos los ciclos pasa que existen dos ciclos diferentes con la misma secuencia de colores y hace que ${\tilde {G}}$ no sea parcialmente observable.