离散数学第101陈瑜.ppt

陈瑜
Email:******@scu.
**********
5/26/2018
离散数学
计算机学院
5/26/2018
1
计算机科学与工程学院
主要内容
图的基本概念
什么是图
图的分类
结点的度数
握手定理
子图与补图
完全图
补图
图的同构
5/26/2018
2
计算机学院
§ 图的基本概念
无序积的定义:设A,B 为任意集合,称集合A&B ={(a,b)|a∈A ,b∈B}为A 与B 的无序积,(a,b ) 称为无序对。
与序偶不同,无论a,b是否相等,均有:
(a,b)=(b,a)。
5/26/2018
3
计算机学院
§ 图的基本概念
无序积的定义:设A,B 为任意集合,称集合A&B ={(a,b)|a∈A ,b∈B}为A 与B 的无序积,(a,b ) 称为无序对。
与序偶不同,无论a,b是否相等,均有:
(a,b)=(b,a)。
5/26/2018
4
计算机学院
图的定义
定义10-一个图是一个序偶<V,E>,记为
G=<V,E>,其中:
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 。
5/26/2018
5
计算机学院
图的定义
定义10-一个图是一个序偶<V,E>,记为
G=<V,E>,其中:
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 。
5/26/2018
6
计算机学院
图的定义
定义10-一个图是一个序偶<V,E>,记为
G=<V,E>,其中:
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 。
5/26/2018
7
计算机学院
图的分类(按边的方向)
若边e与无序结点对(u,v)相对应,则称边e为无向边,记为e=(u,v),这时称u,v是边e的两个端点;
若边e与有序结点对<u,v>相对应,则称边e为有向边,记为e=<u,v>,这时称u是边e的始点。v是边e的终点,统称为e的端点;e是u的出边,是v的入边。
每条边都是无向边的图称为无向图;
每条边都是有向边的图称为有向图;
有些边是无向边,而另一些是有向边的图称为混合图。
用小圆圈表示V中的结点,用由u指向v的有向线段表示<u,v>,无向线段表示(u,v)。
5/26/2018
8
计算机学院
图的分类(按边的方向)
若边e与无序结点对(u,v)相对应,则称边e为无向边,记为e=(u,v),这时称u,v是边e的两个端点;
若边e与有序结点对<u,v>相对应,则称边e为有向边,记为e=<u,v>,这时称u是边e的始点。v是边e的终点,统称为e的端点;e是u的出边,是v的入边。
每条边都是无向边的图称为无向图;
每条边都是有向边的图称为有向图;
有些边是无向边,而另一些是有向边的图称为混合图。
用小圆圈表示V中的结点,用由u指向v的有向线段表示<u,v>,无向线段表示(u,v)。
5/26/2018
9
计算机学院
图的分类(按边的方向)
若边e与无序结点对(u,v)相对应,则称边e为无向边,记为e=(u,v),这时称u,v是边e的两个端点;
若边e与有序结点对<u,v>相对应,则称边e为有向边,记为e=<u,v>,这时称u是边e的始点。v是边e的终点,统称为e的端点;e是u的出边,是v的入边。
每条边都是无向边的图称为无向图;
每条边都是有向边的图称为有向图;
有些边是无向边,而另一些是有向边的图称为混合图。
用小圆圈表示V中的结点,用由u指向v的有向线段表示<u,v>