图论模型
图论模型
.循环比赛的名次 6支球队比赛结果 n支球队循环赛,每场比赛 只计胜负,没有平局。 根据比赛结果排出各队名次 方法1:寻找按箭头方向通过 全部顶点的路径。 312456146325……卣无法排名 方法2:计算得分:1队胜4场,2,3队各胜3场,4,5 队各胜2场,6队胜1场。2,3队,4,5队无法排名 3→2,4→5d排名132456合理吗
1. 循环比赛的名次 • n支球队循环赛，每场比赛 只计胜负，没有平局。 6支球队比赛结果 1 2 3 4 5 6 • 根据比赛结果排出各队名次 方法1：寻找按箭头方向通过 全部顶点的路径。 312456 146325 …… 无法排名 方法2：计算得分：1队胜4场，2, 3队各胜3场，4, 5 队各胜2场， 6队胜1场。 2, 3队， 4, 5队无法排名 3→2，4 →5 排名 132456 合理吗
循环比赛的结果—竞赛图 每对顶点间都有边相连的有向图 3个顶点 的竞赛图 (2) 名次{1,2,3} (1,2,3)}并列 4个顶点 的竞赛图 2 34 (2) 名次1,2,3,421,34) (1,4),2}(1,2,(3,4 {1,2,3
1 2 3 (1) 1 2 3 (2) 1 2 4 3 (1) 1 2 4 3 (2) 1 2 4 3 (3) 1 2 4 3 (4) 循环比赛的结果——竞赛图 每对顶点间都有边相连的有向图 3个顶点 的竞赛图 名次 {1，2，3} {(1,2,3)}并列 {1, 2, 3, 4} {2,(1,3,4)} {(1,3,4), 2} 4个顶点 的竞赛图 名次 {(1,2),(3,4)} {1, 2, 3, 4}?
2 2 (1) (2) (3) 具有唯一的完全路径,如(1); 竞赛图的·双向连通图任一对顶点存在两条有 3种形式向路径相互连通,如(4); 其他,如(2),(3)。 必存在完全路径; 竞赛图 若存在唯一的完全路径,则由它确定的顶 的性质点顺序与按得分排列的顺序一致,如(1)
1 2 4 3 1 2 4 3 1 2 4 3 (1) (2) (3) 1 2 4 3 (4) • 具有唯一的完全路径，如(1)； 竞赛图的 3种形式 • 双向连通图——任一对顶点存在两条有 向路径相互连通，如(4)； • 其他，如(2)， (3) 。 竞赛图 的性质 • 必存在完全路径； • 若存在唯一的完全路径，则由它确定的顶 点顺序与按得分排列的顺序一致，如(1)
双向连通竞赛图G=(V,E)的名次排序 1,,∈E 邻接矩阵 3 0.vV E 01 0 得分向量s=(ss2…,s) 0011 A 0001 s=Ae=(2,2,1,1)~1级得分向量 s2=As=(3,2,2)~2级得分向量 s0=(3.3),s=(553=4s=r s5)=(8,6,3,5),s6)=(9,85,8) k→>∞,()→>? (13,13,8,9)′,s8)=(21,17913)
T s = Ae , e = (1,1,",1) s(1) = Ae = (2,2,1,1) T ~ 1级得分向量 ⎥⎥⎥⎥⎦⎤ ⎢⎢⎢⎢⎣⎡ = 1 0 0 0 0 0 0 1 0 0 1 1 0 1 1 0 A ⎩⎨⎧ ∉∈ = v v E v v E a i j i j ij 0, 1, 1 2 4 3 (4) 双向连通竞赛图G=(V,E)的名次排序 邻接矩阵 T n s (s ,s , ,s ) 得分向量 = 1 2 " s( 2) = As(1) = (3,2,1,2)T ~ 2级得分向量 T T s (3,3,2,3) , s (5,5,3,3) (3) ( 4 ) = = s As A e k k k = = ( ) ( −1) T T s (8,6,3,5) , s (9,8,5,8) (5) (6) = = , ? k →∞ s(k ) → "" T T s (13,13,8,9) ,s (21,17,9,13) (7) (8) = =