Topological sorting is, given with a directed acyclic graph G = (V,E), to find a total ordering of the vertices such that if (u,υ)∈E then u is ordered before υ. Instead of finding total orderings, we wish to find out how many total or-derings exist in a given directed acyclic graph G = (V, E). Here we call a total ordering as legal sequence and the problem as legal sequence number problem. In this paper, we first propose theorems on equivalent transformation of graphs with respect to legal sequence number. Then we give a formula to calculate legal sequence number of basic series-parallel digraphs and a way of the calculation for general series-parallel digraphs. Finally we apply our results to show how to obtain legal sequence number for a class of extended series-parallel digraphs.
展开▼
