图论简介完整版课件.ppt

图论简介图论是数学的一个分支,以图为研究对象.这种图由若干给定的点和连接两点的线构成,借以描述某些事物之间的关系.用点代表事物,用连接两点的线表示两个事物之间具有特定关系.图论起源于18世纪,追朔到1736年瑞士数学家L.Euler出版第一本图论著作,提出和解决著名Konigsberg七桥问题.从那时以来,图论不仅在许多领域,如计算机科学,运筹学,心理学等方面得到了广泛的应用,而且学科本身也获得长足发展,形成了拟阵理论,超图理论,代数图论,拓扑图论等新分支.图的定义与记号图G是一个二重组:G=?V,E?,其中V是非空有限集合,它的元素称为结点或顶点,E也是(可空)有限集合,它的元素称为边.图G的边e是一个结点二重组:?a,b?,a,b?V,e可以是有序的,称为有向边,简称为弧,a称为弧e的始点,b称为e的终点;e也可以是无序的,称为无向边.e=?a,b?时,称e与a,b关联,或a,b与e关联,或a与b相邻接;关联于同一顶点的一条边称为自回路或环.每条边都是无向边的图称为无向图;每条边都是有向边的图称为有向图;我们仅讨论无向图和有向图.图的定义与记号续在无向图中两结点间(包括结点自身)若多于一条边，则称这几条边为平行边.在有向图中若同始点和同终点的边多于一条,则称这几条边为平行边,平行边的条数称为该边的重数.含平行边的图称为多重图,非多重图称为线图.无自回路的线图称为简单图.常用一个图形来表示图称为图的图示deg+(1)=2,deg-(1)=0,deg(1)=deg(2)=…deg+(2)=deg-(2)=1,…=deg(6)=3.deg(1)=…=deg(4)=2.结点的度(次数)有向图中,以结点v为始点的边数称为v的出度,记为deg+(v);以结点v为终点的边数称为v的入度,记为deg-(v);它们的和:deg(v)=deg+(v)+deg-(v)称为v的度.无向图中,与结点v相关联的边数称为v的度,记为deg(v).各结点的度都相等的图称为正则图,或k-正则图,其中k为结点度的公共值.(注:可以只考虑正则的无向图,然后再定义其底图的无向图是正则图的有向图为正则有向图.)例子见上一张幻灯片.关于有n结点m边的(n,m)图度的定理定理1-1令v1,…,vn为图的所有结点,则?i=1ndeg(vi)=2m.(1)定理1-2任何图中度为奇数的结点必为偶数个.图的同构定义:对给定两个图G=?V,E?,G?=?V?,E??,若存在双射f:V?V?使对任意a,b?V,(a,b)?E?(f(a),f(b))?E?,并且(a,b)与(f(a),f(b))有相同重数,则称G与G?同构,记为G?G?.注:①两图同构是相互的:G?G??G??G.②两图同构时不仅结点之间要有一一对应关系,而且要求这种对应关系保持结点间的邻接关系.对有向图同构还要求保持边的方向.③寻求判断图同构的简单有效方法仍是图论待解决的重要问题.同构图举例G?G’H?H’1?a,2?b,3?c,1?a,2?b,3?c,4?d4?d,5?e,6?f非同构图举例存在结点数及每个结点对应度都相等的两个图仍然不同构的情况.;如下:(注意:两个4度点或邻接或不相邻接)子图的概念定义:给定两个无(有)向图G=?V,E?,G?=?V?,E??.若V??V和E??E,则称G?是G的子图;若V??V,E??E,且G??G,则称G?是G的真子图;若V?=V和E??E,则称G?是G的生成子图;完全图与补图E=V?V的有向图G=?V,E?称为有向完全图.n个结点的无向简单图如果任二不同结点都相邻时,称为n结点无向完全图,记为Kn.n结点线图G=?V,E?与H=?V,E’?称互为补图(记为G=H’或H=G’),如果E’是n结点完全图的边集与E的差集.下列二无向图G与H互为补图.路径与回路图G=?V,E?的点边交替序列P=v0e1v1e2v2???envn称为G的一条从v0到vn的长为n的路径(或途径）,其中,ei=(vi-1,vi)?E,i=1,…,n(对有向图要求vi-1,vi为ei的始,终点).P称为简单路径,如果e1,???,en两两不同;P称为基本路径(链),如果v0,v1,???,vn两两不同(易见链必为简单路径);P称为回路,如果v0=vn;回路P称为简单(基本)