https://wiki.taigi.ima.org.tw/w/index.php?action=history&feed=atom&title=%E6%9F%AF%E5%B0%BC%E6%A0%BC%E5%BC%95%E7%90%86 2026-05-28T21:02:24Z 本 wiki 上此頁面的修訂紀錄 MediaWiki 1.43.1 https://wiki.taigi.ima.org.tw/w/index.php?title=%E6%9F%AF%E5%B0%BC%E6%A0%BC%E5%BC%95%E7%90%86&diff=438722&oldid=prev 2025-08-22T21:45:01Z

<p>從 JSON 檔案批量匯入</p> <p><b>新頁面</b></p><div>&#039;&#039;&#039;柯尼格引理&#039;&#039;&#039;（英語：König&#039;s lemma）為圖論中的一个定理。<br /> <br /> ==命題==<br /> <br /> 予遮的定具攏有無散个頂點毋過每一个頂點的度有限的連通圖 _ G _，著嘿 _ G _ 的任意頂點攏至少存在一條無散食的簡單路草。<br /> <br /> ==證明==<br /> <br /> 著 _ G _ 的任意頂點 _ v _ 一，因為 _ G _ 連通，故 _ v _ 一到 _ G _ 的任意頂點攏存在簡單路徑。因為 _ G _ 存在無散一个頂點，故事佇咧對 _ v _ 一出發的一个無窮的簡單路徑集。考慮這个散赤簡單路徑集。因為 _ v _ 一的度有限，故該無窮集必須是有一个無窮窮過 _ v _ 一的某一个相鄰頂點 _ v _ 二。同理，考察通過 _ v _ 一、_ v _ 二的該無窮簡單路徑子集，因為 _ v _ 二的度有限，故這寡無窮簡單路徑閣存在一無窮仔集通過 _ v _ 二的某一个相鄰頂點 _ v _ 三，注意 _ v _ 三 ≠ _ v _ 一。以此類推，會當一無窮簡單路徑 _ v _ 一 _ v _ 二 _ v _ 三 . . .。<br /> <br /> ==說明==<br /> <br /> * 上述證明為非構造證明，干焦說明存在性，但是無算出計算路草的算法（事實上，該算法無存在）。<br /> * 此結論定定做為一个特例應用佇樹仔：予散赤的所在，毋過逐个節點的分叉有限的樹仔，是至少愛佇咧一條對根節點出發的無窮路草。反之，若一粒樹仔無存在無散路草，而且無節點具有無窮分叉，則該樹仔的節點數有限。<br /> * 雖然講每一个節點的度有限，但是因為有無窮的節點，規个圖的度可能無上限（比如講會當構造以所有自然數為頂點的圖，予第 _ i _ 個節點的度為 _ i _）。<br /> <br /> [[分類: 待校正]]</div>

TaiwanTonguesApiRobot