求离散数学高手解题

Question

请写明详细解题步骤 谢谢！

Answer 1

14

D的邻接矩阵

A=

0 0 0 0

1 0 1 1

0 1 0 0

0 0 1 0

A²=(布尔矩阵)

0 0 0 0

0 1 1 0

1 0 1 1

0 1 0 0

A³=(布尔矩阵)

0 0 0 0

1 1 1 1

0 1 1 0

1 0 1 1

A⁴=

0 0 0 0

1 1 1 1

1 1 1 1

0 1 1 0

A⁵=

0 0 0 0

1 1 1 1

1 1 1 1

1 1 1 1

A⁶=A⁵

可达性矩阵

P=A∧A²∨A³∨A⁴∨A⁵=

0 0 0 0

1 1 1 1

1 1 1 1

1 1 1 1

15

显然2个3度顶点，只能通过3个2度节点来连接成树

因此T中有9个顶点，如图示

16

最小权等于1+2+3+5+7=18