一种图的st编号路径长度算法  

Algorithm of St-numbering Path Length of Graph

作　　者：刘阳[1] 晏立[1] 

机构地区：[1]江苏大学计算机科学与通信工程学院

出　　处：《微型电脑应用》2013年第1期61-64,共4页Microcomputer Applications

基　　金：国家自然科学基金(61005017);江苏省高校自然科学基金(10KJB520005)

摘　　要：通过对无向图的顶点标注st-编号,可以使它转换为一个有向图,根据有向图的方向可计算出从源点到汇点的路径长度。用DFS算法可计算出st-编号,但一个图有多种不同的st-编号方法,不能确定图的最长路径或者最短路径。使用移除法,连续移除根据时间戳选择出来的顶点,计算出图的st-编号,能够确定图的最长路径或者最短路径。st-编号路径长度在计算网络动态路由、计算最少着色数、减少框图高度等问题上有广泛的应用。An undirected graph with vertices labeled St-numbering can be turned into a directed graph.The DFS algorithm can com-pute a st-numbering of the graph,but cannot confirm its longest or shortest path,cause a graph may have several different st-numberings.While the Removing method,which successively remove vertices selected by the timestamp,can compute the st-numbering of the graph and confirm the longest or shortest path of it.The length of st-numberings graph has a wide application in the computation of network dynamic routing and the minimum number of Graph Coloring,reduction of height of the block diagram and so on.

关 键 词：图论 平面图 st-编号 最短路径 最长路径 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]