4图论-图基本概念9-21.

上次课主要内容一、图的概念1、图的定义定义1一个无向图是一个有序的二元组V，E，记作G，其中(1)V≠ø称为顶点集，其元素称为顶点或结点．(2)E称为边集，它是无序积V＆V的多重子集，其元素称为无向边，简称为边．无向图G=V，EV＝｛v1,v2,v3｝边集合E＝｛(v1,v2),(v3,v2)…｝园括号表示无向边定义2一个有向图是一个有序的二元组V，E，记作D，其中(1)V≠ø称为顶点集，其元素称为顶点或结点．(2)E为边集，它是笛卡儿积V&V的多重子集，其元素称为有向边，简称边(弧)．有向图D=V，EV＝｛v1,v2,v3｝边集合E＝｛v1,v2,v1,v2…｝尖括号表示有向边边也可以用字母ek表示有向图的基图—将其有向边的方向去掉所得的无向图2、节点与边的关联性设G＝V，E为无向图，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，并称vi邻接到vj，vj邻接于vi两个结点为一条边的端点，则称两个结点互为邻接点4、平行边：在无向图中，关联一对顶点的无向边如果多于1条，则称这些边为平行边，平行边的条数称为重数．在有向图中，关联一对顶点的有向边如果多于1条，并且这些边的始点与终点相同(也就是它们的方向相同)，则称这些边为平行边．5、多重图和简单图：含平行边的图称为多重图既不含平行边也不含环的图称为简单图．二、结点的度1）定义4设G＝V，E为无向图，∀v∈V，称v作为边的端点次数之和为v的度数，简记为度记作dG(v)，简记为d(v)即为：结点v所关联的边的总条数关于有向图D＝V，E有：∀v∈V，称v作为边的始点的次数之和为v的出度，记作d+(v)，称v作为边的终点的次数之和为v的入度，记作d-(v)，称d+(v)+d-(v)为v的度数，记作d(v)2）度为偶数(奇数)的顶点称为偶度(奇度)顶点3、握手定理（欧拉）1)定理1设G＝V,E为任意无向图,V＝{v1，v2，…，vn},｜E｜=m，则∑d(vi)＝2m(所有结点的度数值和为边数的2倍)2)定理2设D＝V,E为任意有向图,V＝{v1，v2，…，vn},|E|=m，则∑d+(vi)＝∑d-(vi)=m．且∑d(vi)＝2m3)推论任何图(无向的或有向的)中，奇度顶点的个数是偶数4)结点的度数序列(1)设G＝V，E为一个n阶无向图，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＝Vl，E1，G2=V2，E2为两个无向图(两个有向图)，若存在双射函数f：V1→V2顶点的一一对应对于∀vi，vj∈V1，(vi，vj)∈E1(vi，vj∈E1)当且仅当(f(vi)，f(vj))∈E2(f(vi)，f(vj)∈E2)，边的对应并且(vi，vj)(vi,vj)与(f(vi),f(vj))(f(vi),f(vj))的重数相同，则称G1与G2是同构的，记作Gl≅G2注：1)互为同构的两个图（必要条件）有相同样的阶数（结点）和同样数量的边数及顶点的度数序列2)图之间的同构关系可看成全体图集合上的二元关系同构的图为一个等价类，在同构的意义之下都可以看成是一个图。四、特殊图－完全图与正则图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，则称G为是k-正则图k-正则图的边数与结点个数的关系：m=kn/2可画3－正则图和4－正则图五、子图、生成子图、导出子图1、定义设G＝V，E，G‘＝V’，E’为两个图(同为无向图或同为有向图)若V’⊆V且E’⊆E，则称G‘是G的子图，G为G‘的母图，记作G’⊆G，又若V‘⊂V或E’⊂E则称G‘为G的真子图若V’＝V(且E’⊆E)则称G‘为G的生成子图2、设G＝V，E为图，V1⊂V且V1≠ø，称以V1为顶点集，以G中两个端点都在V1中的边组成边集E1的图为G的V1导出的子图，记作G[V1]．可画图表示G及G［V1］（由部分结点导出的子图）又设E1⊂E且E1≠ø，称以E1为边集，以E1中边关联的顶点为顶点集V1的图为G的E1导出的子图，记作G[E1]．（由部分边导出的子图）3、补图1）定义设G＝V，E为n阶无向简单图，图G＝V，E以V为顶点集以E={(u,v):u∈V∧v∈V∧u≠v∧(u,v)¢E}为边的图称为G的补图，记作G2）自补图：若图G≌G(同构)则称G为自补图§14.2通路、回路一、通路与回路1、通路1）定义：给定有向图D中的任何一个边序列L，如果其中的任何一条边的终点，都是继之出现的边(如果存在的话)的始点，则称这样的边的序列是图G的通路。若序列中首尾结点相同，则称L为回路2）定义：有向图D中边序列中的各条边全都是互不相同的通路，称为简单通路3）定义：有向图D中，序列中的每一个结点仅出现一次的通路，称为初级通路若序列中首尾结点相同，则称通路为初级回路或圈4）定义：序列中边的条数称为它的长度2、简单通路和初级通路的关系有向图中的每一条初级通路，也都必定是简单通路。反之不成立回路也可分为简单回路和初级回路。3、通路的表示：可仅用通路中的边序列表示：e1e2…ek也可仅用通路中所经过的结点的序列表示：v1v2v3…vk4、性质：1）定理在n阶图D中，若从顶点vi到vj(vi≠vj)存在通路，则从vi到vj存在长度小于或等于(n—1)的通路若大于n-1，则存在相同节点（有回路），将回路删去可得2）在n阶图D中，若从顶点vi到vj存在通路，则vi到vj一定存在长度小于或等于n—1的初级通路(路径)3）定理在一个n阶图D中，若存在vi到自身的回路，则一定存在vi到自身长度小于或等于n的回路．4）在一个n阶图D中，若存在vi到自身的简单回路，则一定存在长度小于或等于n的初级回路．以上概念均可用在无向图G中§14.3图的连通性一、无向图的连通性1、结点的连通：设无向图G＝V，E，∀u,v∈V，若u，v之间存在通路，则称u,v是连通的，记作u～v，∀u∈V，规定u～u2、结点的连通关系是等价关系若定义：～＝{u，v┃u，v∈V且u与v之间有通路}此关系是自反，对称的，传递的，因而～是V上的等价关系3、无向图的连通图定义14．13若无向图G是平凡图或G中任何两个顶点都是连通的，则称G为连通图，否则称G为非连通图或分离图（各子图为连通分支）4、结点之间的距离1）定义：设u，v为无向图G中任意两个顶点若u～v，称u，v之间长度最短的通路为u，v之间的短程线短程线的长度称为u，v之间的距离，记作d(u，v)当u，v不连通时，规定d(u，v)＝∞．2）无向图结点的距离有以下性质：1．d(u，v)≥0，u=u时，等号成立．2．具有对称性：d(u，v)＝d(v，u)．3．满足三角不等式：∀u,v，w∈V(G)，则d(u，v)+d(v，w)≥d(u，w)二、有向图的连通性1、结点的可达性定义：设D＝V，E为一个有向图．∀vi,vj∈V，若从vi到vj存在通路则称vi可达vj,记作vi→vj。规定vi总是可达自身的，即vi→vi．2、结点的相互可达若vi→vj且vj→vi则称vi与vj是相互可达的，记作:vi↔vj规定vi↔vi．3、结点的可达关系为V上的二元关系，但不是等价关系（不满足对称性）。相互可达关系为V上的二元关系，且是V上的等价关系．有向图中顶点之间的可达关系既无对称性，也无反对称性4、有向图中结点的距离定义：设D＝V，E为有向图∀vi,vj∈V，若vi→vj，称vi到vi长度最短的通路为vi到vj的短程线短程线的长度为vi到vj的距离，记作dvi，vj注：该定义与无向图中顶点vi与vj之间的距离d(vi，vj)的区别：无对称性一般地：dvi，vj≠dvj，vi（可能dvi，vj不存在）5、弱连通图、单向连通图和强连通图定义1设D＝{V，E)为一个有向图．若D的作为无向图是连通图，则称D是弱连通图，简称为连通图．定义2设D＝{V，E)为一个有向图，若∀vi,vj∈V,vi→vj与vj→vi至少成立其一，则称D是单向连通图．若∀vi,vj∈V，均有vi↔vj，则称D是强连通图注：三种图的关系：强连通图一定是单向连通图，反之不成立单向连通图一定是弱连通图．反之不成立6、有关强连通图与单向连通图的判定（1）定理：设有向图D＝V，E，V＝{v1，v2，…，vn}．D是强连通图当且仅当D中存在经过每个顶点至少一次的回路．(2)定理设D是n阶有向图D是单向连通图当且仅当D中存在经过每个顶点至少一次的通路．例2．设有向图D是单向连通图，但不是强连通图，问在D中至少加几条边所得图D’就能成为强连通图?§14.4图的矩阵表示一、图的矩阵表示用矩阵表示图之前，必须将图的顶点或边标定成顺序，使其成为标定图1、无向图的关联矩阵1）定义14．24设无向图G＝V，E，V＝{v1,v2,…，vn}。E={e1,e2,e3，…em}令mij为顶点vi与边ej的关联次数，则称(mij)nxm为G的关联矩阵，记作M(G)．2）关联矩阵的性质:关联矩阵是n行（结点数）m列（边数）的矩阵(1）M(G)每列元素之和均为2，这正说明每条边关联两个顶点(环所关联的两个端点重合)．∑mij=2(j=1，2，…，m)(2）M(G)第i行元素之和为结点vi的度数，i＝1，2，…n(3)所有行的和（即矩阵所有元素之和）等于边数的2倍（该例10＝边数5的2倍）。∑d(vi)＝∑∑mij=∑2＝2m，这个结果正是握手定理的内容（即各顶点的度数之和等于边数的2倍）．（4）第j列与第k列相同，当且仅当边ej与ek是平行边．(5)某行i的和为0（即∑mij=0）,当且仅当vi是孤立点．2、有向图的关联矩阵定义：设有向图D＝V，E中无环，V＝{v1，v2，…，vn}。E＝{el，e2,…，em}，令1vi为边ej的起点mij=0vi为边ej不关联－1vi为边ej的终点则称(mij)nxm，为D的关联矩阵，记作M(D）2)有向图关联矩阵的性质（1）∑mij=0，j＝1，2，…，m，从而∑∑mij=0，这说明M(D)中所有元素之和为0．(2)M(D)中，负1的个数等于正1的个数，都等于边数m，这正是有向图握手定理的内容（入度之和等于出度之和）．（3）第i行中，正1的个数等于d+(vi)（结点的入度），负1的个数等于d-(vi)（结点的出度）．（4）平行边所对应的列相同3、有向图的邻接矩阵1）定义：设有向图D＝V，E，V＝{v1，v2，…，vn}，E＝{e1，e2，…，em}令：aij为顶点vi邻接到顶点vj边的条数称(aij))nxn为D的邻接矩阵，记作A(D)，或简记为A．2）邻接矩阵的性质（1）每列元素之和为结点的入度，即∑aij＝d+(vi)，i＝1，2，…