第八章图论Р8/3/2018Р1Р教学目标Р通过本章学习,了解图的基本概念,掌握最短路问题的数学模型、解法及其应用,为实际应用奠定基础。Р8/3/2018Р2Р教学内容Р第一节图的基本概念?图的定义;路和回路;图G的分类。?第二节最短路问题?狄克斯特拉算法(双标号法);无向图上的狄克斯特拉算法。Р8/3/2018Р3Р考核知识点及考核要求Р1.最短路问题(重点) ?领会:最短路问题应用背景;?综合应用:计算具体问题的最短路。?2.图的基本概念(一般)?识记:图的概念,图的分类,链、路与回路。Р8/3/2018Р4Р教学重难点Р最短路问题的数学模型、解法及其应用Р8/3/2018Р5Р教学过程Р8/3/2018Р6Р§1 图的基本概念Р1.1 图的定义?1、许多现象能用图形表示?例8.1用图表示篮球队比赛情况,如图8-1。此图还表示人与人之间的认识关系;表示工厂间业务往来关系。?例8.2 图8-2是一个石油流向的管网示意图用图表示篮球队比赛情况,如图8-2。此图还表示城市交通网络研究最短路程或运费最省的运输方案。Р8/3/2018Р7Р2、几个常用概念?(1)图G的节点、节点集、不同元素的有序偶或无序偶集合、G的边、G的边集?(2)有向边、无向边、关联、无序节点(a,b)、无序节点<a,b>?(3)一个图可用一个图形来表示且表示是不唯一的。见图8-3Р8/3/2018Р8Р1.2 路与回路Р1、路、起点、终点、长度?2、链条、回路Р8/3/2018Р9Р1.3 图G的分类Р1.3.1 按G中关联于同一对节点的边数分为多重图和简单图?1、自回路(环):关联同一节点的一条边?2、平行边(多重边):关联同一对节点的一条边?3、多重图:含有平行边的图?4、简单图:不含平行边和自环的图Р8/3/2018Р10
全文预览
