概念導讀
有限簡單無向圖:鄰居、度數與握手公式
設 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|。
OCME · 中英數學知識與推導
299 份概念教學導讀;另有 36,000 題逐題詳解,兩者分開查找。
概念導讀
設 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|。
概念導讀
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 的邊。
概念導讀
有限無向無 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。
概念導讀
逐邊驗proper coloring並展示上界非自動最優。
概念導讀
完整核選邊與端點,再分清三種匹配性質。