Grafos observables

La idea de un grafo observable es un grafo dirigido y coloreado (ver Coloración de grafos ) en donde podemos colocar a un agente que 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á.

Analicemos un primer 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 una de colores emmitida 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}$ .

Teorema-(diseñar grafos observables es NP-completo)

Dados $G$ un grafo y $k$ un entero positivo , el problema 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 contruiremos 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 (ver coloración de grafos ) 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 (ver Coloración de grafos) que ya es NP-completo. Comencemos por la construcción de $G^{'}$

Paso 1

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 vertices 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

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

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 por 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.