上課筆記有一題: n個點{1,2,3,.........,n}
1.simple graph 個數?
2.三角形123 有幾個?
3.所有三角形有幾個?
4.平均一個graph的三角形有幾個?
另外，98中山電機
1.How many ways can the undirected complete graph be oriented into a directed graph?
2.Given two selected vertices S and T, how many paths of length n-1 with distinct vertices
from vertex S to vertex T are contained in the graph?
我圖論算個數都不太會.....不知道怎麼想
麻煩助教了，謝謝
10 則留言:
1.2^c(n 2)
2.2^c(n 2)-3(因為三角形123必選)
3.c(n 3)*2^c(n 2)-3
4.1/6(tr(A)^3)
1.2^c(n 2) (因為每一個邊有A->B或A<-B兩種選擇)
2.(n-2)! (起終點固定)
中山電機
1.應該要扣掉某個點outdegree為0吧
2^(c(n 2)-c(n 1))
98中山那題他題目少打了, 前提是 "In an undirected complete graph with n distinct vertices," 才有下面的小題, 所以mango寫的沒錯
請問一下,中山電機第一題:
若是其他2到n的點,都指向1這點的情況
這樣還算是directed graph嗎?
1無法走到其他點..
還是我有誤解題目呢?
我把connected,directed想成同一個了@@
不好意思我也有答案~~可是可以解釋一下嗎?
因為我不知道怎麼取的~~
謝謝
1.你可以想成adjacency matrix，因此任兩點可以有邊或無邊。
2.同1.但要扣掉邊123
3.任三邊決定一個三角形且須包含1跟2條件(題組)
4.參考課本
原來上面是題組喔~
我一直在想(3)為何要-3
如果不用符合1.2性質，那算三角形個數?
應該怎麼算呢??
中山電機可以解釋一下嗎?
謝謝
98中山電機那一題, 1. 這邊orient an edge的意思就是把一個原本無向的邊變成是有向的, 而因為K_n有c(n,2)個邊, 每個邊都有兩個方向可以選, 所以將K_n變成directed complete graph的總方法數就是c^c(n,2)
2. 由 S 到 T 長度為 n-1 的path 為 S-v1-v2-...-v_(n-2)-T, 其中v1有n-2種可能, v2有n-3種, ..., 所以這種path的個數為 (n-2)!
張貼留言