Research Space for Linear Algebra & Discrete Mathematics
(<=) 觀察這個degree sequence有n-1個點, 此時再加上一個點 v, 使得 v 和這原本的n-1的點中degree最多的那d1個點相連, 可行成一新的圖, 該圖的 degree sequence就是(d1,d2,...,dn), 所以此deg sequence為graphical(=>) 在這裡我先假設 vi 為degree為di的點, for i=1,2,...,n, 也就是說 G=(V,E) 的點集(v1,v2,...,vn)所對應的degree為(d1,d2,...,dn), 和證明另一個方向時的想法差不多, 我們在這裡希望去掉v1時所產生的新的圖 H, H 為graphical且deg sequence就是題目中的那個, 可是在這之前得先建構出一個圖 G'=(V',E'), 使得 G'的deg sequence為(d1,d2,...,dn) 且 (v1,vi)∈E' (在這裡的邊皆為無向), for i=2,...,d1+1, 其建構方法如下:如果v1與vi不相連, for 1d1+1, 使得(v1,vj)∈E, 且因為di>dj, 所以必定存在一點vk, 使得(vi,vk)∈E但(vj,vk)∉E, 那麼此時更新E'為 E'=E+(v1,vi)-(v1,vj)+(vj,vk)-(vi,vk), 則更新後的圖的 sequence必與原圖相同, 這個步驟可以一直重複做到(v1,vi)∈E, for all i (1<i<=d1+1), 之後再刪掉v1, 就可以建構出我們要的那個圖了 寫的有點複雜但想法其實滿單純的, 希望你看的懂囉
謝謝助教~可以請助教舉個簡單的例子這個定理使用方式嗎?(扣除掉degree為奇數的點不為偶數個這種情形)
譬如(3,3,2,2,2) is graphical<=> (3-1,2-1,2-1,2)=(2,1,1,2) is graphical,當然你還可以一直reduce下去讓點數越來越少在(=>)證明中建構圖的地方, 同樣以此seq為例, 假設我們將(3,3,2,2,2)=(v1,v2,v3,v4,v5)畫成是一個bipartite的樣子, 那麼假設去掉v1, 因為v1與v2不相連, 所以去掉之後的deg sequence為(3,1,1,1)並不是我們要的, 所以我們得先改畫一下: 令vi=v2, 取 vj=v3, vk=v5 則將邊集去掉(v1,vj)以及(vi,vj), 再加上(v1,vi)以及(vj,vk)所形成的圖G', G'具有seq同為(3,3,2,2,2), 且去掉v1之後的seq就會是(2,1,1,2)
謝謝助教回答^^
勘誤: 前一次回覆中倒數第三句的"將邊集去掉(v1,vj)以及(vi,vj)", 應改成"將邊集去掉(v1,vj)以及(vi,vk)"
張貼留言
5 則留言:
(<=) 觀察這個degree sequence有n-1個點, 此時再加上一個點 v, 使得 v 和這原本的n-1的點中degree最多的那d1個點相連, 可行成一新的圖, 該圖的 degree sequence就是(d1,d2,...,dn), 所以此deg sequence為graphical
(=>) 在這裡我先假設 vi 為degree為di的點, for i=1,2,...,n, 也就是說 G=(V,E) 的點集(v1,v2,...,vn)所對應的degree為(d1,d2,...,dn), 和證明另一個方向時的想法差不多, 我們在這裡希望去掉v1時所產生的新的圖 H, H 為graphical且deg sequence就是題目中的那個, 可是在這之前得先建構出一個圖 G'=(V',E'), 使得 G'的deg sequence為(d1,d2,...,dn) 且 (v1,vi)∈E' (在這裡的邊皆為無向), for i=2,...,d1+1, 其建構方法如下:
如果v1與vi不相連, for 1d1+1, 使得(v1,vj)∈E, 且因為di>dj, 所以必定存在一點vk, 使得(vi,vk)∈E但(vj,vk)∉E, 那麼此時更新E'為 E'=E+(v1,vi)-(v1,vj)+(vj,vk)-(vi,vk), 則更新後的圖的 sequence必與原圖相同, 這個步驟可以一直重複做到(v1,vi)∈E, for all i (1<i<=d1+1), 之後再刪掉v1, 就可以建構出我們要的那個圖了
寫的有點複雜但想法其實滿單純的, 希望你看的懂囉
謝謝助教~
可以請助教舉個簡單的例子
這個定理使用方式嗎?
(扣除掉degree為奇數的點不為偶數個這種情形)
譬如(3,3,2,2,2) is graphical
<=> (3-1,2-1,2-1,2)=(2,1,1,2) is graphical,
當然你還可以一直reduce下去讓點數越來越少
在(=>)證明中建構圖的地方, 同樣以此seq為例, 假設我們將(3,3,2,2,2)=(v1,v2,v3,v4,v5)畫成是一個bipartite的樣子, 那麼假設去掉v1, 因為v1與v2不相連, 所以去掉之後的deg sequence為(3,1,1,1)並不是我們要的, 所以我們得先改畫一下: 令vi=v2, 取 vj=v3, vk=v5 則將邊集去掉(v1,vj)以及(vi,vj), 再加上(v1,vi)以及(vj,vk)所形成的圖G', G'具有seq同為(3,3,2,2,2), 且去掉v1之後的seq就會是(2,1,1,2)
謝謝助教回答^^
勘誤: 前一次回覆中倒數第三句的"將邊集去掉(v1,vj)以及(vi,vj)", 應改成"將邊集去掉(v1,vj)以及(vi,vk)"
張貼留言