Branching, inaccessibility and immediate predecessors of the states in finite dynamic system of all possible orientations of a graph

Abstract

A finite dynamic system of graph orientations is considered. The states of such a system are all possible orientations of a given graph, and the evolutionary function of the system transforms digraphs by reorientation of all arcs entering the sinks. Branching of the states (the number of its immediate predecessors) is found, namely, it is equal to the number of such different subsets of the set of sources in the digraph from which there is an arc to each sink of this digraph, if it has sinks; and to the number of different subsets of the set of sources, including the empty one, in the digraph if there are no sinks in it. As a consequence immediate predecessors of the states is found, namely, all arcs emanating from all sources of the corresponding sets are reoriented, and all other arcs remain unchanged. The inaccessibility property is defined for a state, namely, it is inaccessible if and only if there is at least one sink in the digraph that is not adjacent to the sources.