离散数学：08图论a_图的基本概念

1、高级语言程序设计SEISEI程序设计基础 2007春季1离散数学 2007秋季1 图 论主要内容主要内容n图的基本概念图的基本概念n顶点的度数顶点的度数n图的同构图的同构n图的运算图的运算n图的子图与补图图的子图与补图高级语言程序设计SEISEI程序设计基础 2007春季2离散数学 2007秋季2n一个图G是一个三重组，其中V(G)是一个非空的结点（顶点）集合， E(G)是边的集合，G是从边集E到结点偶对集合上的函数。 一个图可以用一个图形表示。 图 论图基本概念图基本概念顶点的度数顶点的度数图的同构图的同构图的运算图的运算子图与补图子图与补图图的基本概念图的基本概念G=V(G),E(G),G

2、V(G)=a,b,c,d E(G)=e1,e2,e3,e4,e6,e7G(e1)=(a,b),G(e2)=(a,c),G(e3)=(b,d), G(e4)=(b,c),G(e5)=(d,c),G(e6)=(a,d),G(e7)=(b,b)。高级语言程序设计SEISEI程序设计基础 2007春季3离散数学 2007秋季3n定义中的结点偶对可以是有序的，也可以是无序的。若边e所对应的偶对(a,b)是有序的，即序偶，则称e是有向边。有向边简称弧，a称为弧e的始点，b称为弧e的终点，统称为e的端点。称e是关联于结点a和b的，结点a和b是邻接的。若边e所对应的偶对(a,b)是无序的，则称e是无向边。无向

3、边简称棱，除无始点和终点概念外，其它与有向边相同。 图 论图基本概念图基本概念顶点的度数顶点的度数图的同构图的同构图的运算图的运算子图与补图子图与补图图的基本概念图的基本概念高级语言程序设计SEISEI程序设计基础 2007春季4离散数学 2007秋季4n每一条边都是有向边的图称为有向图；每一条边都是无向边的图称为无向图；如果在图中一些边是有向边，而另一些边是无向边，则称这个图是混合图。n约定：表示有向边，(a,b)表示无向边，a,b既表示有向边又表示无向边。于是图的三元组表达形式可以变为二元组形式G=，其中E为偶对集合，隐含表示图中的边。n把无向图中每一条边都看成两条方向不同的有向边，无向图

4、就成为有向图；把有向图中每条有向边都看成无向边，就成为无向图。通常称这个无向图是该有向图的底图。 图 论图基本概念图基本概念顶点的度数顶点的度数图的同构图的同构图的运算图的运算子图与补图子图与补图图的基本概念图的基本概念高级语言程序设计SEISEI程序设计基础 2007春季5离散数学 2007秋季5n在图中，不与任何结点邻接的结点称为孤立结点。全由孤立结点构成的图称为零图。关联于同一结点的一条边称为自回路，自回路的方向不定。n在有向图中，两结点间（包括结点自身间）若同始点和同终点的边多于一条，则这几条边称为平行边。在无向图中，两结点间（包括结点自身间）若多于一条边，则这几条边称为平行边。两结点

5、a和b间互相平行的边的条数称为边a,b的重数。仅有一条边时，重数为1，无边时重数为0。n含有平行边的图称为多重图。非多重图称为线图。无自回路的线图称为简单图。多重图要用三元组形式表示，线图则可以不用。 图 论图基本概念图基本概念顶点的度数顶点的度数图的同构图的同构图的运算图的运算子图与补图子图与补图图的基本概念图的基本概念高级语言程序设计SEISEI程序设计基础 2007春季6离散数学 2007秋季6n赋权图G是一个三重组或四重组，其中V是一个非空的结点集合， E是边的集合，f是定义在V上的函数，g是定义在E上的函数。如左图所示：V=a,b,c,E=e1,e2,e3,f(a)=3, f(b)=

6、4, f(c)=5, g(e1)=6, g(e2)=7, g(e3)=8。3a5c4be16e38e27 图 论图基本概念图基本概念顶点的度数顶点的度数图的同构图的同构图的运算图的运算子图与补图子图与补图图的基本概念图的基本概念高级语言程序设计SEISEI程序设计基础 2007春季7离散数学 2007秋季7n在有向图中，对于任何结点v，以v为始点的边的条数称为结点v的引出次数（或出度），记为deg+(v);以v为终点的边的条数称为结点v的引入次数（或入度），记为deg-(v)；结点v的引出次数和引入次数之和称为结点v的次数（或度数），记为deg(v)。n在无向图中，结点v的次数是与结点v相关联

7、的边的条数，也记为deg(v)。孤立结点的次数为0。以后把具有n个结点和m条边的图简称为(n,m)图。n各结点的次数均相同的图 称为正则图，各结点的次 数均为k时，称为k正则 图。右图为彼得森图。 图 论顶点的度数顶点的度数图基本概念图基本概念顶点的度数顶点的度数图的同构图的同构图的运算图的运算子图与补图子图与补图高级语言程序设计SEISEI程序设计基础 2007春季8离散数学 2007秋季8n设G是一个(n,m)图，它的结点集合为V=v1,v2,.,vn，则nimvi12)deg(mvivinini2)(deg)(deg11在有向图中，可以写成 图 论图基本概念图基本概念顶点的度数顶点的度数

8、图的同构图的同构图的运算图的运算子图与补图子图与补图顶点的度数顶点的度数高级语言程序设计SEISEI程序设计基础 2007春季9离散数学 2007秋季9n在图中，次数为奇数的结点必有偶数个。证明：设V1和V2分别是图G中奇数次数和偶数次数结点的集合，则有|2)deg()deg()deg(21EvvvVvVvVv是偶数。是偶数，故所以是偶数，而是偶数之和，必为偶数由于| 1|)deg(|2)deg(12VvEvVvVv 图 论图基本概念图基本概念顶点的度数顶点的度数图的同构图的同构图的运算图的运算子图与补图子图与补图顶点的度数顶点的度数高级语言程序设计SEISEI程序设计基础 2007春季10离

9、散数学 2007秋季10n设G=和G=是两个图，若存在从V到V的双射函数f，使对任意a,bV，a,bE，当且仅当f(a),f(b)E，并且a,b和f(a),f(b)有相同的重数，则称G和G是同构的。两个图的各结点之间，如果存在一一对应关系，而且这种对应关系保持了各结点间的邻接关系（有向图还保持边的方向）和边的重数，则这两个图是同构的。即同构图除了顶点和边的名称不同外，实际上就是一个图形。 图 论图基本概念图基本概念顶点的度数顶点的度数图的同构图的同构图的运算图的运算子图与补图子图与补图图的同构图的同构高级语言程序设计SEISEI程序设计基础 2007春季11离散数学 2007秋季114321a

10、cdb同构 图 论图基本概念图基本概念顶点的度数顶点的度数图的同构图的同构图的运算图的运算子图与补图子图与补图图的同构图的同构高级语言程序设计SEISEI程序设计基础 2007春季12离散数学 2007秋季12632154321654K3,3图 图 论图的同构图的同构图基本概念图基本概念顶点的度数顶点的度数图的同构图的同构图的运算图的运算子图与补图子图与补图高级语言程序设计SEISEI程序设计基础 2007春季13离散数学 2007秋季13n两图同构的必要条件：n结点数相同n边数相同n度数相同的结点数相等不同构 图 论图的同构图的同构图基本概念图基本概念顶点的度数顶点的度数图的同构图的同构图的

11、运算图的运算子图与补图子图与补图高级语言程序设计SEISEI程序设计基础 2007春季14离散数学 2007秋季14设图G1=和图G2=。nG1与G2的并：定义为图G3=，其中V3V1V2，E3E1E2，记为G3G1G2。nG1与G2的交：定义为图G3=，其中V3V1V2，E3E1E2，记为G3G1G2。nG1与G2的差：定义为图G3=，其中E3E1E2， V3(V1V2)E3中边所关联的顶点，记为G3G1G2。 图 论图基本概念图基本概念顶点的度数顶点的度数图的同构图的同构图的运算图的运算子图与补图子图与补图图的运算图的运算高级语言程序设计SEISEI程序设计基础 2007春季15离散数学

12、2007秋季15nG1与G2的环和：定义为图G3=， G3(G1G2)(G1G2)，记为G3G1G2。此外还有以下两种操作：n 删去图G的一条边；n 删去图G的一个结点v：即删去结点v和与v关联的 所有边。 图 论图基本概念图基本概念顶点的度数顶点的度数图的同构图的同构图的运算图的运算子图与补图子图与补图图的运算图的运算高级语言程序设计SEISEI程序设计基础 2007春季16离散数学 2007秋季16acbdG2e4e1e5acbG1e2e1e3acbdG1G2e2e4e1e3e5 图 论图基本概念图基本概念顶点的度数顶点的度数图的同构图的同构图的运算图的运算子图与补图子图与补图图的运算图的

13、运算高级语言程序设计SEISEI程序设计基础 2007春季17离散数学 2007秋季17acbG1G2e1acbdG2e4e1e5acbG1e2e1e3acbG1G2e2e3 图 论图基本概念图基本概念顶点的度数顶点的度数图的同构图的同构图的运算图的运算子图与补图子图与补图图的运算图的运算高级语言程序设计SEISEI程序设计基础 2007春季18离散数学 2007秋季18acbdG1G2e2e4e1e3e5acbG1G2e1acbdG1G2e2e4e3e5 图 论图基本概念图基本概念顶点的度数顶点的度数图的同构图的同构图的运算图的运算子图与补图子图与补图图的运算图的运算高级语言程序设计SEIS

14、EI程序设计基础 2007春季19离散数学 2007秋季19acbG1e2e1e3acb删去边e2e1e3ab删去结点ce1 图 论图基本概念图基本概念顶点的度数顶点的度数图的同构图的同构图的运算图的运算子图与补图子图与补图图的运算图的运算高级语言程序设计SEISEI程序设计基础 2007春季20离散数学 2007秋季20n设图G=和图G=。n如果V V和E E，则称G是G的子图。如果V V和E E而GG，则称G是G的真子图。n如果VV和E E，则称G为G的生成子图。n以E为边集，以E中边关联的顶点的全体为顶点集，并保持它们的关联关系，得到G，则称G为由边集E导出的子图。n以V为顶点集，以V中

15、关联的边的全体为边集，并保持它们的关联关系，得到G，此时称G为由结点集V导出的子图。 图 论图基本概念图基本概念顶点的度数顶点的度数图的同构图的同构图的运算图的运算子图与补图子图与补图图的子图与补图图的子图与补图高级语言程序设计SEISEI程序设计基础 2007春季21离散数学 2007秋季21真子图abeacbde生成子图acbde图Gabde由V=a,b,d,e导出的子图 图 论图的子图与补图图的子图与补图由E=a,b,b,c,c,d导出的子图acbd图基本概念图基本概念顶点的度数顶点的度数图的同构图的同构图的运算图的运算子图与补图子图与补图高级语言程序设计SEISEI程序设计基础 2007春季22离散数学 2007秋季22n在n个结点的有向图G中，如果EVV，则称G为有向完全图；在n个结点的无向图G中，如果任何两个不同结点间都恰好有一条边，则称G为无向完全图，记为Kn。n设线图G有n个顶点，线图H也有同样的顶点，而E是由n个顶点的完全图的边删去E所得，则图H称为图G的补图，记为。，显然GGGH 图 论图的子图与补图图的子图与补图