(2) 0001 1000 若记项点的得分向量为S")=(s1,S2…,Sn),其中S是顶点i的得分,则由()不难知道 由(2)、(3)式容易算出双向连通的图(4)(见4个顶点情况)的得分向量是s=(2,2,11)y, 正如前面已经给出的。由S无法排出名次。 注意到矩阵A的第i行第j列位置元素表示有向图中从顶点i出发两步可以到达的顶点的数 目,因此s2)=A2e。(此处待续!) 其它情况对于既没有唯一完全路径,又不是双向连通的竞赛图,通常可以分解为若干 个双向连通的子竞赛图(只有一个顶点的图视为双向连通竞赛图的特例),在下图中8个顶 点的竞赛图分解为3个双向连通子竞赛图G1G2,G3, (此处缺图待补!) 图中子图之间的边被简化了,实际上两子图的每对顶点之间都有边相连,而这些连的方向必 是一致的,否则相应的子图可以合并为更大的双向连通子竞赛图,在每个这样的图中按上面 介绍的方法排名次,而子图之间的名次不难由它们相连边的方向决定。在图中G1中各点的 名次为{1,2,3,4};G,是3个顶点的双向连通竞赛图,5、6、7的名次相同;G只有1个 顶点8。故全部顶点的名次排列为{1,2,4,3,5(6,7),8} §8.6根树及其应用 根树 定义86.1如果一个有向图在不考虑方向时是一棵树,则称这个有向图为有向树 定义86.2设T是一棵有向树。若T中有一个顶点的入度为0,其余顶点的入度均为1,则 称T为根树。入度为0的顶点称为树根,入度为1且出度为0的顶点称为树叶,其余顶点 称为内点,树根和内点称为分支点。 注:1.从树根到任意顶点v的通路长度称为v的层数,层数最大顶点的层数称为树高 2由于根树中各有向边的方向是一致的,所以画根树的图示时通常省去各边上的箭头 并将树根画在最上方10 0110 0011 0001 1000 A = ⎡ ⎤ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ （2） 若记顶点的得分向量为 (1) 1 2 (, , , )T m s = ⋅⋅⋅ ss s ，其中 i s 是顶点i 的得分，则由(1)不难知道 (1) , (1,1, ,1)T s Ae e = = ⋅⋅⋅ （3） 由(2)、(3)式容易算出双向连通的图(4)（见 4 个顶点情况）的得分向量是 (1) (2,2,,1,1)T s = ， 正如前面已经给出的。由 s (1)无法排出名次。 注意到矩阵 2 A 的第 i 行第 j 列位置元素表示有向图中从顶点 i 出发两步可以到达的顶点的数 目，因此 (2) 2 s = A e 。（此处待续！） 其它情况 对于既没有唯一完全路径，又不是双向连通的竞赛图，通常可以分解为若干 个双向连通的子竞赛图（只有一个顶点的图视为双向连通竞赛图的特例），在下图中 8 个顶 点的竞赛图分解为 3 个双向连通子竞赛图 123 GGG , , ， （此处缺图待补！） 图中子图之间的边被简化了，实际上两子图的每对顶点之间都有边相连，而这些连的方向必 是一致的，否则相应的子图可以合并为更大的双向连通子竞赛图，在每个这样的图中按上面 介绍的方法排名次，而子图之间的名次不难由它们相连边的方向决定。在图中G1中各点的 名次为{1, 2, 3, 4}；G2 是 3 个顶点的双向连通竞赛图，5、6、7 的名次相同；G3 只有 1 个 顶点 8。故 全部顶点的名次排列为{1, 2, 4, 3, 5 (6, 7), 8}. §8.6 根树及其应用 一、根树 定义 8.6.1 如果一个有向图在不考虑方向时是一棵树，则称这个有向图为有向树。 定义 8.6.2 设 T 是一棵有向树。若 T 中有一个顶点的入度为 0，其余顶点的入度均为 1，则 称 T 为根树。入度为 0 的顶点称为树根，入度为 1 且出度为 0 的顶点称为树叶，其余顶点 称为内点，树根和内点称为分支点。 注：1.从树根到任意顶点 v 的通路长度称为 v 的层数，层数最大顶点的层数称为树高 2.由于根树中各有向边的方向是一致的，所以画根树的图示时通常省去各边上的箭头， 并将树根画在最上方