  The aim of this paper is to characterize an important class of marked
digraphs, called structurally observable graphs (SOGs), and to solve two
minimum realization problems. To begin with, by exploring structural
observability of large-scale Boolean networks (LSBNs), an underlying type of
SOGs is provided based on a recent observability criterion of conjunctive BNs.
Besides, SOGs are also proved to have important applicability to structural
observability of general discrete-time systems. Further, two minimum
realization strategies are considered to induce an SOG from an arbitrarily
given digraph by marking and controlling the minimal vertices, respectively. It
indicates that one can induce an observable system by means of adding the
minimal sensors or modifying the adjacency relation of minimal vertices.
Finally, the structural observability of finite-field networks, and the minimum
pinned node theorem for Boolean networks are displayed as application and
simulation. The most salient superiority is that the designed algorithms are
polynomial time and avoid exhaustive brute-force searches. It means that our
results can be applied to deal with the observability of large-scale systems
(particularly, LSBNs), whose observability analysis and the minimum controlled
node theorem are known as intractable problems.
