71图的概念/ ntroduction of Graph 72图的术语/ Graph Terminology 73图的表示与同构/ Representing graph and graph Isomorphism 74连通性/ Connectivity 7.5欧拉道路与哈密尔顿道路/ Euler and hamilton paths 7.6最短道路问题/ hortest path problem 77平面图/ Planar graphs 78图的着色/ Graph coloring 2/24/202111:38PM Deren Chen, Zhejiang UniV
G r a p h s / 图 论 2/24/2021 11:38 PM Deren Chen, Zhejiang Univ. 1 7.1 图的概念/Introduction of Graph 7.2 图的术语/Graph Terminology 7.3 图的表示与同构/ Representing Graph and Graph Isomorphism 7.4 连通性/Connectivity 7.5 欧拉道路与哈密尔顿道路/ Euler and Hamilton Paths 7.6 最短道路问题/Shortest Path Problem 7.7 平面图/Planar Graphs 7.8 图的着色/Graph Coloring
Graph8/图论 74连通性/ Connectivity [定义]道路/path: 当G中相邻边的序列(Vo,V1), (V1,V2),(Vk-1,Vk)称为一条道 路(通路)。此道路的长度为k。也可以 以(V0,V1,…,V1)表示道路,V为 起点,V为终点。 当V。V时,该道路称为回路/ circuit 2/24/202111:38PM Deren Chen, Zhejiang UniV 2
G r a p h s / 图 论 2/24/2021 11:38 PM Deren Chen, Zhejiang Univ. 2 7.4 连通性/Connectivity [定义]道路/path： 当Ｇ中相邻边的序列（Ｖ0，Ｖ1）， （Ｖ1，Ｖ2），…（Ｖk-1，Ｖk）称为一条道 路（通路）。此道路的长度为ｋ。也可以 以（Ｖ0，Ｖ1，…，Ｖk）表示道路，Ｖ0为 起点，Ｖk为终点。 当Ｖ0 =Ｖk时，该道路称为回路/circuit
Graph8/图论 [定义]简单道路/ Simple path: 条道路中没有两条边是相同的,称 此道路为简单道路。当其是回路时,称 为简单回路/ Simple circuit [定义]基本道路/ lement path: 一条道路中,除了起点和终点可以相 同,没有其他相同顶点出现,称此道路 为基本道路。当其是回路时,称为基本 回路/ Element Circuit。 2/24/202111:38PM Deren Chen, Zhejiang UniV 3
G r a p h s / 图 论 2/24/2021 11:38 PM Deren Chen, Zhejiang Univ. 3 [定义]简单道路/Simple Path： 一条道路中没有两条边是相同的，称 此道路为简单道路。当其是回路时，称 为简单回路/Simple Circuit。 [定义]基本道路/Element Path： 一条道路中，除了起点和终点可以相 同，没有其他相同顶点出现，称此道路 为基本道路。当其是回路时，称为基本 回路/Element Circuit
GPap8/图论 4 e2 3 e=, e 1,e2’es’e4)是简单道路, 不是基本道路,因为(c,a,b,c,d, b)中b,c均出现了两次。但(c,d,b, c)是基本道路 2/24/202111:38PM Deren Chen, Zhejiang UniV
G r a p h s / 图 论 2/24/2021 11:38 PM Deren Chen, Zhejiang Univ. 4 e3 e5 e2 e1 d c b a e4 （ｅ5，ｅ1 ，ｅ2 ，ｅ3，ｅ4）是简单道路， 不是基本道路，因为（ｃ，ａ，ｂ，ｃ，ｄ， ｂ）中ｂ，ｃ均出现了两次。但（c，d，b， c）是基本道路
Graph8/图论 [定义]连通性/ connectivity 设G=(V,E),(V 0 )是G中的一条道路,则称V0到V连通 / connective或可达/ 说明:对无向图而言,若V到V可达,则 V到V0也可达。对有向图而言则未必。 2/24/202111:38PM Deren Chen, Zhejiang UniV
G r a p h s / 图 论 2/24/2021 11:38 PM Deren Chen, Zhejiang Univ. 5 [定义]连通性/connectivity： 设Ｇ＝（Ｖ，Ｅ），（Ｖ0，Ｖ1，…， Ｖk） 是G中的一条道路，则称Ｖ0到Ｖk连通 /connective或可达/。 说明：对无向图而言，若Ｖ0到Ｖk可达，则 Ｖk到Ｖ0也可达。对有向图而言则未必