浙江大学：《数学建模 Mathematical Modeling》课程教学资源（课件讲稿）第十三章 图论模型

图论模型

图论模型

.循环比赛的名次 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) = =

双向连通竞赛图的名次排序s)=As4)=Ae 对于n(>3)个顶点的双向连通竞赛图,存在 正整数r,使邻接矩阵A满足A>0,A称素阵 素阵A的最大特征根为正单 A e m 根,对应正特征向量s,且22k k→∞,S(归一化局→S口用排名 几=1.4. 0011 4=|0001s=(0.323028001670230) 3 排名为{,2,4,3} {1,2,3,4}

s As A e k k k = = 双向连通竞赛图的名次排序 ( ) ( −1) • 对于n(>3)个顶点的双向连通竞赛图，存在 正整数r，使邻接矩阵A 满足Ar >0，A称素阵 s A e k k k = → ∞ λ lim • 素阵A的最大特征根为正单 根λ，对应正特征向量s，且 ⎥⎥⎥⎥⎦⎤ ⎢⎢⎢⎢⎣⎡ = 1 0 0 0 0 0 0 1 0 0 1 1 0 1 1 0 A 排名为{1，2，4，3} k s s →∞, (k ) (归一化后) → T s (0.323,0.280,0.167,0.230) 1.4, = λ = 用s排名 1 2 4 3 (4) {1, 2, 3, 4}?

6支球队比赛结果 000000 0 0000 00 000 111000 00 s=(4,3,3,2,2,1) S2)=(8,5,9,3,4,3)7 s3)=(1510,16,7,12,9),s(=(38,28,32,21,25,16)′ =2.232,S=(0.238,0.164,0.2310.113,0.1500.104) 排名次序为{1,3,2,5,4,6}

⎥⎥⎥⎥⎥⎥⎥⎦⎤ ⎢⎢⎢⎢⎢⎢⎢⎣⎡ = 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 1 1 1 0 1 0 1 1 1 A T T T T s s s s (15,10,16,7,12,9) , (38,28,32,21,25,16) (4,3,3,2,2,1) , (8,5,9,3,4,3) ( 3 ) ( 4 ) (1) ( 2 ) = = = = 1 2 3 4 5 6 6支球队比赛结果 T λ = 2.232, s = (0.238,0.164,0.231,0.113,0.150,0.104) 排名次序为{1，3， 2，5，4，6}

2.社会经济系统的冲量过程 例能源利用系统的预测 F能派利用量:2能源价格 3能源生产率;v环境质量; v ;工业产值;v就业机会; v人口总数。 系统的元素—图的顶点 元素间的影响一带方向的弧带符号的有向图 影响的正反面—弧旁的+、-号 影响—直接影响符号—客观规律;方针政策

2. 社会经济系统的冲量过程 + - + - + + + + - - + v2 • v1 v3 v4 v6 v7 v5 例 能源利用系统的预测 v1—能源利用量； v2—能源价格； v3—能源生产率； v4—环境质量； v5—工业产值； v6—就业机会； v7—人口总数。 系统的元素——图的顶点 元素间的影响——带方向的弧 带符号的有向图 影响的正反面——弧旁的+、– 号 影响——直接影响 符号——客观规律；方针政策

带符号有向图G1=(V,B的邻接矩阵A 2 顶点集E弧集 若 右v 为为 0,若vv,gE v 000000 100100 A 0010 00 0000 带符号的有向图G1 000001 000000」某时段v增加导致 定性模型 下时段v增加减少

带符号有向图 G 1=(V,E)的邻接矩阵A V~顶点集 E~弧集 ⎪ ⎩ ⎪ ⎨ ⎧ ∉ − − + = v v E v v v v a i j i j i j ij ， 若 若 为 ， 若 为 0 1, 1 + - + - + + + + - - + v 2 • v 1 v 3 v 4 v 6 v 7 v 5 ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ − − − − = 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 A - vi vj + 某时段 v i 增加导致 下时段 vj 增加减少 带符号的有向图 G 1 定性模型

加权有向图G2及其邻接矩阵W"2 0.7 0.3 2 0.5 某时段v增加1单位导致 0.8 7 下时段v增加w:单位 12 -0.50.8-1.20 5 6 0 070020 000000 20010 加权有向图G2 000000.3 定量模型 1.200001.50 00 A视为W的特例 000000

⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ − − − − = 1.5 0 0 0 0 0 0 0 0 0 0 0 0 1 1.2 0 0 0 0 1.5 0 0 0 0 0 0 0 0.3 0 2 0 0 1 0 0 0.7 0 0 0 0 0 0 0 0.5 0.8 1.2 0 0 0 W 加权有向图 G 2及其邻接矩阵 W 定量模型 某时段 v i 增加 1单位导致 下时段 vj 增加 wij单位 j w i v v ⎯⎯→ij A视为 W的特例 v 7 0.3 1 1.5 1 1.5 1.2 0.8 - 2 - 2 -0.7 -0.5 • v 1 v 2 v 3 v 4 v 5 v 6 加权有向图 G 2