# 概念推導導讀

299 份概念教學導讀；另有 36,000 題逐題詳解，兩者分開查找。

[搜尋全部題目與詳解 →](/zh-Hant/explore/)

1共 5 項 · 第 1／1 頁



概念導讀



## [有限簡單無向圖：鄰居、度數與握手公式](/zh-Hant/derivations/derivation-mko-graph-01/?from=%2Fzh-Hant%2Fderivations%2F%3Fq%3Dmko-graph)

設 V={1,2,3,4,5}，邊以端點對清單輸入：(1,2)、(2,1)、(2,3)、(3,4)、(2,4)、(4,2)，每一項表示一條無向邊。把輸入正規化為邊集合 E，求每個頂點的鄰居集合 N(v) 與度數 deg(v)，核對度數和等於 2|E|，並對每個有限簡單無向圖證明握手公式 Σ_{v∈V} deg(v)=2|E|。

有限簡單無向圖

derivation-mko-graph-01



概念導讀



## [圖同構：以完整映射表逐項核對雙射與鄰接當且僅當](/zh-Hant/derivations/derivation-mko-graph-isomorphism-01/?from=%2Fzh-Hant%2Fderivations%2F%3Fq%3Dmko-graph)

G 的頂點為 1、2、3、4，邊為 {1,2}、{2,3}、{3,4}、{1,4}；H 的頂點為 a、b、c、d，邊為 {a,c}、{b,c}、{b,d}、{a,d}。證明映射 f：1↦a、2↦c、3↦b、4↦d 是圖同構 G→H；說明雙射 g：1↦a、2↦b、3↦c、4↦d 不是同構；並證明路徑 P（邊 {1,2}、{2,3}、{3,4}）與 H 不同構，即使 f 把 P 的每條邊都送到 H 的邊。

圖同構

derivation-mko-graph-isomorphism-01



概念導讀



## [圖的 walk 與 simple path：逐對核對、長度與 trail 的區別](/zh-Hant/derivations/derivation-mko-graph-walk-simple-path-01/?from=%2Fzh-Hant%2Fderivations%2F%3Fq%3Dmko-graph)

有限無向無 loop 簡單圖 G：V={0,1,2,3,4}，E={{0,1},{1,2},{2,3},{0,3},{1,3},{3,4}}。對頂點序列 W₁=(0,1,2,3,4)、W₂=(0,1,3,1,2)、W₃=(0,2,3)、W₄=(2,3,0,1,3,4)、W₅=(4)、W₆=(1,1) 逐一判定是否為 walk、長度為何、是否為 simple path；並證明 simple path 不重複邊，以及本圖中 simple path 的長度至多為 4。

圖walk與simple path

derivation-mko-graph-walk-simple-path-01



概念導讀



## [完整著色與非最優greedy trace](/zh-Hant/derivations/derivation-mko-graph-coloring-01/?from=%2Fzh-Hant%2Fderivations%2F%3Fq%3Dmko-graph)

逐邊驗proper coloring並展示上界非自動最優。

圖著色

derivation-mko-graph-coloring-01



概念導讀



## [P4中maximal與maximum的分界](/zh-Hant/derivations/derivation-mko-graph-matching-01/?from=%2Fzh-Hant%2Fderivations%2F%3Fq%3Dmko-graph)

完整核選邊與端點，再分清三種匹配性質。

圖匹配

derivation-mko-graph-matching-01





1共 5 項 · 第 1／1 頁