| 图的平面嵌入的一种新算法 |
| |
| 引用本文： | 王万树,罗涛. 图的平面嵌入的一种新算法[J]. 吉林大学学报(工学版), 1989, 0(1) |
| |
| 作者姓名： | 王万树 罗涛 |
| |
| 作者单位： | 吉林工业大学电子工程系(王万树)，吉林工业大学电子工程系(罗涛) |
| |
| 摘 要： | 一个图是平面图的充分必要条件是这个图存在对偶图。那么,给定任意图,对于图中每一条支路,如果在对偶图中存在,说明这条支路可以嵌入平面;如果在对偶图中不存在,说明这条支路不能嵌入平面。这既判定了图的平面性,又给出了图的可以嵌入平面的支路。同文献〔4,5〕的算法相比,本文的算法更加简捷,降低了算法的复杂性,节省了运算时间。该算法用FORTRAN语言在MC68000机上实现,结果准确,运行速度快。
|
| 关 键 词： | 平面嵌入 |
A Novel Method of Embeding Graph in The Plane |
| |
| Wang Wanshu Luo Tao. A Novel Method of Embeding Graph in The Plane[J]. Journal of Jilin University:Eng and Technol Ed, 1989, 0(1) |
| |
| Authors: | Wang Wanshu Luo Tao |
| |
| Affiliation: | Wang Wanshu Luo Tao |
| |
| Abstract: | The sufficient and necessary conditions for a planar graph is that this graph must be a dual graph. So if one branch of a given graph has a corresponding branch in the dual graph, this branch could be embe-ded in the plane; if not, this branch couldn't be embeded in the plane. According to this idea, we can not only determine the plane, but also find the branches that could be embeded in the plane. Comparing with other method[4,5], this method is more simple and direct. This method has been realized successfully in FORTRAN language by using MC68000 computer. |
| |
| Keywords: | embeding graph in the plane |
| 本文献已被 CNKI 等数据库收录！ |
|
