资源描述：
《《图论初步》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、图论初步第六讲 图论初步§6.1引言图论是运筹学的一个经典和重要的分支，它起源于欧拉（Euler）对七桥问题的抽象和论证。1936年，匈牙利数学家柯尼希（König）出版了图论的第一部专著《有限图与无限图理论》，竖立了图论发展的第一座里程碑。此后，图论进入发展与突破的快车道，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。近几十年来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、生物遗传学、心理学、经济学、社会学等学科中。图论中所谓的“图”是指某类具体事物和这些事物之间的联
2、系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。引例6.1.1最短路问题（SPP－shortestpathproblem）一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。引例6.1.2中国邮递员问题（CPP－chinesepostmanpr
3、oblem）一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？由于这一问题是我国管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题。引例6.1.3旅行商问题（TSP－travelingsalesmanproblem）一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这一问题的研究历史十分悠久，通常称之为旅行商问题。引例6.1.4指派问题（assignmentproblem）一家公司经理准备安排名员工去完成项任务，每人一项。由
4、于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以使总回报最大？引例6.1.5运输问题（transportationproblem）某种原材料有个产地，现在需要将原材料从产地运往个使用这些原材料的工厂。假定个产地的产量和家工厂的需要量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低？§6.2图的基本概念§6.2.1图的定义定义6.2.1称数学结构G={V(G),E(G),G}为一个图，其中V(G)={v1,v2,…,vn}称为图G的顶点集（vertexset）或节点集（nodeset），V(G)中的每一个元素
5、vi（i=1,2,…,n）称为该图的一个顶点（vertex）或节点（node）；E(G)={e1,e2,…,em}称为图G的边集（edgeset），E(G)中的每一个元素ek（即V(G)中某两个元素vi,vj的无序对）记为ek=(vi,vj)或ek=vivj=ek=vjvi（k=1,2,…,m），被称为该图的一条从vi到vj的边（edge）；G是从E(G)到V(G)V(G)的一个映射，它指定E(G)中的每条边与V(G)中的点组成的无序点对相对应。若用小圆点表示点集V(G)中的点，连线表示边集E(G)中的边，则可用图形将图表示出来，称之为图的图形。我们常用图的图形代表图本身。例6.2.
6、1设V={v1,v2,v3,v4}，E={e1,e2,e3,e4,e5}，：EVV定义为(e1)=v1v2，(e2)=v2v3，(e3)=v2v3，(e4)=v3v4，(e5)=v4v4，则G={V,E}是一个图，其图形如图所示。图6.2.1例6.2.2设V={v1,v2,v3,v4}，E={v1v2,v1v2,v2v3}，则G={V,E}是一个图，其图形如图所示。图6.2.2定义6.2.2设e=uv为图G的一条边，我们称u，v是e的端点，u与v相邻，边e与点u（或v）相关联；称u是e的起点，v是e的终点。若两条边e1与e2有共同的端点，则称边e1与e2相邻；称有相同起点
7、和终点的两条边为重边；称两端点均相同的边为环；称不与任何边相关联的点为孤立点。无环且无重边的图称之为简单图。例6.2.1和例6.2.2都不是简单图，因为例6.2.1中既含重边（e2与e3）又含环（e5），而例6.2.2中含重边（v1v2）。下图中给出的则是简单图。图6.2.3任意两点均相邻的简单图称之为完全图。n个点的完全图记为Kn，图6.2.4中给出的分别是K2，K3，K4。图6.2.4如果图G的各条边都被赋予了方向，则称图G为有
