※ 引述《mqazz1 (無法顯示)》之銘言：
: 1. For n>=2, let G=(V,E) be the loop-free undirected graph, where V is the set
: of binary n-tuples (of 0's and 1's) and E={(v,w)|v,w in V and v,w differ in
: two positions}. Find κ(G) ?
: 我看到黃字 我想應該是2
: 請問這張圖在說甚麼呢? http://ppt.cc/xaKL
: ==============================
: 2. m,n為正整數, m<n, How many paths of length m are there in the complete
: graph K_n
: 答案: P(n, m+1) / 2
: 請問為什麼呢?
: ===============================
: 3. For n>=3, how many subgraphs does K_n have?
: n C(i,2)
: 答案: Σ C(n,i)*2
: i=1
: 請問為什麼呢?
: ===================================
: 4. G is regular with 15 edges, determine |V|
: 答案: |V|*deg(v) = 2*15 = 30
: |V| = 1,2,3,5,6,10,15,30 (if loops are allowed in G)
: 請問為什麼呢?
: ===================================
: 請高手相助
: 謝謝!!
試解2,3題好了~ (1.我忘了κ(G)是啥 4.我忘了regular的定義...)
2.
要建造所有不同的的paths of length m, 每一種path必含有m+1個vertex
以vertex的角度切入:
首先從n個點中選一個做為起點, 再從n-1個點中選一個以建造length = 1的path
(記得path中所有的vertex必相異)
再來從n-2個點中選一個以建造length = 2的path...以此類推建出長度為m的path
則總共方法數為:
n * (n-1) * (n-2) * ... * (n-m) = n! / (n-m-1)! = P(n, m+1)
而每一條 path 會被算到兩次 (起點與終點互換) 所以答案除以2
Ans = P(n, m+1) / 2
3.
C(n,i) => 從 Kn 中 任意選 i 個點之組合數
2 ^ C(i,2) => 在含 i 個點的subgraph中, 共有C(i,2)個edge, 而這些edge可有可無
因此共有2 ^ C(i,2)種的subgraph
Σ => 最後對於每一個i所建造的各自subgraph數作總和, 即為此Kn之subgraph總數
有錯多指教~~
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.167.65.183
※ 編輯: Conifers 來自: 218.167.65.183 (10/18 00:35)