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

计算机数学基础(上)第2编 图 论 第三章 图的基本概念 3.1 图的概念与性质 一、图的定义与表示 1。图 由结点的集合V和边的集合E组成的有序对V,E 称为图G。 2。有向图、无向图 每条边都是有向边的图称为有向图，每条边都是 无向边的图称为无向图，否则称为混合图。 3。孤立点、零图 不与其它结点相关联的结点称为孤立点，全部由 孤立点构成的图叫做零图。 4。边的重数 具有相同始点和终点的边称为平行边，平行边的 条数称为边的重数。 5。n 阶图 具有n个结点的图称为n阶图，具有n个结点和m 条边的图称为(n,m)图 6。结点的度数 图中与某结点v相关联的边数(自回路算两条边)， 称为该结点的度数，记作deg(v)。其中以v为始点的边 数称为出度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=V,E，则下列结论成立的是 。 A) B) C) D) 例题3： 设简单连通无向图G有12条边，G中有2个1度结点, 2个2度结点，3个4度结点，其余结点度数为3，求G中 有多少个结点。试作一个满足该条件的简单无向图。 解:设G中有x个结点，则3度的结点有x-7。 根据握手定理有， 解得 ,故G中有9个结点。 满足条件的图如下： 2。简单图 不含平行边和环(自回路)的图称为简单图。 在简单图中，任何结点的度数都小于等于n-1。这 是判断一个度数序列能否构成简单图的主要依据。 3。二部图 若将无向图G的结点集分为两部分，而每一部分中 任何两个结点之间都没有边相连，则G称为二部图。 4。完全图 每一对结点之间都有边相连的无向简单图称为无 向完全图，每一对结点之间都有方向相反的两条边相 连的有向简单图称为有向完全图。 具有n个结点的无向完全图Kn的边数为： 例题4： 设图G是有n个结点的无向完全图，则G的边数为 。 A) n(n-1) B) n(n+1) C) D) 5。正则图 若无向简单图G中每个结点的度数都为k，则G称 为k-正则图。 6。赋权图 若图G中的每一条边都有一个表示长度的实数， 则图G称为赋权图或网络。图G为无向图称为无向赋权 图，图G为有向图称为有向赋权图。 7。补图 由图G中的所有结点和构成完全图需添加的边所组成的图称为G的补图，记作 。 例题5： 已知图的结点集 以及图G和图D的 边集合分别为： 试作图G和图D，写出各结点的度数，回答图G、图D 是简单图还是多重图？ ?解：a d a d ? ? ? b c b c 图G 图D 图G： 图D： 图G不是简单无向图，图D是简单有向图。 8、子图 1。已知图G=V,E，如果 则G’=V’,E’称为G的子图。 2。如果 ，则称G’为G的真子图。 3。如果 ，则称G’为G的生成子图。 三、图的同构 如果图G中的结点