# 圖walk與simple path

有限無向簡單圖的walk要求每對連續頂點相鄰；simple path另要求所有頂點互異。

mko-graph-walk-simple-path · definition · v0.10.0



## 數學敘述

本輪固定有限無向無loop簡單圖。頂點序列(v0,...,vk)為walk，若每個連續無序對都是邊；其edge length為k。simple path是頂點不重複的walk。walk可重複頂點或邊，cycle與trail另有額外責任。





## 代表公式（精確 TeX）

W(v)





## 成立條件


- 頂點標籤為0到n-1，完整無向簡單邊集合與頂點序列明示。
- 空序列不作walk；單頂點序列是長度0的simple path。





## 符號作用域


- G — 有限無向簡單圖
- v — 頂點序列
- k — 邊長度





## 直觀、定義與常見誤解

先逐步核每個連續頂點對是否相鄰。

長度是邊數，等於頂點序列長度減一。

simple path禁止重複頂點；一般walk允許重複。

把任何頂點清單當walk、把頂點數當長度，或把無重複邊的trail與simple path混同。





## 已採用的推導導讀

[圖的 walk 與 simple path：逐對核對、長度與 trail 的區別](https://ocme.evemisslab.com/zh-Hant/derivations/derivation-mko-graph-walk-simple-path-01/)原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。





## 前置知識


- [有限簡單無向圖](https://ocme.evemisslab.com/zh-Hant/mko/mko-graph/) — 鄰接由完整邊集合給出。
- [數列](https://ocme.evemisslab.com/zh-Hant/mko/mko-sequence/) — walk以有序頂點序列表示。
- [二元關係與集合投影](https://ocme.evemisslab.com/zh-Hant/mko/mko-relation/) — 無向鄰接視為對稱關係。





## 驗證界線

只處理明示有限無向簡單圖；不宣稱directed walk、trail或cycle資格。

not_formalized

這不表示內容錯誤；只表示尚未登錄可重播的計算或形式證據。





## 下一個義務

加入連通分量。





## 同源結構化資料

本頁與互動版共用同一個物件與既有語言 edition；未新增證明或人工審定。

[原始 MKO JSON](https://ocme.evemisslab.com/data/mko/graph-walk-simple-path.json) · [純文字 Markdown](https://ocme.evemisslab.com/zh-Hant/mko/mko-graph-walk-simple-path/index.md)