| 计算图中路径问题的代数方法及其应用 |
| |
| 引用本文： | 耿涛.计算图中路径问题的代数方法及其应用[J].大连大学学报,2009,30(6):1-5. |
| |
| 作者姓名： | 耿涛 |
| |
| 作者单位： | 海南大学,信息学院,海南,海口,570228 |
| |
| 基金项目： | 海南省教育厅创新基金 |
| |
| 摘 要： | 对于一个给定的有向图G，G中两个相邻顶点vi→vj的路径可以用多项式vi→vj来表示，并用dij记其边的权值，而dij可由在Ω={0，1}的范围内解线性方程组来确定。该结果可以用来解决有向图的最短路径、关键路径等问题，并且此方法还可推广到无向图，用来解决哈密顿道路和回路，欧拉道路和回路等问题。
|
| 关 键 词： | Grdbner基 约化 路径 权值 |
Algebra Method of Calculating Paths in Graph and Some Applications |
| |
| GENG Tao.Algebra Method of Calculating Paths in Graph and Some Applications[J].Journal of Dalian University,2009,30(6):1-5. |
| |
| Authors: | GENG Tao |
| |
| Institution: | GENG Tao(College of Information Science , Technology,Hainan University,Haikou 570228 China) |
| |
| Abstract: | There are a pair of adjacent points vi、vj(vivj) in the directed graph G,the path can be expressed by polynormal as vi-vj,and dij expresses weight of the edge.Ω={0,1},solving linear equations,then finding out dij.The results can be used to solve the shortest path and critical path in the directed graph G,in addition,it is effective in undirected graph,calculating Hamiltonian path and circuit and Euler path and circuit. |
| |
| Keywords: | bases reducing path weight |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
