Graph8/图论 定义:n个顶点的图G中,A是G的邻接矩阵 B=A+A2++An-I +An 称为G的可达性矩阵。 有向图的连通性(n>1) (1)B中元素全为1分G强连通 (2)A∨A的可达性矩阵元素全为1分 G是弱连通的。 无向图的连通性(n>1) B中元素全为1G连通 2/24/202111:38PM Deren Chen, Zhejiang UniV
G r a p h s / 图 论 2/24/2021 11:38 PM Deren Chen, Zhejiang Univ. 16 定义：ｎ个顶点的图Ｇ中，A是G的邻接矩阵。 B=A+A2+…+An-1 +An 称为G的可达性矩阵。 有向图的连通性（n1）： （１）B中元素全为１Ｇ强连通 （2）Ａ∨ＡT的可达性矩阵元素全为１ Ｇ是弱连通的。 无向图的连通性（n1）： B中元素全为１Ｇ连通
Graph8/图论 7.5 Euler and hamilton path Konigsberg(哥尼斯堡)七桥问题 C B 问题:能否从河岸或小岛出发,通过每一座桥, 而且仅仅通过一次回到原地。 2/24/202111:38PM Deren Chen, Zhejiang UniV
G r a p h s / 图 论 2/24/2021 11:38 PM Deren Chen, Zhejiang Univ. 17 7.5 Euler and Hamilton Path Konigsberg(哥尼斯堡)七桥问题 问题：能否从河岸或小岛出发，通过每一座桥， 而且仅仅通过一次回到原地。 A C B D
Graph8/图论 Euler(欧拉)1736年对这个问题,给出了否 定的回答。将河岸和小岛作为图的顶点,七座 桥为边,构成一个无向重图,问题化为图论中 简单道路的问题: [定义]欧拉道路(回路) G=(V,E),称包含E中所有边的简 单道路为欧拉道路/ Euler path/E道路。 包含E中所有边的简单回路为欧拉回路 Euler circuit/e回路 2/24/202111:38PM Deren Chen, Zhejiang UniV
G r a p h s / 图 论 2/24/2021 11:38 PM Deren Chen, Zhejiang Univ. 18 Euler(欧拉)1736年对这个问题，给出了否 定的回答。将河岸和小岛作为图的顶点，七座 桥为边，构成一个无向重图，问题化为图论中 简单道路的问题： [定义]欧拉道路（回路）： Ｇ＝（Ｖ，Ｅ），称包含Ｅ中所有边的简 单道路为欧拉道路/Euler Path/E道路。 包含Ｅ中所有边的简单回路为欧拉回路 /Euler Circuit/E回路
Graph8/图论 [定理1](欧拉定理) 没有次为0的孤立顶点的无向图存 在欧拉道路的充要条件是 (1)图是连通的; (2)图中奇次顶点个数是0个或2个。 2/24/202111:38PM Deren Chen, Zhejiang UniV 19
G r a p h s / 图 论 2/24/2021 11:38 PM Deren Chen, Zhejiang Univ. 19 [定理1]（欧拉定理）： 没有次为０的孤立顶点的无向图存 在欧拉道路的充要条件是： (1)图是连通的； (2)图中奇次顶点个数是０个或2个