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也可达。对有向图而言则未必
Graph8/图论 [定义]无向图的连通性: 若G=(V,E)中任两个不同顶点 都连通,则称此无向图是连通的 / connected。 [定理1 任意一个连通无向图的任两个不同顶 点都存在一条简单道路。 2/24/202111:38PM Deren Chen, Zhejiang UniV
G r a p h s / 图 论 2/24/2021 11:38 PM Deren Chen, Zhejiang Univ. 6 [定理1] 任意一个连通无向图的任两个不同顶 点都存在一条简单道路。 [定义]无向图的连通性： 若Ｇ＝（Ｖ，Ｅ）中任两个不同顶点 都连通，则称此无向图是连通的 /connected
Graph8/图论 [定义]无向图的连通性: 若G=(V,E)中任两个顶点都连 通,则称此无向图是连通的/ connected [定义]连通分图/ connected components: 图G可分为几个不相连通的子图,每 子图本身都是连通的。称这几个子图为G 的连通分图 2/24/202111:38PM Deren Chen, Zhejiang UniV
G r a p h s / 图 论 2/24/2021 11:38 PM Deren Chen, Zhejiang Univ. 7 [定义]连通分图/connected components： 图Ｇ可分为几个不相连通的子图，每一 子图本身都是连通的。称这几个子图为Ｇ 的连通分图。 [定义]无向图的连通性： 若Ｇ＝（Ｖ，Ｅ）中任两个顶点都连 通，则称此无向图是连通的/connected
Graph8/图论 [定义]有向图的连通性: (1)弱连通: 若G=(V,E)对应的无向图是连通 图,则称G为弱连通/ weakly connected c (2)强连通: 若G=(V,E)中任两点间都有路, 即对a与b,a到b可达,b到a可达,称 G为强连通/ strongly connected 2/24/202111:38PM Deren Chen, Zhejiang UniV
G r a p h s / 图 论 2/24/2021 11:38 PM Deren Chen, Zhejiang Univ. 8 [定义]有向图的连通性： (1)弱连通： 若Ｇ＝（Ｖ，Ｅ）对应的无向图是连通 图，则称Ｇ为弱连通/weakly connected。 (2）强连通： 若Ｇ＝（Ｖ，Ｅ）中任两点间都有路， 即对ａ与ｂ，ａ到ｂ可达，ｂ到ａ可达，称 Ｇ为强连通/strongly connected
Graph8/图论 连通无向图: 弱连通 2/24/202111:38PM Deren Chen, Zhejiang UniV
G r a p h s / 图 论 2/24/2021 11:38 PM Deren Chen, Zhejiang Univ. 9 连通无向图: 弱连通
Graph8/图论 强连通 2/24/202111:38PM Deren Chen, Zhejiang UniV
G r a p h s / 图 论 2/24/2021 11:38 PM Deren Chen, Zhejiang Univ. 10 强连通: