[问题] 关于HW3的问题

楼主: kiwaygo (鸡尾酒)   2008-10-16 18:19:22
写的时后遇到两个问题:
第二题:证明若G存在 u-to-v Eular Trail 则 G 为 connected graph 且
下列两叙述其中之一对....
题目是这样说,可是 Eular Trail 可以不是 connected graph 吧?
例如:
y ●
u ●──────● v
│ │
x ●──────┘
不是 connected graph 但有 u to v Eular Trail。
请问是题目有错呢?还是我对 Eular Trail的定义有问题?
(投影片上对 Eular Trail 的定义只有:traverse each edge only once)
第四题:题目要我们用矩阵表示是否存在 i-to-j walk of length <= k
,那么在第0步可以到达的点是否要算成存在呢?
(就是:从1→1、2→2...在矩阵中这些字段是否每个本来都固定填1呢?)
麻烦回答,谢谢。
作者: zarcen (微臣)   0000-00-00 00:00:00
第一个 如果u=v=y 会发生什么事情第二个 一个reflexive transitive closure of A的情况 第0步要填 一般的transitive closure不用至于该题怎么定义 就是题目要问的东西~"~我的看法 有错误麻烦指正与包涵
作者: imprazaguy (Wayne)   0000-00-00 00:00:00
第一题:参考课本p.534~ Definition11.15"with no isolated vertices"

Links booklink

Contact Us: admin [ a t ] ucptt.com