教案九网络分析.doc

教案九网络分析教学内容 第六章网络分析与网络计划第一节图的基本概念第二节最小树问题第三节最短路径问题教学学时 3学时教学目标 、网络最短路问题重点难点 重点是图的基本概念、最小生成树、网络最短路问题难点是图的基本概念。教学方法及手段 教师与学生互动 使用多媒体课件教学过程 一、复****巩固 (见课件)(见课件)(见课件)二、讲授新课第一节图的基本概念(见课件)一、,路线关系、工序安排、,-1歌尼斯堡七桥问题哥尼斯堡(Konigsbergs)城域有一个普雷格尔河系,由新河、旧河及其交汇而成的大河组成,它把该城分成了一岛三岸共四块陆地,陆地之间有七座桥连通,如图6-1(a):从某陆地出发,-1(a) 图6-1(b) ,用相应两点间的边表示桥,从而建立了该问题的图的模型,见图6-1(b).于是问题归结为:在这个连通多重图中,能否找出一条回路,,把图6-1(a)所示的实际问题抽象为图6-1(b)-,c,d球队有赛事;b球队还与c球队,,这5个球队之间的比赛关系可用图6-2(a)来表示,也可用图6-2(b)-2(a) 图6-2(b) 以上两例都忽略了问题的具体细节,-1中两岸和岛的形状及桥的曲直都被忽略,-,一个图代表了某些对象集合之间的关系,,,,这里所讲的图并不是解析几何与微积分书中常见的图,在那里,点的位置,,这些都是不重要的,,、(,),记为:=(,)其中,V是一个有限非空的集合,其元素称为G的结点或顶点,简称点,而V称为G的结点集或顶点集,简称点集,一般表示为:={,,…,}而E称为G的边集,表示为:={,,…,}其中由中元素对(,)(,)是无序对,,一般表示为=(,)-3 无向图=(,),其中点集={,,,,},={,,,,,,,},边与顶点的关联情况由表6--1 边与顶点的关联情况(,)(,)(,)(,)(,)(,)(,)(,)(,)         根据表6-1,可作其几何图,如图6-,仅要求表示出顶点、边以及它们间的关联关系,而对顶点的位置以及边的曲直、-3 基于无向图的结构特点,我们给出下列一些术语:平行边——若两条不同的边与具有相同的端点,-3中与是平行边,因为它们的端点均为、.简单图——若无平行边,——图中任两个顶点间恰有一条边相关联,=(,,…,),边的集合=(,,…,).如果中任一条边是的一个有序元素对(,)(这里,≠),则称为有向边集,中元素称为有向边或弧,记为=(,)其中为的起点,,记作=(,)例6-4 给有向图=(,),其中=(,,,),=(,,…,),边与顶点的关联情况如表6--2 边与顶点的关联情况(,)(,)(,)(,)(,)(,)(,)(,)(,)         根据表6-2也可作出有向图,如图6-4(a)图6-4(a) 图6-4(b)