一个在置换图中寻找DFS树的最优算法.PDF

第 10 卷　第 1 期 运　 筹　 与 　管　 理 . 10, . 1 V o l N o 2001 年 3 月 O PERA T ION S R ESEA RCH AND M ANA GEM EN T SC IEN CE M ar. , 2001 　 　 一个在置换图中寻找D FS 树的最优算法 王知人, 　王　平, 　徐玉辰 (燕山大学 数理系, 河北 秦皇岛 066004) 摘　要: 本文是通过在连通置换图中构造辅助树的方法, 给出了一个在具有 n 个顶点的置换图 G ( ) ( ) 中寻找深度优先支撑树 简称,D FS 树 的最优算法, 并证明了该算法的时间复杂性为O n 。 关键词: 最优算法; 支撑树; 置换图; 复杂性 中图分类号: 157. 5 ∶ 224　　　文献标识码: 　　　文章编号:(2001) O O A A n O p tim a l A lgo rithm fo r F ind ing D FS T re e on P e rm uta tion G ra phs , , W AN G Zh i ren W AN G P in XU Yu chen (Y anshan U n iversity , Q inhuang d ao 066004, Ch ina) Abs tra c t: In th is paper , w e develop a schem e fo r finding an aux iliary tree on connected per m u tation graph s and show that th is aux iliary tree con structed is D FS tree. T he p ropo sed al go rithm takes O (n ) tim e. : ; ; ; ; Ke y w o rds op tim al algo rithm spann ing tree perm u tation diagram com p lex ity 0　引言 一个无向图可记作 = ( , ) , 其中 ( ) = {1, 2, …, }是 的顶点集合, 且 ( ) ≠, G V E V G n G V G o E (G) 的每个元素与V (G ) 的一个或两个不同元素对应, 称为 G 的边集合。如果对于所有属于V 中的 和 , 关于{1, 2, …, }存在一个置换 , 并且 和 由图