图论与网络模型 及其应用(二 循环比赛的名次
图论与网络模型 及其应用(二) 循环比赛的名次
若干支球队参加单循环比赛,他们两两互相交锋,假 设每场比赛只计胜负且不允许平局在循环比赛结 束后怎样根据他们的比赛成绩排列名次? 考虑用点表示球队胜负用带箭头的弧表示,如1队 胜2队,表示为: 如图:1胜场,2,3各 胜3场,4,5各胜2 场,6队胜1场 2,3名难产,4,5名难
若干支球队参加单循环比赛,他们两两互相交锋,假 设每场比赛只计胜负,且不允许平局.在循环比赛结 束后怎样根据他们的比赛成绩排列名次? 考虑用点表示球队,胜负用带箭头的弧表示,如1队 胜2队,表示为: 1• •2 1• •2 6• •3 5• •4 如图:1胜4场,2,3各 胜3场,4,5各胜2 场,6队胜1场. 2,3名难产,4,5名难 产
有向图在每条边上都标出方向的图 竞赛图每对顶点之间都有一条边相连的有向图 两个顶点的竞赛图的排名不成问题 三个顶点的竞赛图只有两种形式: 四个顶点的竞赛图只有四种形式 通过全部顶点的有向路径称为完全路径
有向图:在每条边上都标出方向的图. 竞赛图:每对顶点之间都有一条边相连的有向图. 两个顶点的竞赛图的排名不成问题. 三个顶点的竞赛图只有两种形式: • • • 四个顶点的竞赛图只有四种形式: • • • • • • • • • • • • • • • • 通过全部顶点的有向路径称为完全路径
有唯一完全路径的竞赛图,此完全路径确定的顶 点的顺序与按得分多少排列的顺序是一致的 对于任何一对页点存在两条有向路径每条路径 由一条或几条边组成使两顶点可以互相连通,这 种有向图称为双向连通的 双向连通竞赛图的名次排序 竞赛图的邻接矩阵4=(a;)定义为 「1,存在从顶点到的有向边 -(0,否则
有唯一完全路径的竞赛图,此完全路径确定的顶 点的顺序与按得分多少排列的顺序是一致的. 对于任何一对顶点,存在两条有向路径(每条路径 由一条或几条边组成),使两顶点可以互相连通,这 种有向图称为双向连通的. 双向连通竞赛图的名次排序: . 0, 1, ( ) 从顶点 到 的有向边 否则 存在 竞赛图的邻接矩阵 定义为 i j a A a ij ij n n = =
如对图 3 0110 0001 1000 若顶点的得分向量为s=(s1,2…n)y,其中 s;是顶点得分 则 Ae,e=(1,1,…41) 对上图,s=(2,2,1,1)
• • • 如对图 • = 1 0 0 0 0 0 0 1 0 0 1 1 0 1 1 0 A 1 2 4 3 . ( , ,... ) , 1 2 是顶点 的得分 若顶点的得分向量为 其中 s i s s s s i T = n T 则 s = Ae, e = (1,1,...1) , (2,2,1,1) T 对 上 图 s =