有限有向圖

數學敘述

固定loop-free simple convention：每edge=(u,v)、u!=v，(u,v)與(v,u)不同，E為set故同向parallel duplicates禁止。out-degree與in-degree分開，兩者全圖總和皆等於|E|。walk每一步必須符合edge orientation；loops由negative boundary拒絕。

代表公式（精確 TeX）

D(V,E)

成立條件

• vertices標為0至n-1且n>=1。
• edges canonical lexicographic、unique、loop-free。

符號作用域

• D — 有限有向圖
• E — 有向邊集合

直觀、定義與常見誤解

edge orientation是語義的一部分。

in/out degrees各自總和為edge count。

loop與multiedge需要不同模型。

把(u,v)與(v,u)視為同edge，或沿用undirected degree。

已採用的推導導讀

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

前置知識

• 二元關係與集合投影 — ordered pairs。
• 集合 — vertex與edge sets。
• 集合基數比較 — degree counts。

驗證界線

本輪不含loops、parallel edges或undirected connectivity conventions。

not_formalized

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

下一個義務

加入topological ordering與flow networks。

同源結構化資料

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