通路[數學中的概念]

通路，圖論中的概念。一個圖中（無向圖或有向圖），點與邊交替連線成為通路，一條通路有它的起點和終點。

定義

給定圖G=<V,E>（無向圖或有向圖）, G中頂點與邊的交替序列£=v0e1v1e2…envn. 其中1<=i<=n, ei=(vi-1,vi), 則稱£為v0到vn的通路。v0和vn分別為通路的起點和終點, n(邊的條數)為通路的長度。

性質

結點數=邊數+1

若通路G 中所有頂點各異(當然邊也各異）, 則稱G 為初級通路。

若£中的所有邊互不相同，則稱£為簡單通路，當v0=v1時，稱此簡單通路為簡單迴路。

套用

七橋問題（一筆畫問題）

這個問題是這樣的：哥尼斯堡(Königsberg)城市有一條橫貫全城的普雷格爾(PreGel)河，城的各部分用七座橋連線，每逢假日，城中的居民進行環城的逛游，這樣就產生一個問題，能不能設計一次“逛游”，使得從某地出發對每座跨河橋走一次，而在遍歷了七橋之後卻又能回到原地。

通路[數學中的概念]

用圖表示如右圖：

大數學家歐拉在1736年的一篇論文中提出了一條簡單的準則，確定了哥尼斯堡七橋問題是不能解的。

其原理就是每個結點都要能進去多少次就能出來多少次。

把這種“一筆畫”性質稱作歐拉通路。