Graph8/图论 例:用图描述一台自动售货机,只用5分,10 分二种硬币,满15分后压按钮,选择一块巧克 力,钱多了不找还 p 10 p 5 5 5 p LO 10 10 2/24/202111:38PM Deren Chen, Zhejiang UniV 11
G r a p h s / 图 论 2/24/2021 11:38 PM Deren Chen, Zhejiang Univ. 11 例：用图描述一台自动售货机，只用５分，１０ 分二种硬币，满１５分后压按钮，选择一块巧克 力，钱多了不找还
Graph8/图论 顶点:a:0 分边:5:投5分 b:5分 10:投10分 c:10分 p:压按扭动作 d:≥15分 表示已投入钱的状态 表示一种动作 自动售货机:有向加权图描绘得很清楚 (1)钱数不够,压按扭,不起作用 (2)钱数够了,压按扭,给过糖果回到0分状态 (3)钱超过15分,再加钱白加 2/24/202111:38PM Deren Chen, Zhejiang UniV
G r a p h s / 图 论 2/24/2021 11:38 PM Deren Chen, Zhejiang Univ. 12 顶点：ａ：０ 分边： ５：投５分 ｂ：５分 １０：投１０分 ｃ：１０分 ｐ：压按扭动作 ｄ：≥１５分 表示已投入钱的状态 表示一种动作 自动售货机：有向加权图描绘得很清楚 （1）钱数不够，压按扭，不起作用 （2）钱数够了，压按扭，给过糖果回到０分状态 （3）钱超过１５分，再加钱白加
Graph8/图论 用邻接矩阵讨论图G的连通性质 在邻接矩阵中,若a;=1,表明V;到V;有 条边,即V1到V;可达;若ai;=0不说明Ⅴ1到V 没有道路,若通过其他点中转,也有可能连通。作 邻接矩阵的普通矩阵乘法: B=A2=A·A=(bn)mn =∑ ik kj k=1 2/24/202111:38PM Deren Chen, Zhejiang UniV 13
G r a p h s / 图 论 2/24/2021 11:38 PM Deren Chen, Zhejiang Univ. 13 用邻接矩阵讨论图Ｇ的连通性质： 在邻接矩阵中，若ａij＝１，表明Ｖi到Ｖj有一 条边，即Ｖi到Ｖj可达；若ａij＝０不说明Ｖi到Ｖj 没有道路，若通过其他点中转，也有可能连通。作 邻接矩阵的普通矩阵乘法： Ｂ＝Ａ2 ＝Ａ·Ａ＝ i j n n b ( ) ｂi j＝ = n k i k k j a a 1
Graph8/图论 b;的值表示V;到V;路长为2的道路条 数,一般地,就有: [定理2 Am的元素m;:表示V;到V;长度为m的 道路条数。 2/24/202111:38PM Deren Chen, Zhejiang UniV 14
G r a p h s / 图 论 2/24/2021 11:38 PM Deren Chen, Zhejiang Univ. 14 ｂij的值表示Ｖi到Ｖj路长为２的道路条 数，一般地，就有： [定理2] Ａm的元素ｍij表示Ｖi到Ｖj长度为ｍ的 道路条数
Graph8/图论 [定理3]: n个顶点的图G中,如果V;到V (V;≠V;)有道路,则其最短的道路长 度≤n-1 [定理4]:n个顶点的图G中,A是G的邻接 矩阵。V;、V;是G的顶点, b=A+A++An-1 则v1到V;(V:≠;)连通当且仅当bi 非零。 2/24/202111:38PM Deren Chen, Zhejiang UniV
G r a p h s / 图 论 2/24/2021 11:38 PM Deren Chen, Zhejiang Univ. 15 [定理3]： ｎ个顶点的图Ｇ中，如果Ｖi到Ｖj （Ｖi≠Ｖj）有道路，则其最短的道路长 度≤ｎ－１。 [定理4]：ｎ个顶点的图Ｇ中，A是G的邻接 矩阵。Ｖi、Ｖj 是G的顶点， B=A+A2+…+An-1 则Ｖi到Ｖj（Ｖi≠Ｖj）连通当且仅当b ij 非零