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

数学物理学报 ›› 2010, Vol. 30 ›› Issue (5): 1248-1253.

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

王振宇

武汉数字工程研究所武汉 430074

收稿日期:2010-07-22 出版日期:2010-10-25 发布日期:2010-10-25

Enumerating Characteristics of a kind of Chain-like Graphs

WANG Zhen-Yu

Wuhan Digital Engineering Institute, Wuhan 430074

Received:2010-07-22 Online:2010-10-25 Published:2010-10-25

摘要/Abstract

摘要：

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

关键词: 并发程序复杂性度量, 链状图, 第二类Stirling数

Abstract:

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.

Key words: Concurrent program complexity metrics, Chain-like graph, Stirling numbers of second kind

中图分类号:

05C30

王振宇. 一类链状图的枚举特征——纪念李国平院士吴新谋教授诞辰100周年[J]. 数学物理学报, 2010, 30(5): 1248-1253.

WANG Zhen-Yu. Enumerating Characteristics of a kind of Chain-like Graphs[J]. Acta mathematica scientia,Series A, 2010, 30(5): 1248-1253.