图和子图.pptVIP

图和子图(1) 四川师范大学数学与软件科学学院 周思波 1.1 基本概念 现实世界的许多现象可以用一类图形来描述，这种图形由一个点集和连接这个点集中某些点对的线所构成．例如用点表示车站，线表示连接车站与车站的道路；或者用点表示人，连线表示一对朋友．在这种图形中，人们主要感兴趣的是：两点是否被一条线所连接，而连线的长短曲直则无关紧要．大量的这类事实的数学抽象，产生了图的概念． 图的概念 有序三元组G＝[V(G)，E(G)，ΨG]称为一个图，其中： ⅰ) V(G) 称为顶点集合； ⅱ) E(G)∩V(G)=φ，E(G)称为边集合； ⅲ) ΨG是E(G)到{(a,b)|a,b∈V(G)}的映射，称为关联函数． V(G)中的元素称为顶点，E(G)中的元素称为边．V(G)所含元素的个数即顶点个数称为图的阶，用|V(G)|表示．E(G)所含元素的个数称为G的边数，用|E(G)|表示．我们用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)=v1v3 相关概念 在图G＝[ V(G)， E(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，则说这对顶点间有重边相连．同一对顶点间边的条数称为边的重数，既没有环也没有重边的图称为简单图，否则称为伪图，没有环的伪图称为多重图． 每对不同的顶点均有边相连的简单图称为完全图．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称为完全二分图．若| V1 |=m,| V2 |=n,则这样的图记为Km,n 定理1.2 Km,n有mn条边。 补图 G是简单图，如果简单图GC满足， ⅰ) V(GC)= V(G) ⅱ) V(GC)中两点当且仅当它们在G中不邻接时在GC中邻接． 那么GC称为G的补图． 平面图 在保持图的顶点和边的关联关系不变的情况下，一个图可以作出许多图形．如果一个图具有这样的图形，它的边仅在顶点处相交，则称它为平面图． 判断图1是否为平面图？ 恒同和同构 两个图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，则说这两个图同构，记为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倍。 子图 设H和G是两个图，如果V(H)是V(G)的子集，E(H)是E(G)的子集且ΨH 是 ΨG在E(H)内的导出函数，那么H称为G的子图，此时G称为H的母图，记为 导出子图 设V’是V(G)的非空子集，H是G的一个子图，如果：ⅰ)V(H)=V’；ⅱ)E(H)={e|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’中的顶点及与这些顶点相关联的边所得到的子图。若V’={v}，则把G-{v}简记为G-