Grobner基理論在最短路徑問題中的應用

在最短路徑問題中,若連通圖中相鄰節(jié)點對xi和xj間的路徑長為aij,則節(jié)點之間的關系可用多項式xi-xj-aij描述,把所有的這種多項式以終點所表示的項為首項歸納和排序得到集合F,若存在最短路徑供選擇,則F生成理想的Gr?bner基為{1}. 因此,求節(jié)點xm到xk的最短路徑,可用多項式xk-xm對F中的元素約化,所得到的一個常數(shù)就是這條可達路徑的長度;若有多條路徑可供選擇,則每條路徑對應一個常數(shù),所有這些常數(shù)中的最小數(shù)就是最短路徑的長度.

作 者： 陳小松 彭豐富   作者單位： 中南大學,數(shù)學科學與計算技術(shù)學院,湖南,長沙,410083  刊 名： 中南工業(yè)大學學報(自然科學版)  ISTIC EI PKU 英文刊名： JOURNAL OF CENTRAL SOUTH UNIVERSITY OF TECHNOLOGY(NATURAL SCIENCE)  年，卷(期)： 2002 33(6)  分類號： O157.6 O51.26  關鍵詞： 最短路徑   Gr?bner基   約化  

【Grobner基理論在最短路徑問題中的應用】相關文章：

《數(shù)形結(jié)合在解題中的應用》電子教案04-25

社會交換理論在秘書公關中的應用11-26

端午最短寄語11-02

語文手抄報：強化理論在語文教學的應用07-01

臨床路徑總結(jié)11-19

《最佳路徑》課文03-05

《最佳路徑》教案04-25

《最佳路徑》教案03-06

最短的辭職書范文02-23

最短的晚安句子（精選140句）09-19