圖walk與simple path

數學敘述

本輪固定有限無向無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混同。

已採用的推導導讀

原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。

前置知識

• 有限簡單無向圖 — 鄰接由完整邊集合給出。
• 數列 — walk以有序頂點序列表示。
• 二元關係與集合投影 — 無向鄰接視為對稱關係。

驗證界線

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

not_formalized

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

下一個義務

加入連通分量。

同源結構化資料

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