离散数学第101陈瑜

《离散数学第101陈瑜》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、陈瑜Email：yuchen@scu.edu.cn134028388009/3/2021离散　　数学计算机学院主要内容图的基本概念什么是图图的分类结点的度数握手定理子图与补图完全图补图图的同构9/3/20212计算机学院§10.1图的基本概念无序积的定义：设A,B为任意集合，称集合A&B＝{(a,b)

2、a∈A，b∈B}为A与B的无序积，（a,b）称为无序对。与序偶不同，无论a,b是否相等，均有：(a,b)＝(b,a)。9/3/20213计算机学院§10.1图的基本概念无序积的定义：设A,B为任意集合，称集合A&B＝{(a,b)

3、a∈A，b∈B}为A与B的无序积，（a,b）

4、称为无序对。与序偶不同，无论a,b是否相等，均有：(a,b)＝(b,a)。9/3/20214计算机学院图的定义定义10-1.1一个图是一个序偶，记为G＝，其中：1）V（G）＝{v1,v2,v3,…,vn}是一个有限的非空集合，vi(i＝1,2,3,…,n)称为结点,简称点，V为结点集；2）E（G）＝{e1,e2,e3,…,em}是一个有限的集合，ei(i＝1,2,3,…,m)称为边，E为边集，E中的每个元素都是由V中不同结点所构成的无序对，且不含重复元素。3）图G的结点数称为G的阶，用n表示，G的边数用m表示，也可表示成(G)=m。9/3/2021

5、5计算机学院图的定义定义10-1.1一个图是一个序偶，记为G＝，其中：1）V（G）＝{v1,v2,v3,…,vn}是一个有限的非空集合，vi(i＝1,2,3,…,n)称为结点,简称点，V为结点集；2）E（G）＝{e1,e2,e3,…,em}是一个有限的集合，ei(i＝1,2,3,…,m)称为边，E为边集，E中的每个元素都是由V中不同结点所构成的无序对，且不含重复元素。3）图G的结点数称为G的阶，用n表示，G的边数用m表示，也可表示成(G)=m。9/3/20216计算机学院图的定义定义10-1.1一个图是一个序偶，记为G＝，其中

6、：1）V（G）＝{v1,v2,v3,…,vn}是一个有限的非空集合，vi(i＝1,2,3,…,n)称为结点,简称点，V为结点集；2）E（G）＝{e1,e2,e3,…,em}是一个有限的集合，ei(i＝1,2,3,…,m)称为边，E为边集，E中的每个元素都是由V中不同结点所构成的无序对，且不含重复元素。3）图G的结点数称为G的阶，用n表示，G的边数用m表示，也可表示成(G)=m。9/3/20217计算机学院图的分类(按边的方向)若边e与无序结点对(u，v)相对应，则称边e为无向边,记为e＝(u，v)，这时称u，v是边e的两个端点；若边e与有序结点对相对应，则称边

7、e为有向边，记为e＝，这时称u是边e的始点。v是边e的终点，统称为e的端点；e是u的出边，是v的入边。每条边都是无向边的图称为无向图；每条边都是有向边的图称为有向图；有些边是无向边，而另一些是有向边的图称为混合图。用小圆圈表示V中的结点，用由u指向v的有向线段表示，无向线段表示(u,v)。9/3/20218计算机学院图的分类(按边的方向)若边e与无序结点对(u，v)相对应，则称边e为无向边,记为e＝(u，v)，这时称u，v是边e的两个端点；若边e与有序结点对相对应，则称边e为有向边，记为e＝，这时称u是边e的始点。v是边e的终点，统

8、称为e的端点；e是u的出边，是v的入边。每条边都是无向边的图称为无向图；每条边都是有向边的图称为有向图；有些边是无向边，而另一些是有向边的图称为混合图。用小圆圈表示V中的结点，用由u指向v的有向线段表示，无向线段表示(u,v)。9/3/20219计算机学院图的分类(按边的方向)若边e与无序结点对(u，v)相对应，则称边e为无向边,记为e＝(u，v)，这时称u，v是边e的两个端点；若边e与有序结点对相对应，则称边e为有向边，记为e＝，这时称u是边e的始点。v是边e的终点，统称为e的端点；e是u的出边，是v的入边。每条边都是无向边的图称为无向图；

9、每条边都是有向边的图称为有向图；有些边是无向边，而另一些是有向边的图称为混合图。用小圆圈表示V中的结点，用由u指向v的有向线段表示，无向线段表示(u,v)。9/3/202110计算机学院图的分类(按边的方向)若边e与无序结点对(u，v)相对应，则称边e为无向边,记为e＝(u，v)，这时称u，v是边e的两个端点；若边e与有序结点对相对应，则称边e为有向边，记为e＝，这时称u是边e的始点。v是边e的终点，统称为e的端点；e是u的出边，是v的入边。每条边都是无向边的图称为无向图；每条边都是有向边的图称为