通路，圖論中的概念。一個圖中（無向圖或有向圖），點與邊交替連線成為通路，一條通路有它的起點和終點。
基本介紹
- 中文名：通路
- 外文名：path
- 學科：數學
- 所屬分支：圖論
定義,性質,套用,
定義
給定圖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年的一篇論文中提出了一條簡單的準則，確定了哥尼斯堡七橋問題是不能解的。
其原理就是每個結點都要能進去多少次就能出來多少次。
把這種“一筆畫”性質稱作歐拉通路。
