离散数学第3章图的基本概念

《离散数学第3章图的基本概念》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机数学基础(上)第2编图论第三章图的基本概念3.1图的概念与性质一、图的定义与表示1。图由结点的集合V和边的集合E组成的有序对称为图G。2。有向图、无向图每条边都是有向边的图称为有向图，每条边都是无向边的图称为无向图，否则称为混合图。3。孤立点、零图不与其它结点相关联的结点称为孤立点，全部由孤立点构成的图叫做零图。4。边的重数具有相同始点和终点的边称为平行边，平行边的条数称为边的重数。5。n阶图具有n个结点的图称为n阶图，具有n个结点和m条边的图称为(n,m)图6。结点的度数图中与某结点v相关联的边数(自回路算两条边)，称为该结点的度数，记作deg(v)。其中以v为

2、始点的边数称为出度deg+(v)，以v为终点的边数成为入度deg-(v)因此有图G中结点的最大、最小度数记做Δ(G)、δ(G)二、图的基本概念与握手定理1。握手定理图G中所有结点的度数之和等于边数的二倍。[推论1]在任何图中，度数为奇数的结点数必为偶数。[推论2]在有向图中，所有结点的入度之和等于所有结点的出度之和。例题1：已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是。解：例题2：设图G=，则下列结论成立的是。A)B)C)D)例题3：设简单连通无向图G有12条边，G中有2个1度结点,2个2度结点，3个4度结点，其余结点度数为3，求G中

3、有多少个结点。试作一个满足该条件的简单无向图。解:设G中有x个结点，则3度的结点有x-7。根据握手定理有，解得,故G中有9个结点。满足条件的图如下：2。简单图不含平行边和环(自回路)的图称为简单图。在简单图中，任何结点的度数都小于等于n-1。这是判断一个度数序列能否构成简单图的主要依据。3。二部图若将无向图G的结点集分为两部分，而每一部分中任何两个结点之间都没有边相连，则G称为二部图。4。完全图每一对结点之间都有边相连的无向简单图称为无向完全图，每一对结点之间都有方向相反的两条边相连的有向简单图称为有向完全图。具有n个结点的无向完全图Kn的边数为：例题4：设图G是有n个结点的无向

4、完全图，则G的边数为。A)n(n-1)B)n(n+1)C)D)C5。正则图若无向简单图G中每个结点的度数都为k，则G称为k-正则图。6。赋权图若图G中的每一条边都有一个表示长度的实数，则图G称为赋权图或网络。图G为无向图称为无向赋权图，图G为有向图称为有向赋权图。7。补图由图G中的所有结点和构成完全图需添加的边所组成的图称为G的补图，记作。例题5：已知图的结点集以及图G和图D的边集合分别为：试作图G和图D，写出各结点的度数，回答图G、图D是简单图还是多重图？解：adadbcbc图G图D图G：图D：图G不是简单无向图，图D是简单有向图。8、子图1。已知图G=，如果则G’=

5、称为G的子图。2。如果，则称G’为G的真子图。3。如果，则称G’为G的生成子图。三、图的同构如果图G中的结点集V与图G’中的结点集V’具有一一对应的关系，并且对应的边都具有相同的重数，则称G与G’同构，记作。因此，两图同构必须满足下列条件：⑴结点数相同，⑵边数相同，⑶度数相同的结点数相同。上述条件是两图同构的必要条件，但不是充分条件，也就是说，两个图即使满足上述条件也不一定同构。如果把其中一个图中的结点重新排列，边跟着结点移动，并且可以任意弯曲，能够与另一图完全重合，那么这两个图是同构的。四、通路与回路1。通路、回路在G=中，如果从结点v0依次经过边和结点

6、可以到达vn，则称v0与vn间存在通路，或v0与vn连通，记作v0～vn，如v0＝vn则称为回路。通路经过的边数称为通路的的长度。2。简单通路、简单回路没有重复边的通路称为简单通路，没有重复边的回路称为简单回路。3。基本通路、基本回路没有重复结点的通路称为基本通路，没有重复结点的回路称为基本回路。例题6：设G如图，已知通路⑴⑵⑶⑷试回答它们各是简单通路、简单回路、基本通路和基本回路。解：⑴是简单通路，基本通路，⑵是简单回路，但不是基本回路，⑶是简单回路，基本回路，⑷是简单通路，但不是基本通路。v1v2v5v3v4一、连通性若在无向图G中，任何两个不同的结点都是连通的则称G是连通图

7、。无向图中结点的连通关系具有自反性、对称性和传递性，所以结点的连通关系是等价关系。若图G不是连通图，但如果把G分成几个部分，每一个部分都是连通的，则每一个部分称为一个连通子图，每一个连通子图G’称为G的一个连通分支。G中相互连通的结点一定在同一连通分支中。无向图G的连通分支数记作W(G)。3.2图的连通性例如G：G不是连通图，但可以划分为三个连通分支。是一个连通分支，是一个连通分支，是一个连通分支。称为V的一个划分。二、有向连通图1。强连通图、单侧连通图、弱连通图在有向简单图D中