[圖論] complete graph

[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)

請問為什麼呢?


===================================

請高手相助

謝謝!!

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 218.166.118.226
推 chuo        :第4題就只是30的因數而已
→ mqazz1      :請問為什麼是30的因數?
→ chuo        :15 edges 每個edges提供了2個degree 共30個degree
→ chuo        :G is regular 所以 頂點個數一定是30的因數
推 TassTW      :....把 loop 算成半個 edge 也是很好笑