2009-01-19

[離散] path相關問題

無向圖
Path: V0->V1->V2->......->Vn (點不重複)
V0=Vn 稱為close path (cycle)

疑問:

Q1:
V0->V1->V2 與 V2->V1->V0
這兩種算一樣還是不一樣的path ?

Q2:
V0->V1->V0
這種close path 能算是 長度為2的path?

Q3:
consider a complete graph of n vertex , n >= 4
The number of paths of length 3 is n*(n-1)*(n-1)*(n-1)
上面這敘述應該是錯吧 ?

謝謝

4 則留言:

黃子嘉 提到...

Q1: 一般來說這二個算同一個path
Q2: closed path, 也就是cycle, 也算是path, 但有些書的定義不算path
Q3: 以Q1的想法算是錯的, 我在書上最後的Note有提到, 我是把次序考慮進去, 所以才寫true

彌生 提到...

請問大家
要怎麼問問題??
找不到按鈕(汗)
謝謝

qq22 提到...

去公告那看
寫信給助教
通過後即可
不過那篇好像失蹤了

彌生 提到...

我找到了
謝謝qq22的幫忙

http://zjhwang.blogspot.com/2007/02/blog-post_26.html