Matemáticas - Teoría de grafos

grafo etiquetado es la asignación de etiquetas, tradicionalmente representada mediante enteros, a las aristas ovértices, o ambos, de un grafo.¹

Formalmente, dado un grafo G, un vértice etiquetado es una función que hace corresponder vértices de G a un conjunto de etiquetas. Un grafo con tal función definida es llamado grafo de vértices etiquetados. De la misma manera, una arista etiquetada es una función de asignación de aristas de G tal conjunto de «etiquetas». En este caso, G es llamado como grafo de aristas etiquetadas. Cuando las etiquetas de las aristas pertenecen a un conjunto ordenado ( i.e., los números reales), ésta puede ser llamada como grafo ponderado.

Cuando es usado sin calificación, el término grafo etiquetado reneralmente se refiere a un grafo con vértices etiquetados con todas las etiquetas distintas. Tal grafo puede ser equivalentemente etiquetado mediante enteros consecutivos {1, ..., n}, donde n es el número de vértices en el grafo.¹ Para muchas aplicaciones, a las aristas y los vérticesle corresponde etiquetas que tienen un significado en el dominio asociado. Por ejemplo, las aristas pueden ser asignadas mediante pesos que representan el «coste» de atravesar entre los vértices implicados.²

En la definición de arriba se entiende como grafo un grafo simple indirecto finito. Sin embargo, la noción de etiquetado puede ser aplicada a todas las extensiones y generalizaciones de grafos. Por ejemplo, en teoría de autómatas y teoría de lenguaje formal es conveniente considerar multigrafos etiquetados, i.e., un par de vértices puede ser conectado por varias aristas etiquetadas.

Historia

La mayoría de los grafos etiquetados tienen sus origenesen los etiquetados presentados por Alex Rosa en un artículo en 1967.⁴ Rosa identificó tres tipos de etiquetado, a los cuales llamó α-, β-, y ρ-etiquetado.⁵ Los β-etiquetados fueron más tarde renombrados como elegantes por S.W. Golomb y el nombre se ha hecho popular desde entonces.

Casos especiales

Etiquetado elegante

Un etiquetado elegante. Las etiquetas de los vértices están en negro, las etiquetas de las aristas en rojo.

Un grafo es denominado como elegante cuando sus vértices son etiquetados desde 0 a ${\displaystyle \|E\|}$, el tamaño del grafo, y este etiquetado induce un etiquetado de aristas desde 1 a ${\displaystyle \|E\|}$. Para cualquier arista e, los etiquetas de e son la diferencia positiva entre dos vértices incidentes con e. En otras palabras, si e es incidente con los vértices etiquetados k y j, e será etiquetado como ${\displaystyle \|k-j\|}$. Así pues, un grafo ${\displaystyle G:=(V,E)}$ es elegante si y sólo si existe una inyección que induce una biyección de E a los enteros positivos hasta ${\displaystyle \|E\|}$.

En su trabajo original, Rosa demostró que todos los grafos eulerianos con orden equivalente a 1 o 2 (mod 4) no son elegantes. El si ciertas familias de grafos son elegantes o no es una área de la teoría de grafos que está bajo intenso estudio. Podría decirse que, la conjetura no demostrada más grande de etiquetado de grafos es la conjetura de Ringel-Kotzig, la cual conjetura que todos los árboles son elegantes. Esto ha sido demostrado para todos los caminos, orugas, y muchas otras familias infinitas de los árboles. El mismo Kotzig ha llamado al esfuerzo de demostrar la conjetura una «enfermedad».

Etiquetado armonioso

Un grafo armonioso es un grafo con k aristas que permiten una inyección de los vértices de G al grupo de enteros módulo k que induce una biyección entre las aristas deG y los enteros positivos hasta ${\displaystyle \|E\|}$. Para cualquier arista e, los etiquetados de e son la suma de las etiquetas de dos vértices incidentes con e (mod q).

Coloración de grafos

Una coloración por vértices para ungrafo de Petersen, donde cada color representa una etiqueta.

La coloración de grafos es un caso especial de grafos etiquetados, tales que los vértices adyacentes y las aristas coincidentes deben tener diferentes etiquetas.

 grafo G es simétrico si, dado cualquier par de pares de vértices adyacentes u₁—v₁ y u₂—v₂ de G, existe un automorfismo

f: V(G) → V(G)

tal que

f(u₁) = u₂ and f(v₁) = v₂.¹

En otras palabras, un grafo es simétrico si su grupo automórfico actúa transitivamente sobre pares ordenados de vértices adyacentes (es decir, sobre los bordes considerados como teniendo una dirección).² Este grafo se denomina a veces también 1-arco-transitivo.^2 3

Por definición (ignorando u₁ y u₂), un grafo simétrico sin vértices aislados también debe ser vértice transitivo.¹ Ya que la definición anterior mapea un borde al otro, una grafo simétrico también debe ser arista transitivo. Sin embargo, un grafo arista transitivo no es necesariamente simétrico, ya que a—b puede mapear a c—d, pero no a d—c. Los grafos semi-simétricos, por ejemplo, son arista transitivos y regulares, pero no vértice transitivos.

Cada grafo simétrico conectado debe por lo tanto ser a la vez vértice transitivo y arista transitivo, y lo contrario es cierto para los grafos de grado impar.³ Sin embargo, para los grafos de grado par, existen grafos conectados que son vértice transitivos y arista transitivos, pero no simétricos.⁴ Tales grafos son llamados semi-transitivos.⁵ el grafo semi-transitivo conectado más pequeño es el grafo de Holt, de grado 4 y con 27 vértices.^1 6 Confusamente, algunos autores usan el término "grafo simétrico" hablando de grafos que son vértice transitivos y arista transitivos, pero no son arco transitivos. Una definición así incluiría los grafos semi-transitivos, que están excluidos en virtud de la definición anterior.

Un grafo distancia-transitivo es aquél donde en lugar de considerar pares de vértices adyacentes (es decir, los vértices separados por una arista), la definición comprende dos pares de vértices, cada uno a la misma distancia. Tales grafos son automáticamente simétricos, por definición.¹

Un t-arco es definido como una secuencia de t+1 vértices, tal que dos vértices consecutivos cualesquiera en la secuencia son adyacentes, y cualquier vértice repetido está separado por lo menos 2 pasos. Un grafo t-transitivo es un grafo tal que el grupo automórfico actúa transitivamente sobre t-arcos, pero no sobre (t+1)-arcos. Ya que 1-arcos son simplemente aristas, cada grafo simétrico de grado 3 o mayor debe ser t-transitivo para alguna t, y el valor de t puede ser usado para clasificar los grafos simétricos. Por ejemplo, el cubo es 2-transitivo.

Ejemplos

La combinación de la condición de simetría con la restricción que los grafos sean cúbicos (es decir, todos los vértices tengan grado 3) es muy restrictiva, y tales grafos son lo suficientemente raros para ser enumerados. El censo Foster proveen esa lista.⁷ El censo Foster fue iniciado en 1930 por Ronald M. Foster mientras era empleado de los Laboratorios Bell,⁸ y en 1988 (cuando Foster tenía 92 años¹ ) el censo Foster actualizado (listando todos los grafos simetricos cúbicos de hasta 512 vértices) fue publicado en forma de libro.⁹ Los primeros trece elementos de la lista son grafos simétricos cúbicos de hasta 30 vértices^10 11 (diez de ellos son también distancia-transitivos; las excepciones son como se indica):

Vértices	Diametro	Cintura	Grafo	Notas
4	1	3	El grafo completo K4	distancia-transitivo, 2-transitivo
6	2	4	El grafo bipartito completo K3,3	distancia-transitivo, 3-transitivo
8	3	4	Los vértices y las aristas del cubo	distancia-transitivo, 2-transitivo
10	2	5	El grafo de Petersen	distancia-transitivo, 3-transitivo
14	3	6	El grafo de Heawood	distancia-transitivo, 4-transitivo
16	4	6	El grafo de Möbius–Kantor	2-transitivo
18	4	6	El grafo de Pappus	distancia-transitivo, 3-transitivo
20	5	5	Los vértices y las aristas del dodecaedro	distancia-transitivo, 2-transitivo
20	5	6	El grafo de Desargues	distancia-transitivo, 3-transitivo
24	4	6	El grafo de Nauru (the grafo de generalized Petersen G(12,5))	2-transitivo
26	5	6	El grafo de F26A11	1-transitivo
28	4	7	El grafo de Coxeter	distancia-transitivo, 3-transitivo
30	4	8	El grafo de Tutte–Coxeter	distancia-transitivo, 5-transitivo

Otros grafos simétricos cúbicos conocidos son el grafo de Dyck, el grafo de Foster y el grafo de Biggs–Smith. Los diez grafos distancia-transitivos listado arriba, junto con el grafo de Foster y el grafo de Biggs–Smith, son los únicos grafos cúbicos distancia-transitivs.

Los grafos simetricos no cúbicos incluyen ciclos (de grado 2), grafos completos (de grado 4 o mayor cuando tienen 5 o más vértices), grafos hipercubos (de grado 4 o mayor cuando tienen 16 o más vértices), y los grafos formados por los vértices y aristas del octaedro, icosaedro, cuboctaedro, and icosidodecaedro. El grafo de Rado es un ejemplo de grafo simetrico con vértices infinitos y grado infinito.

 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 es un grafo observable y parcialmente observable.

Sea un grafo dirigido ${\displaystyle G(V,E)}$, sea ${\displaystyle \Sigma }$ un conjunto finito, a los elementos de ${\displaystyle \Sigma }$ les decimos sin distinción letras, etiquetas o colores que serán asignadas a las aristas o a los vértices según se especifique.

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

Un camino ${\displaystyle P}$ en ${\displaystyle G}$ es permitido por una palabra ${\displaystyle w\in \Sigma ^{*}}$ si la arista ${\displaystyle e_{i}}$ del camino está etiquetada por ${\displaystyle 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 ${\displaystyle R}$ y el verde por ${\displaystyle V}$ tenemos que el camino ${\displaystyle F-E-C-B}$ está permitido por la palabra ${\displaystyle RVR}$ y que no existe ningún camino permitido por la palabra ${\displaystyle RRV}$.

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

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

Un vértice de un grafo ${\displaystyle 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 ${\displaystyle G}$, y sus etiquetas en ${\displaystyle \Sigma }$ es observable si existe un entero ${\displaystyle T}$ tal que para toda ${\displaystyle \omega \in \Sigma ^{*}}$, donde ${\displaystyle \left\vert \omega \right\vert \geq T}$, se tiene que ${\displaystyle \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 ${\displaystyle 1\leq t\leq T}$ tal que ${\displaystyle \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 un 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 ${\displaystyle ARR}$ entonces no hay otra opción para el agente que estar en ${\displaystyle V_{4}}$ o igualmente si nos dan ${\displaystyle RAR}$ el agente no tiene otra opción que estar en ${\displaystyle 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 ${\displaystyle RRA}$ analizando el grafo podremos caer en cuenta que el agente puede estar ubicado en ${\displaystyle V_{1}}$ pero también en ${\displaystyle V_{4}}$.

Verificación de Observabilidad

El siguiente teorema nos dice que verificar si un grafo es observable es relativamente fácil pues depende de dos condiciones que se verifican rápidamente.
Teorema
Un grafo ${\displaystyle G}$ de aristas etiquetadas es observable si y solo si:

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

• No existe un vértice asintóticamente alcanzable del grafo ${\displaystyle G}$ del cual salgan dos aristas con el mismo carácter.

Demostración

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

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

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

← Sea el entero ${\displaystyle T_{1}}$ de tal forma que todo camino de medida mayor que ${\displaystyle T_{1}}$ tiene el último vértice asintóticamente alcanzable, sea la sucesión de caracteres ${\displaystyle \omega }$ y considere dos caminos pertenecientes a ${\displaystyle \omega }$. La intención es ver que estos caminos se intersectan entre ${\displaystyle T_{1}}$ y ${\displaystyle T_{1}+({\hat {n}})^{2}}$ donde ${\displaystyle {\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 ${\displaystyle ({\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 ${\displaystyle \omega }$ y esto contradice la hipótesis del teorema.

El siguiente corolario nos dice cómo el camino que debemos recorrer para determinar la posición en un grafo observable no es muy larga con respecto a la cantidad de nodos del grafo.
Corolario

En un grafo observable, son suficientes ${\displaystyle {\frac {(n(n-1))}{2}}}$ observaciones para localizar un agente. Donde ${\displaystyle n}$ es la cantidad de nodos del grafo.

Demostración

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

Es decir hay ${\displaystyle {\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

El siguiente teorema nos dice que para un gafo arbitrario y cualquier número de colores, el problema de etiquetar los vértices del grafo para hacerlo observable es NP-completo.

Teorema

Dados ${\displaystyle G}$ un grafo y ${\displaystyle k}$ un entero positivo , el problema de asignar ${\displaystyle k}$ colores a los vértices de ${\displaystyle G}$ para que sea observable es NP-completo..

Ilustración

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

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 ${\displaystyle 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 ${\displaystyle E}$ no tengan la misma coloración. Luego por cada ${\displaystyle v_{i}\in E}$ consideremos un ${\displaystyle v_{i}^{'}\in E^{'}}$ y por cada ${\displaystyle e_{i}\in E}$consideremos un ${\displaystyle v_{e_{i}}^{'}\in V^{'}}$, además si ${\displaystyle e_{i}=(v_{m},v_{n})\in E}$ entonces ${\displaystyle (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 está representado a mano derecha el grafo ${\displaystyle G}$ y a la izquierda se ve como se va formando el grafo ${\displaystyle G^{'}}$ y Coloreamos los nuevos vértices de azul. Notemos que en esta construcción se está 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 construcción

En este segundo paso lo que haremos es por cada ${\displaystyle v_{e_{i}}^{'}}$ consideraremos un ${\displaystyle v_{e_{i}}^{''}}$ en ${\displaystyle E^{'}}$ estos los colorearemos de un color distinto al color seleccionado para los ${\displaystyle v_{e_{i}}^{'}}$, además haremos que ${\displaystyle (v_{e_{i}}^{''},v_{e_{i}}^{'})}$ para todo ${\displaystyle 0$ y ${\displaystyle (v_{e_{j}}^{''},v_{e_{j+1}}^{''})}$ para ${\displaystyle 0$ estén en${\displaystyle 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 ${\displaystyle v_{i}^{'}}$añadimos dos vértices etiquetados con el color distinto al que utilizamos en los pasos anteriores llamemos ${\displaystyle R_{1},R_{2}}$ a ambos vértices a ${\displaystyle E^{'}}$ le añadimos las aristas ${\displaystyle (v_{i}^{'},R_{1}),(R_{1},R_{2})}$ y ${\displaystyle (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 ${\displaystyle G}$ es 3-Coloreable entonces por la construcción anterior cuando el agente reciba una sucesión que termina con ${\displaystyle ...RRV}$ (siguiendo las etiquetas dadas en el ejemplo ilustrativo) el agente sabrá que al recibir la ${\displaystyle V}$ ha pasado por ${\displaystyle v_{e_{1}}^{''}}$ luego de esto puede recibir solo azul o verde, en el caso en que salga azul entonces estará en ${\displaystyle v_{e_{1}}^{'}}$ y si recibe verde sabrá que está dirigiéndose hacia algún ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle G}$ es 3-coloreable y por al construcción no es posible que se dé ese caso. así que el grafo ${\displaystyle G^{'}}$ es observable. y el hecho de que ${\displaystyle G^{'}}$ sea observable obliga a que ${\displaystyle G}$ sea 3-coloreable por el mismo argumento.

Diseñar grafos parcialmente observables es NP-completo

El siguiente teorema nos dice que para un gafo arbitrario y cualquier número de colores, el problema de etiquetar las aristas del grafo para hacerlo parcialmente observable es NP-completo.
Note como en el teorema anterior etiquetábamos los vértices y en este las aristas. Establecer la complejidad en los casos complementarios (observable etiquetando aristas y parcialmente observable etiquetando vértices) es un problema abierto.
Teorema
El problema de determinar para un grafo dado ${\displaystyle G}$ y un entero ${\displaystyle k}$, si ${\displaystyle G}$ puede ser parcialmente observable coloreando sus aristas con ${\displaystyle 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 ${\displaystyle G}$ y se creara ${\displaystyle {\tilde {G}}}$ que podrá ser coloreado con dos colores de tal forma que sea parcialmente observable si y solo si se puede colorear ${\displaystyle 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.

Grafo que se usa para ilustrar la demostración.

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

Ahora considere todos los triángulos o 3-cliques ${\displaystyle \{e_{a}-e_{b}-e_{c}:a$ en ${\displaystyle G}$ y ordenelos arbitrariamente ${\displaystyle \{T_{1},T_{2},\dots ,T_{m}\}}$, por cada triángulo en ${\displaystyle G}$ creamos en ${\displaystyle {\tilde {G}}}$ un nodo ${\displaystyle 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 ${\displaystyle \{e_{a}-e_{b}-e_{c}:a$ tiene una arista dirigida al primer nodo de ${\displaystyle E_{a}}$, una a al primero de ${\displaystyle E_{b}}$ y una al de ${\displaystyle E_{c}}$.

Parte del grafo generado.

Después en ${\displaystyle {\tilde {G}}}$ creamos un árbol binario con los nodos ${\displaystyle T_{i}}$ como sus hojas. Este árbol tendrá ${\displaystyle 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 ${\displaystyle G}$ puede ser coloreado con dos colores de tal forma que cualquier triángulo tiene dos aristas con colores diferentes, llamamos a esta propiedad ser triángulo coloreable.

Supongamos que ${\displaystyle G}$ no puede ser triángulo coloreado. Sin importar que color se le asigne a cada arista en ${\displaystyle G}$ siempre tendrá un triángulo monocromático. Para un coloreo en especial llamemos éste triángulo ${\displaystyle T}$. Del nodo en ${\displaystyle {\tilde {G}}}$ que corresponde a ${\displaystyle 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 ${\displaystyle 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í porcontrarrecíproco que si existe un 2-coloreo que distingue diferentes rutas, ${\displaystyle G}$ puede ser triángulo coloreado.

Ahora supongamos que ${\displaystyle 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 ${\displaystyle 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á 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 ${\displaystyle {\tilde {G}}}$ de tal forma que dos caminos diferentes siempre tengan secuencias de colores diferentes.

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

Ahora completamos ${\displaystyle {\tilde {G}}}$. Del árbol antes creado generamos ${\displaystyle 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 ${\displaystyle K_{3,3}}$ cada trío de nodos representa un nivel, de estos hacemos${\displaystyle N+3}$ niveles. Finalmente cada uno de los nodos del último nivel se les conecta con las raíces de los árboles creados anteriormente.

Ahora vamos a probar que ${\displaystyle G}$ puede ser triángulo coloreado si y solo si ${\displaystyle {\tilde {G}}}$ puede ser 2-coloreado en sus aristas de tal forma que sea parcialmente observable.
Si ${\displaystyle G}$ es un grafo triángulo coloreable. Coloreamos ${\displaystyle {\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 ${\displaystyle x}$ para los que salen de los nodos finales de las aristas reales y los que entran en las raíces de los árboles. Para las demás, las aristas que conforman los niveles bipartitos, se colorean del color ${\displaystyle y}$ que queda.

Grafo finalmente generado.

Si en un recorrido se reportan ${\displaystyle N+3}$ aristas del color ${\displaystyle y}$ y luego una de color ${\displaystyle 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 ${\displaystyle {\tilde {G}}}$ es parcialmente observable.

Si ${\displaystyle G}$ no es triángulo coloreable para cualquier coloreo de ${\displaystyle G}$ existe un triángulo monocromático digamos ${\displaystyle T}$. Si consideremos en cada uno de los árboles los caminos que van desde la raíz hasta el nodo que representa ${\displaystyle T}$ cada camino representa una secuencia de colores como hay a lo más ${\displaystyle S}$ de tales secuencias y ${\displaystyle 2S+1}$ árboles por principio del palomar habrá una 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 ${\displaystyle {\tilde {G}}}$ no sea parcialmente observable.

Aplicaciones

La observabilidad en grafos se encuetra relacionada con áreas como dinámica simbólica, teoría de autómatas, teoría de control, modelos ocultos de markov, entre otros.

Sistemas Dinámicos de Eventos Discretos

El concepto de observabilidad parcial tratado en este artículo está relacionado con el concepto de observabilidad en sistemas dinámicos de eventos discretos (DEDS) tratado en Özveren & Cüneyt [4]. Allí, los autores definen los DEDS como grafos coloreados, con la diferencia de que se permite que las transiciones puedan ser no observables. Dichos sistemas son sistemas dinámicos en los cuales se tiene que el conjunto de estados es discreto y la transisición entre estos estados es controlada por eventos dentro del sistema. Algunos ejemplos de DEDS son los sistemas de colas, sistemas de tráfico aéreo y de telecomunicaciones, sistemas de cómputo, sistemas de bases de datos, entre otros.

Los DEDS se modelan a través de autómatas finitos no deterministas, pero se diferencian de la teoría clásica de autómatas en que en los DEDS los eventos se asume que son generados internamente por el sistema, y las señales de entrada al sistema son señales de control que habilitan o deshabilitan ciertos estados. Así, un DEDS se representa como la cuádrupla ${\displaystyle G=(X,\Sigma ,U,\Gamma )}$ en donde ${\displaystyle X}$ es el conjunto finitos de estados, ${\displaystyle \Sigma }$ es el conjunto (finito) de posibles eventos, ${\displaystyle U\subset 2^{\Sigma }}$ es el conjunto de entradas de control y ${\displaystyle \Gamma \subset \Sigma }$ es el conjunto de eventos observables. Adicional a esto se tienen las siguientes funciones,

• ${\displaystyle d:X\rightarrow 2^{\Sigma }}$
• ${\displaystyle e:X\rightarrow 2^{\Sigma }}$
• ${\displaystyle f:X\times X\rightarrow 2^{X}}$
• ${\displaystyle h:\Sigma \rightarrow \Gamma \cup \lbrace \epsilon \rbrace }$

Con ${\displaystyle d}$ especificando el conjunto de posibles eventos definidos en cada estado, ${\displaystyle e}$ el cojunto de eventos que no puede ser deshabilitado en cada estado, ${\displaystyle f}$ codificando las transiciones entre estados bajo diferentes eventos, y ${\displaystyle h}$ la función de salida. Así, la dinḿica del sistema se expresa como

${\displaystyle x[k+1]\in f(x[k],\sigma [k+1])}$

${\displaystyle \sigma [k+1]\in d(x[k])}$

En donde ${\displaystyle x[k]\in X}$ es el estado luego del ${\displaystyle k}$-ésimo evento y ${\displaystyle \sigma [k+1]\in \Sigma }$ es el ${\displaystyle (k+1)}$-ésimo evento. Lo expuesto hasta ahora permite dar la siguiente definición de observabilidad en DEDS, que en este contexto consiste en el problema de determinar el estado actual del sistema a partir de una secuencia de eventos observables.

Definición (Observabilidad de estados)[3,4]

Un sistema dinámico de eventos discretos ${\displaystyle G}$ se dice observable si existe algún entero ${\displaystyle n_{0}}$ tal que ${\displaystyle \forall x\in X,\forall s\in L(A,x)}$ tal que ${\displaystyle |s|\geq n_{0}}$, existe un prefijo de s, ${\displaystyle p\in L_{f}(A,x)}$ tal que ${\displaystyle |s/p|\leq n_{0}}$, ${\displaystyle f(x,p)}$ esta bien definida, y ${\displaystyle \forall y\in X,t\in L_{f}(A,x):h(t)=h(p)\Rightarrow f(y,t)=f(x,p)}$.

En la definición anterior ${\displaystyle L(A,x)}$ denota el lenguaje generado por ${\displaystyle A}$ y ${\displaystyle L_{f}(A,x):=\lbrace s\in L(A,x)\wedge s_{f}\in \Gamma \rbrace }$, es el conjunto de cadenas en ${\displaystyle L(A,x)}$ que tienen un evento oservable como su evento final ${\displaystyle s_{f}}$.

Modelos Ocultos de Markov

Los grafos hasta ahora tratados pueden considerarse como Modelos Ocultos de Márkov o HMM, con alfabeto finito. La diferencia con estos es que no se permiten probabilidades de transición distintas de 0 y 1, es decir, la transicicón de un estado a otro se permite o no.

Visto de esta manera, la observabilidad se traduce en el problema de decodificación en HMMs, el cual puede plantearse de la siguiente manera: "Dados un modelo oculto de Márkov ${\displaystyle (Q,V,\pi ,A,B)}$ y unsecuencia de observaciones ${\displaystyle O=O_{1}O_{2}...O_{T}}$, con ${\displaystyle O_{i}\in V}$ y ${\displaystyle T}$ el número de observaciones en la secuencia. ¿Cómo escoger una correspondiente secuencia de estados ocultos más probable ${\displaystyle Q=q_{1}q_{2}...q_{T}}$, que llevó a la observación particular?"

Dentro de la literatura referente a HMMs, existen diversas formas de abordar el problema recién mecionado. Para este caso particular (probalidades de transición 0 y 1 solamente) una estrategia usual es encontrar la mejor secuencia de estados (o camino) que maximice ${\displaystyle P(Q|O,\lambda )}$. La búsqueda de esta secuencia de estados es se realiza con el Algoritmo de Viterbi, el cual permite además una fácil implementación en software.