a12}=1,说明v到ⅴs有一条路,可两步到达。 a162)=0,表明v到v6两步不能到达。继续计算A3 0000 21021 A3=A2.A 021121 01101 由于a163)=1,表明从ⅵ三步可达v6,若要了解这条路沿途经过哪些顶 点到达v6,只要回溯前面计算过程中的a16③这个数是怎样产生的,就可知 道。因为a163是由A2中的第一行与A中的第六列相应各数乘加而得,即 是由a152)=1和a6=1相乘而得。同理a1s2=1是由a1=1与aBs=1相乘而得。 因此有v→v3→s→v6。 §2.树与最小树 、树及其性质 连通且不含圈的无向图称为树,记为T(V,E) 设图T=(VE,顶点数为P,边数为q,则以下关于树的说法是等价的 1T是一棵树; 2T无圈,且qp-1; 3T连通,且q=p-1 4T无圈,但每加一新边即得唯一的一个圈: 5T连通,但每舍去一边就不连通 6T中任意两点,有唯一链相连。 、图的生成树 若图G的生成子图是一棵树,则称该树为G的生成树。26 a15(2)=1，说明 v1到 v5有一条路，可两步到达。 a16(2)=0，表明 v1到 v6两步不能到达。继续计算 A3                     =  = = 0 1 1 0 1 1 0 2 1 1 2 1 0 2 0 1 1 1 0 2 1 0 2 1 0 1 1 1 0 1 0 2 1 1 1 1 ( ) 3 2 (3) A A A aij 由于 a16(3)=1，表明从 v1 三步可达 v6，若要了解这条路沿途经过哪些顶 点到达 v6，只要回溯前面计算过程中的 a16(3)这个数是怎样产生的，就可知 道。因为 a16(3)是由 A2 中的第一行与 A 中的第六列相应各数乘加而得，即 是由 a15(2)=1 和 a56=1 相乘而得。同理 a15(2)=1 是由 a13=1 与 a35=1 相乘而得。 因此有 v1→v3→v5→v6。 §2. 树与最小树 一、树及其性质 连通且不含圈的无向图称为树，记为 T(V,E)。 设图 T=(V,E)，顶点数为 P，边数为 q，则以下关于树的说法是等价的。 1.T 是一棵树； 2.T 无圈，且 q=p－1； 3.T 连通，且 q=p－1； 4.T 无圈，但每加一新边即得唯一的一个圈； 5.T 连通，但每舍去一边就不连通； 6.T 中任意两点，有唯一链相连。 二、图的生成树 若图 G 的生成子图是一棵树，则称该树为 G 的生成树