Usuario:MariamAlvarez/Taller

Definición Asintóticamente Alcanzable

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

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