资源描述：
《图和子图(1).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、图和子图(1)四川师范大学数学与软件科学学院周思波1.1基本概念现实世界的许多现象可以用一类图形来描述，这种图形由一个点集和连接这个点集中某些点对的线所构成．例如用点表示车站，线表示连接车站与车站的道路；或者用点表示人，连线表示一对朋友．在这种图形中，人们主要感兴趣的是：两点是否被一条线所连接，而连线的长短曲直则无关紧要．大量的这类事实的数学抽象，产生了图的概念．图的概念有序三元组G＝[V(G)，E(G)，ΨG]称为一个图，其中：ⅰ)V(G)称为顶点集合；ⅱ)E(G)∩V(G)=φ，E(G)称为边集合；ⅲ)ΨG是E(G)到{(a,b)
2、a,b∈V(G)}的映射，称为关联函数．V(G)中的元
3、素称为顶点，E(G)中的元素称为边．V(G)所含元素的个数即顶点个数称为图的阶，用
4、V(G)
5、表示．E(G)所含元素的个数称为G的边数，用
6、E(G)
7、表示．我们用G(p，q)表添一个阶为p、边数为q的图G，这时也说G是一个(p，q)图．例题G＝[V(G)，E(G)，ΨG]，其中：V(G)={v1,v2,v3,v4}，E(G)={e1,e2,e3,e4,e5,e6}，ΨG定义为：ΨG(e1)=v2v3，ΨG(e2)=v3v4ΨG(e3)=v4v4，ΨG(e4)=v2v4ΨG(e5)=v2v3，ΨG(e6)=v1v3e1e6e5e4e3e2e1e6e5e4e3e2相关概念在图G＝[V(G)，E
8、(G)，ΨG]中,若e∈E(G)，u,v∈V(G)，而ΨG(e)=(u,v)，则称u和v是e的端点，或e和u,v关联，此时称u和v是邻接的。若两条不同的边ei和ej有一个公共端点，则称是邻接的，不与任何边邻接的边称为孤立边，不与任何边关联的顶点称为孤立点。两端重合的边称为环，端点不同的边称为杆。若V(G)和E(G)都是有限集，则称G为有限图。G(0,0)称为空图，E(G)=φ即G是由孤立点所组成，称为零图。G(1,0)称为平凡图。简单图和完全图图中若连接两个相同顶点的边的条数大于1，则说这对顶点间有重边相连．同一对顶点间边的条数称为边的重数，既没有环也没有重边的图称为简单图，否则称为伪图，
9、没有环的伪图称为多重图．每对不同的顶点均有边相连的简单图称为完全图．n阶完全图记为Kn定理1.1：Kn有条边二分图图G的顶点集V(G)若能分成两个子集V1和V2，使得G的每条边有一个端点在V1，另一个端点在V2中，则G称为二分图或偶图．这样一个把V(G)分成两个集合V1、V2的分划(V1,V2)称为G的一个二分划．设简单二分图G的二分划为(V1,V2)，如果V1的每个顶点与V2的每一个顶点都邻接，则G称为完全二分图．若
10、V1
11、=m,
12、V2
13、=n,则这样的图记为Km,n定理1.2Km,n有mn条边。补图G是简单图，如果简单图GC满足，ⅰ)V(GC)=V(G)ⅱ)V(GC)中两点当且仅当它们在
14、G中不邻接时在GC中邻接．那么GC称为G的补图．G：GC：平面图在保持图的顶点和边的关联关系不变的情况下，一个图可以作出许多图形．如果一个图具有这样的图形，它的边仅在顶点处相交，则称它为平面图．判断图1是否为平面图？图1：图2：恒同和同构两个图H和G，如果V(H)＝V(G)，E(H)＝E(G)且ΨH＝ΨG，那么H和G就称为是恒同的，恒同的图当然可以用一个图形来表示．G＝[V(G)，E(G)，ΨG]和H＝[V(H)，E(H)，ΨH]，若存在1-1对应偶(θ,φ)，θ:V(G)→V(H)；φ:E(G)→E(H)，使得当且仅当ΨH(φ(e))=θ(u)θ(v)时，ΨG(e)=uv，则说这两个图同
15、构，记为G≌H度与正则图设v∈V(G)，G中与顶点v关联的边的数目称为v在G中的度(次)，记为dG(v)或d(v)．一个环的端点的度数计为2．如果d(v)是奇数，就说v是奇顶点；如果d(v)是偶数，就说v是偶顶点．如果一个图的每一个顶点都具有相同的度，则称这个图是正则图。每个顶点的度均为k的正则图，称为k-正则图．有关度的定理定理1.3图G中各顶点度数之和等于边数的2倍。推论1.4任意一个图奇顶点的个数是偶数．推论1.5正则图的阶与各顶点度数不全为奇数．子图设H和G是两个图，如果V(H)是V(G)的子集，E(H)是E(G)的子集且ΨH是ΨG在E(H)内的导出函数，那么H称为G的子图，此时G
16、称为H的母图，记为如果而H≠G，则说H是G的真子图，记为设H是G的子图，如果V(H)=V(G)，则H称为G的生成子图。导出子图设V’是V(G)的非空子集，H是G的一个子图，如果：ⅰ)V(H)=V’；ⅱ)E(H)={e
17、e∈E(G),ΨG(e)=uv，u,v∈V’}；ⅲ)ΨH是ΨG在E(H)上的导出函数。那么H称为由V’导出的G的子图，记为G[V’]导出子图G[V-V’]记为G-V’，它是从G中删除V’中的顶点及与这些顶点
