Graph Observability: Definition, Condition and Algorithm
Open Access
Author:
Xiao, Yifei
Area of Honors:
Mathematics
Degree:
Bachelor of Science
Document Type:
Thesis
Thesis Supervisors:
Ting He, Thesis Supervisor Sergei Tabachnikov, Thesis Honors Advisor
Keywords:
graph theory observability colored graphs trackable graphs graph algorithm
Abstract:
A directed graph has the property observability means that if we move along colored edges among vertices, after sometime we are able to determine our location just by recording edge color sequences and without gathering any information about vertices. In mathematical terms, a graph with observability, or can be called observable graph, means that we can find out a particular vertex from identical vertices after a sufficient observation of edges. Graph observability can be applied in many fields like factory automation. Robots move on a network, localize themselves with very limited information and do particular task in designated area. In this paper, we will introduce the definition of observable and another weaker definition, partly observable. We will also give conditions to determine whether a given graph is observable or not and prove its correctness. Then we will move to an algorithm to help us justify the observability of more complicated graphs.
