图论问题

握手定理

1

无向树有2个4度顶点，3个3度顶点，其余顶点都是树叶，树的阶数是多少？

14

2

无向树中有1个4度顶点，1个3度顶点，1个2度顶点，其余顶点都是树叶，请问树中共有几个点？

8

欧拉通路

1

一个无向图有2个奇数度顶点，该图有什么？

（A）有欧拉通路，有欧拉回路

 (B) 啥也没有

 (C) 有欧拉回路，无欧拉通路

（D）有欧拉通路，无欧拉回路

D

2

下图有欧拉通路吗，有欧拉回路吗？

都有

3

下图可以在线不重合的情况下被一笔画出吗？

不能，超过两个奇数度顶点，无欧拉通路

邻接矩阵的幂

1

某有向图D的邻接矩阵的三次幂如下，请问该有向图中有几条长度为3的通路，几条长度为3的回路？

[[1,2,3],[4,5,6],[7,8,9]]

45条长度为3的通路

15条长度为3的回路

2

某有向图的邻接矩阵的2次幂如下，该图中有多少条从 v_3 到 v_2 的通路？

[[2,1,2,0],[1,1,1,1], [2,3,0,1],[2,1,1,1]]

3条