Research Space for Linear Algebra & Discrete Mathematics
1. OK2. (a) (n-1)!/2(b) 可以(c) 將 K_n 的點集分成兩個具有相同 size 的 part A 和 B, 現在要去掉一些邊使得 A 與 B 為 disconnected, 若一個邊(a,b)的兩端點, a∈A, b∈B, 則 (a,b) 屬於 cut set, 因為總共有 (n/2)(n/2) 個邊, 其兩端點分屬於 A, B, 所以 cut set 的 size 就是 n^2/4(d) 將 n 個點分堆, 且兩邊的大小要一樣, 共有 c(n,n/2) 種分法, 每種分法會形成一符合題目敘述之cut set, 所以總數就是 c(n,n/2)3. (a) 如果這裡的cut set的定義是去掉cut set中的邊會導致該圖不連通, 因為要使得 K_m,n 為連通圖至少需要有 m+n-1 個邊, 所以最多可以去掉 mn-(m+n-1) 個邊使其仍為聯通圖, 此時只要再去掉任一邊即為不連通, 所以最大 cut set 的 size 即為 mn-(m+n-1)+1 = mn-m-n+2(b) 一個圖具有 Euler path 的充要條件就是恰有 0 或 2 個點的 degree 為奇數, 所以這裡定義的 K_m,n 只有在 m=2 時才會具有 Euler path
謝謝助教詳細的解答再問二、第一部份(c) (d)小題(c)的two equal subgraph 與(d)之equal bi-partion of the graph有何不同?
it seems like it's the same
張貼留言
3 則留言:
1. OK
2.
(a) (n-1)!/2
(b) 可以
(c) 將 K_n 的點集分成兩個具有相同 size 的 part A 和 B, 現在要去掉一些邊使得 A 與 B 為 disconnected, 若一個邊(a,b)的兩端點, a∈A, b∈B, 則 (a,b) 屬於 cut set, 因為總共有 (n/2)(n/2) 個邊, 其兩端點分屬於 A, B, 所以 cut set 的 size 就是 n^2/4
(d) 將 n 個點分堆, 且兩邊的大小要一樣, 共有 c(n,n/2) 種分法, 每種分法會形成一符合題目敘述之cut set, 所以總數就是 c(n,n/2)
3.
(a) 如果這裡的cut set的定義是去掉cut set中的邊會導致該圖不連通, 因為要使得 K_m,n 為連通圖至少需要有 m+n-1 個邊, 所以最多可以去掉 mn-(m+n-1) 個邊使其仍為聯通圖, 此時只要再去掉任一邊即為不連通, 所以最大 cut set 的 size 即為 mn-(m+n-1)+1 = mn-m-n+2
(b) 一個圖具有 Euler path 的充要條件就是恰有 0 或 2 個點的 degree 為奇數, 所以這裡定義的 K_m,n 只有在 m=2 時才會具有 Euler path
謝謝助教詳細的解答
再問
二、第一部份(c) (d)小題
(c)的two equal subgraph
與
(d)之equal bi-partion of the graph
有何不同?
it seems like it's the same
張貼留言