有向图中几类支撑树数目的计算公式.PDFVIP

第 9 卷　第 1 期 运　 筹　 与 　管　 理 . 9, . 1 V o l N o 2000 年 3 月 O PERA T ION S R ESEA RCH AND M ANA GEM EN T SC IEN CE M ar. , 2000 　 　 有向图中几类支撑树数目的计算公式 翟晓燕 (广州大学 模糊系统与知识工程研究所, 广东 广州 510091) 摘　要: 将W . T. T ultte 提出的计算有向图中以某点为根的支撑出树数目的公式推广到了更一般 的情况, 并给出了有向图中具有不同特点的支撑树数目的计算公式。 关键词: 支撑树; 支撑出树; 支撑入树 中图分类号: O 221　　　文献标识码:A 　　　文章编号:(2000) The C a lcula ting Fo rm ula s on the Num be r of the S om e k ind S pa nning T re e s in D ig ra ph ZHA I X iao yan (Institu te of F ang S y stem s know led g e E ng ineering , Guang z hou U n iv. Guang z hou 510091, Ch ina) Abs tra c t: In th is paper , the fo rm u la fo r coun ting spann ing ou tgo ing tree w ith a roo t in digraph , w h ich p resen ted by W . T. T u ltte, is ex tended in to m o re general case, and som e differen t fo rm u las fo r conn ting differen t spann ing trees in digraph are p ropo sed. Ke y w o rds : spann ing tree; spann ing ou tgo ing tree; spann ing incom ing tree. 在交通或通讯网络中, 我们常常要寻找有一个枢纽点且与其它各地点都有联系的最简单 的联络网, 而这类联络网往往具有“树”的形状。那么在一个网络中具有“树”形状的联络网到底 有多少种呢? 这个问题就与有向图中具有某种特点的支撑树的计数问题有关。T u ltte 在文章 [1 ] 中提出了在有向图中计算以某一点为根的支撑出树数目的公式, 本文将在此基础上进一步 讨论有向图中具有不同特点的支撑树的计数方法, 并将 T u ltte 公式推广到更一般的情况。 　　收稿日期: ( ) 　　作者简介: 翟晓燕 1956 , 女, 广东东莞人, 广州大学模糊系统与知识工程研究所副研究员, 硕士, 1987 年毕业于国防科 技大学系统工程与数学系, 专业方向: 运筹学。 © 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved. 第 1 期　　　　　　翟晓燕: 有向图中几类支撑树数目的计算公式