第1讲 图论概述.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,图与网络技术,四川大学工商管理学院,冯 结 制,1,图论与应用,教师联系方式,冯结 电话:,18980765270,，,85436007,（,H）,电子邮箱,：,fengjieasdfg,本课程学习要求,1.必备三物：,教材，作业本,课堂笔记.,2.成绩评定：,平时成绩占20%,期中测验占20%,期末考试占60%,引例：七桥问题,一笔画问题：,要求笔不离纸，边不重复,哥尼斯堡七桥问题,一个图是由两个集合组成：,顶点集,V,（,非空有限集）,边集,E,（,有限集,E）,每条边对应由两个顶点组成的顶点对。若顶点对是无序的，则称为,无向图,；若顶点对是有序的，则称为,有向图,。,若图用,G,表示，则它的点集和边集就分别记为,V(G)，E(G),该图可以记为,G=(V(G)，E(G)。,在不致引起混淆的情况下可简记为,G=(V，E)。,什么是图？,常用,u,v,w,或,v,1,v,2,v,3,来标记图的顶点，用,a,b,c,或,e,1,e,2,e,3,标记图的边。每条边用一条连接该边端点的线表示。画图形时，表示顶点的点的位置和表示边的线的相对位置是无关紧要的，因为一个图的图形仅需画出它的顶点与边之间的关系，所以一个,图的图形表示不是唯一的,。,例1：,V=v,1,v,2,v,3,v,4,v,5,v,6,和,E=e,1,e,2,e,3,e,4,e,5,其中,e,1,=v,1,v,2,e,2,=v,1,v,4,e,3,=v,5,v,6,e,4,=v,1,v,2,e,5,=v,5,v,5,，,则,G=(V,E),的图形表示为：,图1,若一条边的端点为同一顶点，则称此边为,环,。（如图1 中的,e,5,）,若,E,中两条或两条以上不同边具有相同端点，则称这些边为,重复边,（,e,1,和,e,4,）,无环无重边的图称为,简单图,，只有一个顶点的图称为平凡图，其余为非平凡图。无边的图称为,空图,。,一条边的端点称为与此边,关联,的顶点，反之亦然，与同一条边关联的而个顶点称为,相邻,的，与同一顶点关联的两条边也称为相邻的,在图,l,中，,e,1,与,v,1,，v,2,关联，,v,1,与,v,4,相邻，,e,1,与,e,2,相邻。,与顶点,v,i,关联的边的数目称为,v,i,的,度（或次）,，记为,d(v,i,)，,度为0 的顶点称为,孤立点,，度为1的点称为,悬挂点,，与悬挂点相联的边称为,悬挂边,。与,v,i,关联的环计算时作为2 条边，图,G,的顶点数和边数分别用,(G),和,(G),表示,当讨论的图只有一个时，常省去括号中表示图的符号，而只用,V，E，,等记法。,在图1 中，,=6，=5，,d(v,1,)=3，d(v,2,)=2，d(v,3,)=0，d(v,4,)=1，d(v,5,)=3d(v,6,)=1，v,3,为3 孤立点，,v,4,v,6,为悬挂点，,e,2,e,4,为悬挂边,图的本质？,图最为本质的内容是一个,二元关系,.,相关基本概念：,有序对，有序积,AB,（,笛卡尔积），,无序对，无序积,A&B,，,A,到,B,的二元关系，,A,和,B,的二元关系,图，是某顶点集合,V,和,V,上的一个二元关系。,只要一个系统若具有二元关系便可以考虑采用图来建立模型解决实际问题。,几个有趣问题,1.一次集会上面许多朋友相互握手，那么握手次数为奇数的人的数目一定是偶数。,2.有2人以上的人群中，总有两人在该人群内恰好有相同的朋友数。,3.证明：任意6个人中，至少有3人相互认识或者至少有3人相互全都不认识。,定理 设,G=(V，E),是一个图，则,度为奇数的点称为,奇点,，度为偶数的点称为,偶点,。,推论：在任何图中，,奇点的个数必为偶数,。,证明：设,V,1,和,V,2,分别是偶点集和奇点集，由定理 可得下式：,由于2,是偶数，也是偶数，所以 必然是偶数。,由于 中每一项都是奇数，所以它的项数必须是偶数，,即奇点数必为偶数。,节目排序问题,要求,（1）每个演员不连续参加2个节目的演出；,（2）,A,和,H,必须安排在首尾两个节目。,演员,节目,1,2,3,4,5,6,7,8,9,10,A,B,C,D,E,F,G,H,图的作用,图是解决问题的一种工具，是一种重要的数学模型。,图往往能够使问题得到简化，便于处理。,图具有直观性和艺术性。,图论与数学（拓扑学，代数学，组合数学）关系密切，如今，它的许多方法在物理学，化学，通讯科学，计算机技术，运筹学，经济学，生物遗传学，心理学，社会学，人类学，语言学等诸多学科的某些领域都有应用。,图的分类,有向图，无向图,平凡图，非平凡图，空图,连通图，不连通图,平面图，非平面图,赋权图，无权图,一些特殊类型的图,完全图,：任意一对不同顶都有一条边相连的简单图。,n,个顶点的完全图记为,K,n,二部图（偶图）,：图,G=(V，E),的顶点集,V,如能分为两个非空子集,X,和,Y，,使得,E,中每条边都是一个端点在,X,中另一个端点在,Y,中，则称,G,为二部图。若,G,是简单二部图，且,X,中每一顶点与,Y,中每一顶点相连，|,X|=m,|Y|=n（,符号|,A|,表示集合,A,中元素的个数），则称,G,为,完全二部图（完全偶图）,，记为,K,m,n,。,v,2,v,3,v,4,v,5,v,2,v,3,v,4,v,5,v,1,v,1,完全图,K,5,(完全)二部图,K,2,3,k-,部图,：图,G=(V,E),的顶点集,V,如能分为,k,个非空子集,V,1,V,2,V,k,使得,E,中每一条边都有一个端点在某一,V,i,中，另一端 点在某一,V,j,中，,ij,则称,G,为,k-,部图。,r-,正则图,：称图,G,是,r-,正则的，如果对所有,vV,都有,d(v)=r。,图的若干重要定义,途径,：,G,的一条途径是一个有限非空的,顶点和边的交错序列,W=v,0,e,1,v,1,e,2,v,2,e,k,v,k,，,使得对任何,i,e,i,的端点是,v,i-1,和,v,i,，,并称,W,是从,v,0,到,v,k,的一条途径，或一条(,v,0,v,k,),途径。,v,0,和,v,k,分别称为,W,的起点和终点，通称为端点，其余的顶点为它的内点，整数,k,称为,W,的长。,注意,：,在一条途径中，顶点和边可以重复出现,。若,W,的起点与终点是相同的，则称,W,为闭途径，否则为开途径。,在表示途径时亦可用边的序列e,1,e,2,e,k,表示，特别在简单图中，由于不存在重边与环，途径可由顶点序列,v,1,v,2,v,k,表示而不至引起混乱。,v,1,e,1,v,2,e,2,v,3,e,6,v,6,e,5,v,2,e,1,v,1,是闭途径,v,1,e,1,v,2,e,2,v,3,e,6,v,6,e,8,v,5,e,7,v,4,是开途径,链,：一条途径若其所有,边互不相同,则称为链,路,：一条链若其,所有顶点互不相同,，则称为路，记为,P。,一条路所含边的数目称为此路的长，。,圈,：起点终点相同的链，称为圈，记为,C。,一个圈所含边的数目称为此圈的长。,回路,：起点终点相同的路，称为回路。,v,1,e,1v,2,e,2,v,3,为一条路,v,1,e,1,v,2,e,9,v,5,e,7,v,4,e,3,v,1,为一个圈,连通图,：若图,G,中任意两点间都存在一条路,则称,G,为连通的。,子图与生成子图（部分图）,子图,：称图,H,是,G,的,子图,（记为,HG），,如果,V(H)V(G),E(H)E(G),且,E(H),中的边的端点都是,V(H),中的顶点。若,HG，,但,HG，,则称,H,为,G,的,真子图,。,生成子图,：若,H,是,G,的子图，且,V(H)=V(G),则称,H,是,G,的,生成 子图,。在下图中，,a,是图,G,的子图，,b,是图,G,的生成子图。,基础简单图,：,从图,G,中删去所有的环，并使每一对相邻顶点只留下一条边，这样得到的,G,的简单生成子图称为,G,的基础简单图。,导出子图,：设 是,V,的一个非空子集，以 为顶点集，以两个端点均在 中的边的全体为边集所组成的子图称为,G,的导出子图，记为,G 。,导出子图,GVV,记为,GV；,它是从,G,中删去,V,中的顶点以及与这些项点相关联的边所得到的子图。若,V=v，,则把,Gv,简记为,Gv。,设,E,是,E,的非空子集。以,E,为边集，以,E,中边的端点全体为顶点集所组成的子图称为由,E,导出的子图，记为,G E。,边集为,E E,的,G,的生成子图简记为,GE，,它是从,G,中删去,E,中的边所得到的子图；类似地在,G,上添加边集,E（,其中,EE=),所得图记为,G+E，,若,E=e，,则用,G+e,和,G-e,来代替,G+e,和,G-e。,谢 谢！,再 见！,