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 則留言:

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

    回覆刪除
  2. 請問大家
    要怎麼問問題??
    找不到按鈕(汗)
    謝謝

    回覆刪除
  3. 去公告那看
    寫信給助教
    通過後即可
    不過那篇好像失蹤了

    回覆刪除
  4. 我找到了
    謝謝qq22的幫忙

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

    回覆刪除