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.
Accessible Version in Progress
We're generating an accessible version of this file to meet ADA Title II requirements. This process may take up to one hour. Please return later to access the accessible copy once it's ready.
You can still download the current version by clicking "OK".
What's happening:
An accessible PDF is being generated using Adobe with AI used to generate alternative text (alt text) for images in the PDF.