Usuario:MariamAlvarez/Taller
Definición Asintóticamente Alcanzable
[editar]Un vértice de un grafo es asintóticamente si puede ser alcanzador por un camino de longitud arbitraria.
Verificación de Observabilidad
[editar]Teorema
[editar]Un grafo de aristas etiquetadas es observable si y solo si no existe una sucesión de caracteres perteneciente a dos ciclos diferentes y si no existe un vértice asintóticamente alcanzable del grafo del cual salgan dos aristas con el mismo carácter.
Demostración
[editar]→ Se probará la primera implicación por contradicción. Asumamos que es un grafo observable, sea una sucesión de caracteres que pertenece a dos ciclos diferentes y sea un vértice asintóticamente alcanzable del cual salgan dos aristas con el mismo carácter. Existe un entero , tal que es posible encontrar un camino de medida que termina en el vértice .
Ahora bien dado que del grafo salen dos aristas con el mismo carácter y se considera que dicho camino pertenece a la sucesión de caracteres , entonces se obtiene una secuencia arbitraria de caracteres .
Consideremos el conjunto , recordando que del vértice salen dos aristas con el mismo carácter, se obtiene que .
y esto contradice que sea observable.
← Sea el entero de tal forma que todo camino de medida mayor que tiene el ultimo vértice asintóticamente alcanzable, sea la sucesión de caracteres y considere dos caminos pertenecientes a . La intensión es ver que estos caminos se intersectan entre y donde 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 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 y esto contradice la hipótesis del teorema.
Corolario
[editar]En un grafo observable, son suficientes observaciones para localizar un agente.
Demostración
[editar]Si no fuera así implicaría que existe una sucesión de caracteres de tamaño tal que hay dos caminos pertenecientes a esta y que terminan en diferentes vértices.
Es decir hay 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.