一类链状图的枚举特征——纪念李国平院士吴新谋教授诞辰100周年

在并发程序复杂性度量研究中, 作者曾定义了所谓B图, 用以作为 Ada 并发程序中一种会合关系的模型. 该文研究B 图的一种特殊情况---BB图, 一类链状图.n节点 BB 图是在n个节点、高为n-1的有向树上再添加若干条边,其约束条件是: 每个节点的入度不大于二, 每个节点的出度也不大于二. 该文给出BB 图图的若干若干枚举特征,并指出这些特征同第二类Stirling数的密切关系.

Enumerating Characteristics of a kind of Chain-like Graphs

We defined the so-called B graph in research on concurrent program complexity metrics as one the models of rendezvous relations in Ada programs. In this paper, we investigate a special case of  B graph ----- BB graph, and call it chain-like graph. A BB graph of order n is the oriented tree of order n and height n-1by adding some edges with the constraint that both of the in-degree and out-degree for every node are two at most. The paper gives some enumerating characteristics of BB Graph, and points out the closed relationship with the Stirling numbers of second kind.