圖論誕生于七橋問題。出生于瑞士的偉大數(shù)學(xué)家歐拉(Leonhard Euler,1707—1783)提出并解決了該問題。七橋問題是這樣描述的:一個人是否能在一次步行中穿越哥尼斯堡(現(xiàn)在叫加里寧格勒,在波羅的海南岸)城中全部的七座橋后回到起點,且每座橋只經(jīng)過一次,圖示是這條河以及河上的兩個島和七座橋的草圖。請將該問題的數(shù)據(jù)模型抽象出來,并判斷此問題是否有解。
一般來說,可以通過判斷表中最后一列的最大值個數(shù)來判斷,因為背包問題的最優(yōu)值的產(chǎn)生只會在最后一列產(chǎn)生。