资源描述：
《农大离散数学课件第七章.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、图的基本概念第八章计算机科学广泛应用于运筹学，信息论，控制论，网络理论，化学生物学，物理学。原因在于这些学科的许多实际问题和理论问题可以概括为图论。第八、九章介绍与计算机科学关系密切的图论内容及其在实际中的应用。8.1无向图及有向图称{{a,b}
2、aAbB}为A与B的无序积，记作：A&B。习惯上，无序对{a,b}改记成(a,b)有序组(a,b)均用无序积：设A，B为二集合，一、基本图类及相关概念1.无向图无向图：无向图G是一个二元组，其中(1)V是一个非空集–––顶点集V(G)，
3、每个元素为顶点或结点；(2)E是无序积V&V的可重子集(元素可重复出现)，E–––边集E(G)，E中元素称为无向边。v4实际中，图是画出来的，画法：用小圆圈表示V中的每一个元素，如果(a,b)E，则在顶点a与b之间连线段。如：adcbe1e1e2e3e4e5e6e1e2e3e4e5e6v1v2v3v5有向图：有向图D是一个二元组，其中(1)V是非空集–––顶点集V(D)(2)E是笛卡尔积VV的可重子集，其元素为有向边实际中，画法同无向图，只是要根据E中元素的次序，由第一元素用方向线段指向第二
4、元素。2.有向图有限图：V，E均为有穷集合零图：E平凡图：E且
5、V
6、=1(n,m)图：
7、V
8、=n且
9、E
10、=m顶与边关联：如果ek=(vi,vj)E，称ek与vi关联，或ek与vj关联。3.相关概念顶与顶相邻：如果ek=(vi,vj)E，称vi与vj相邻；环：ek=中，若vi=vj，则ek称为环。边与边相邻：如果ek和ei至少有一个公共顶点关联，则称ek与ei相邻。若ek为有向边，则称vi邻接到vj,vj邻接于vi。孤立点：无边关联的顶点。平行边：无向图中，关联一对结点的无向边多于
11、一条，平行边的条数为重数；多重图：包含平行边的图。有向图中，关联一对顶点的无向边多于一条，且始、终点相同。简单图：既不包含平行边又不包含环的图。度：(1)在无向图G=中，与顶点v(vV)关联的边的数目(每个环计算两次)，记作：d(v)。二、度(2)在有向图D=中，以顶点v(vV)作为始点的边的数目，称为该顶点的出度，记作：d+(v)；出度与入度之和，称为顶点v的度：度是图的性质的重要判断依据。d(v)=d+(v)+d–(v)以顶点v作为终点的边的数目，称为该顶点的入度，记作：d–(
12、v)。最大度：(G)=max{d(v)
13、vV}最小度：(G)=min{d(v)
14、vV}度与边数的关系：在任何图中，顶点度数的总和等于边数之和的两倍。握手定理的推论：任何图中，度为奇数的顶点个数一定为偶数。(握手定理)出度与入度的关系：在有向图中，各顶点的出度之和等于各顶点的入度之和。度数序列：设V={v1,v2,…,vn}为图G的顶点集，称(d(v1),d(v2),…,d(vn))为G的度数序列。度数序列之和必为偶数(?)。例8.1(3,3,2,3)，(5,2,3,1,4)能成为图的度数序列吗？为
15、什么？解：由于这两个序列中，奇数个数均为奇数，由握手定理知，它们不能成为图的度数序列。例8.2已知图G中有10条边，4个3度顶点，其余顶点的度数均小于等于2，问G中至少有多少个顶点？为什么？解：图中边数m=10，由握手定理知，G中各顶点度数之和为20，4个3度顶点占去12度，还剩8度，若其余全是2度顶点,则需要4个顶点来占用8度，所以G至少有8个顶点。正则图：各顶点的度都相同的图为正则图；各顶点的度均为k的图为k次正则图。完全图：(1)设G=是n阶的无向简单图，如果G中任何一个顶点都与其余n–1
16、个顶点相邻，则G为无向完全图，记作：Kn。三、正则图与完全图(2)设D=是n阶的有向简单图，如果D中任意顶点u，vV(uv)，即有有向边，又有有向边，则称D为n阶有向完全图。如：四、子图与母图：(1)G=，G'=若V'V，E'E，则G是G'的母图，G'是G的子图，记作：G'G。(2)若G'G且V'=V，则G'是G的生成子图。(3)设V1V，且V1，以V1为顶点集，以2端点均在V1中的全体边为边集的G的子图，称为V1导出的导出子图。(4
17、)设E1E，且E1，以E1为顶点集，以E1中边关联的顶点的全体为顶点集的G的子图，称为E1导出的导出子图。例8.3列举下图的一些子图、真子图、生成子图、导出子图。e3e1e2e4e5v3v4v1v2解：自己对照定义做一做！(1)子图：子图的定义？举例(2)真子图：举例(3)生成子图：定义？举例(4)导出子图：定义？举例补图：给定一个图G=，以V为顶点集，以所有能使G成为完全图的添加边组成边集的图。记作：～G五、
