图论1.ppt

文档介绍：Chapter 7 Graphs
图论
图/Graph:
可直观地表示离散对象之间的相互关系,研究它们的共性和特性,以便解决具体问题。
11/11/2017
1
Deren Chen, Zhejiang Univ.
图的概念/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
2
Deren Chen, Zhejiang Univ.
图的概念/Introduction of Graph
[定义]图
V是一个非空有限集,E是V上的一个二元关系,有序对(V,E)称为有向图/Directed Graph。
若将E中的有序对看成是无序的(即将e=(a,b)看成e={a,b}),则称(V,E)为无向图/Undirected Graph。有向图和无向图统称为图/Graph ,记为G 。
G = (V,E)
11/11/2017
3
Deren Chen, Zhejiang Univ.
[定义]顶点:
V中的元素称为顶点,用带标记的点表示,也称为结点/Vertices。
[定义]边:
在有向图G中,若e=(a,b)∈E,e称为G的有向边/directed edge。用由a到b带箭头的线把a和b连起来;
在无向图G中,若e=(a,b)∈E,e称为G的无向边/undirected edge 。a、b间用连线连结,
有向边和无向边统称为G的边/edge。
11/11/2017
4
Deren Chen, Zhejiang Univ.
[定义]图的分类
对图G=(V,E)。若对于任意的(a,b)∈E,a  b,则称图G为简单图/Simple Graph。

对图G=(V,E)。若允许E是一个重集,则称图G为重图/Multigraph。其相同的元素称为重边。
对图G=(V,E)。若G既允许是重图又允许是非简单图,则称图G为拟图/Pseudograph。

一般的G称为线性图/Linear Graph。
11/11/2017
5
Deren Chen, Zhejiang Univ.
图的术语/Graph Terminology
[定义]相邻和关联:
在无向图G中,若e=(a,b) ∈E,则称a与b相邻/adjacent,或边e关联a、b/incident或联结a、b/connect。a、b称为边e的端点或结束顶点/endpoint.
在有向图G中,若e=(a,b)∈E,即箭头由a到b,称a相邻到b,或a关联或联结b。a称为e的起点/initial vertex,b称为e的终点/terminal or end vertex。
11/11/2017
6
Deren Chen, Zhejiang Univ.
[定义]自回路:
若(a,a)∈E,({a,a}∈E),称边(a,a)({a,a})是自回路/loop。
[定义]孤立顶点:
若a∈V,a不与其他顶点相邻,称a为孤立顶点/isolated。
11/11/2017
7
Deren Chen, Zhejiang Univ.
[定义]顶点的次:
在无向图G中,与a相邻的顶点的数目称为a的次或度/degree。记为deg(a)或d(a)。
在有向图G中,以a为终点的边的条数称为a的入次或入度/in-degree。记为deg–(a)或d –(a)。以a为起点的边的条数称为a的出次或出度/out-degree。记为deg+(a)或d +(a)。
11/11/2017
8
Deren Chen, Zhejiang Univ.
[定理1 (Handshaking)] 设无向图G=(V,E)有e条边,则G中所有顶点的次之和等于e的两倍。
证明思路:利用数学归纳法。
[定理2] 无向图中次为奇数的顶点个数恰有偶数个。
证明思路:将图中顶点的次分类,再利用定理1。
11/11/2017
9
Deren Chen, Zhejiang Univ.
[定理3] 设有向图G=(V,E)有e条边,则G中所有顶点的入次之和等于所有顶点的出次之和,也等于e。
证明思路:利用数学归纳法。
11/11/2017
10
Deren