离散数学讲义-图论

图论

?图的基本概念和性质?图的连通性及可达性?图的矩阵表示

?Euler图与Hamilton图?平面图

?对偶图与着色?树与生成树?根树及其应用

2013-7-22

图论

1

图论简介

2013-7-222

图论一、图的基本概念

一个图是一个序偶,记为G＝，其中：

V＝{v1,v(i2＝,v1,2,3,3,…,vn…}是一个有限的非空集合,vi,n)称为结点,简称点,V为结点集；

E＝e{e1,e2,e3,…,em}是一个有限的集合，i(i＝1,2,3,…,m)称为边,E为边集，E中的每个元素都有V中的结点对与之对应。

2013-7-22

图论

3

二、图的类型

1)若边e与无序结点对(u，v)相对应，则称边e为无向边,记为e＝(u，v)，这时称u，v是边e的两个端点；

2)若边e与有序结点对相对应，则称边e为有向边(或弧)，记为e＝，这时称u是边e的始点(或弧尾).v是边e的终点(或弧头)，统称为e的端点；

2013-7-22

图论

4