写的时后遇到两个问题:
第二题:证明若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呢?)
麻烦回答,谢谢。