图论图基本概念ppt课件.ppt

《图论图基本概念ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、上次课主要内容一、图的概念1、图的定义定义1一个无向图是一个有序的二元组，记作G，其中(1)V≠ø称为顶点集，其元素称为顶点或结点．(2)E称为边集，它是无序积V＆V的多重子集，其元素称为无向边，简称为边．无向图G=V＝｛v1,v2,v3｝边集合E＝｛(v1,v2),(v3,v2)…｝园括号表示无向边定义2一个有向图是一个有序的二元组，记作D，其中(1)V≠ø称为顶点集，其元素称为顶点或结点．(2)E为边集，它是笛卡儿积V&V的多重子集，其元素称为有向边，简称边(弧)．有向图D=V＝｛v1,v2,v3｝

2、边集合E＝｛,…｝尖括号表示有向边边也可以用字母ek表示有向图的基图—将其有向边的方向去掉所得的无向图2、节点与边的关联性设G＝为无向图，ek=(vi，vj)∈E，则称vj，vj为ek的端点，ek与vi、vj是彼此相关联的．不与任何边关联的结点称为孤立点（包括有向图)3、邻接(1)边的相邻：ek，el∈E．若ek与el至少有一个公共端点，则称ek与el是相邻的(2)顶点的相邻：若∃et∈E，使得et=，并称vi邻接到vj，vj邻接于vi两个结点为一条边的端点，则称两个结点互为邻接点4、平行边

3、：在无向图中，关联一对顶点的无向边如果多于1条，则称这些边为平行边，平行边的条数称为重数．在有向图中，关联一对顶点的有向边如果多于1条，并且这些边的始点与终点相同(也就是它们的方向相同)，则称这些边为平行边．5、多重图和简单图：含平行边的图称为多重图既不含平行边也不含环的图称为简单图．二、结点的度1）定义4设G＝为无向图，∀v∈V，称v作为边的端点次数之和为v的度数，简记为度记作dG(v)，简记为d(v)即为：结点v所关联的边的总条数关于有向图D＝有：∀v∈V，称v作为边的始点的次数之和为v的出度，记作d+(v)，称v作为

4、边的终点的次数之和为v的入度，记作d-(v)，称d+(v)+d-(v)为v的度数，记作d(v)2）度为偶数(奇数)的顶点称为偶度(奇度)顶点3、握手定理（欧拉）1)定理1设G＝为任意无向图,V＝{v1，v2，…，vn},｜E｜=m，则∑d(vi)＝2m(所有结点的度数值和为边数的2倍)2)定理2设D＝为任意有向图,V＝{v1，v2，…，vn},

5、E

6、=m，则∑d+(vi)＝∑d-(vi)=m．且∑d(vi)＝2m3)推论任何图(无向的或有向的)中，奇度顶点的个数是偶数4)结点的度数序列(1)设G＝为一个n阶无向图

7、，V＝{v1，v2，…，vn}称d(v1)，d(v2)，…，d(vn)为G的度数列条件：奇度数的结点个数应该是偶数个（2）序列的可图化：d=(d1,d2,…dn)对一个整数序列d,若存在以n个顶点的n阶无向图G，有d(vi)=di称该序列是可图化的（3）定理设非负整数列d＝(d1，d2，…，dn)，则d是可图化的当且仅当∑di=0(mod2)(序列之和必须是偶数)（4）由于简单图中没有平行边及环结论：n个结点的简单图中结点的最大度数（△（G)）应小于等于n-1每个结点至多与其他n-1个结点相邻三、图的同构定义设G1＝，G2=

8、2，E2>为两个无向图(两个有向图)，若存在双射函数f：V1→V2顶点的一一对应对于∀vi，vj∈V1，(vi，vj)∈E1(∈E1)当且仅当(f(vi)，f(vj))∈E2(∈E2)，边的对应并且(vi，vj)()与(f(vi),f(vj))()的重数相同，则称G1与G2是同构的，记作Gl≅G2注：1)互为同构的两个图（必要条件）有相同样的阶数（结点）和同样数量的边数及顶点的度数序列2)图之间的同构关系可看成全体图集合上的二元关系同构的图为一个等价类，在同构的意

9、义之下都可以看成是一个图。四、特殊图－完全图与正则图1）完全图定义设G为n阶无向简单图，若G中每个顶点均与其余的n—1个顶点相邻，则称G为n阶无向完全图，简称n阶完全图，记作Kn(n≥1)．设D为n阶有向简单图，若D中每个顶点都邻接到其余的n—1个顶点，又邻接于其余的n—1个顶点，则称D是n阶有向完全图．可画图表示（无向图K3,K4,K5、有向图3阶）2)完全图的性质：n阶无向完全图G的边数与结点的关系m=n(n-1)/2n阶有向完全图G的边数与结点的关系m=n(n-1)3)正则图定义设G为n阶无向简单图，若∀v∈V(G)，均有d(v)＝k，

10、则称G为是k-正则图k-正则图的边数与结点个数的关系：m=kn/2可画3－正则图和4－正则图五、子图、生成子图、导出子图1、定义设G＝，G‘＝