walk(圖論中的walk概念)

walk在離散數學中具有重要的意義，是圖論中基礎的概念、定義。在對各種各樣的圖的研究中，發揮了巨大的作用。

walk是指從圖上一點到另外一點所經過的可以重合的點和不會重合的邊的集合，是非空交替序列。（walk不能算作是特殊的圖）

基本介紹

• 中文名：遊走
• 外文名：walk
• 適用領域：圖論
• 所屬學科：組合數學

定義

walk（遊走）是一個非空的交替序列v0 e1 v1 e2 v2 ... ek vk

u,v-walk指從點u到點v的walk

性質

walk包括的點vi可以重複。

每個u，v-walk一定包含一個u，v-path（u到v的path）。

例子：概念圖中的紅線部分，walk為v1 e1 v3 e2 v6 e9 v7 e14 v4 e5 v6 e8 v5 e12 v2。