图论2.ppt

文档介绍：图的概念/Introduction of Graph
图的术语/Graph Terminology
图的表示与同构/
Representing Graph and Graph Isomorphism
连通性/Connectivity
欧拉道路与哈密尔顿道路/
Euler and Hamilton Paths
最短道路问题/Shortest Path Problem
平面图/Planar Graphs
图的着色/Graph Coloring
11/11/2017
1
Deren Chen, Zhejiang Univ.
连通性/Connectivity
[定义]道路/path:
当G中相邻边的序列(V0,V1),(V1,V2),…(Vk-1,Vk)称为一条道路(通路)。此道路的长度为k。也可以以(V0,V1,…,Vk)表示道路,V0为起点,Vk为终点。
当V0=Vk时,该道路称为回路/circuit。
11/11/2017
2
Deren Chen, Zhejiang Univ.
[定义]简单道路/Simple Path:
一条道路中没有两条边是相同的,称此道路为简单道路。当其是回路时,称为简单回路/Simple Circuit。
[定义]基本道路/Element Path:
一条道路中,除了起点和终点可以相同,没有其他相同顶点出现,称此道路为基本道路。当其是回路时,称为基本回路/Element Circuit。
11/11/2017
3
Deren Chen, Zhejiang Univ.
(e5,e1 ,e2 ,e3,e4)是简单道路,不是基本道路,因为(c,a,b,c,d,b)中b,c均出现了两次。但(c,d,b,c)是基本道路。
11/11/2017
4
Deren Chen, Zhejiang Univ.
[定义]连通性/connectivity:
设G=(V,E), (V0,V1,…,Vk) 是G中的一条道路,则称V0到Vk连通/connective或可达/。
说明:对无向图而言,若V0到Vk可达,则Vk到V0也可达。对有向图而言则未必。
11/11/2017
5
Deren Chen, Zhejiang Univ.
[定理1]
任意一个连通无向图的任两个不同顶点都存在一条简单道路。
[定义]无向图的连通性:
若G=(V,E)中任两个不同顶点都连通,则称此无向图是连通的/connected。
11/11/2017
6
Deren Chen, Zhejiang Univ.
[定义]连通分图/ponents:
图G可分为几个不相连通的子图,每一子图本身都是连通的。称这几个子图为G的连通分图。
[定义]无向图的连通性:
若G=(V,E)中任两个顶点都连通,则称此无向图是连通的/connected。
11/11/2017
7
Deren Chen, Zhejiang Univ.
[定义]有向图的连通性:
(1)弱连通:
若G=(V,E)对应的无向图是连通图,则称G为弱连通/weakly connected。
(2)强连通:
若G=(V,E)中任两点间都有路,即对a与b,a到b可达,b到a可达,称G为强连通/strongly connected。
11/11/2017
8
Deren Chen, Zhejiang Univ.
11/11/2017
9
Deren Chen, Zhejiang Univ.
11/11/2017
10
Deren Chen, Zhejiang Univ.