图论基础(信息学奥赛).ppt

文档介绍：该【图论基础(信息学奥赛) 】是由【licaia】上传分享，文档一共【90】页，该文档可以免费在线阅读，需要了解更多关于【图论基础(信息学奥赛) 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。图论及其算法
单击添加副标题
吴闻
第一章 基本概念
CONTENTS
01
引言
单击添加文本具体内容
03
道路和回路
单击添加文本具体内容
02
图的定义
单击添加文本具体内容
04
树
单击添加文本具体内容
引言
图论是一个应用十分广泛而又极其有趣的数学分支。物理、化学、生物、科学管理、计算机等各个领域都可找到图论的足迹。
介绍几个图论有关的简单例子
引言
例1 下图是一个公路网，V1 ,V2,...,V10是一些城镇，每条线旁边的数字代表这一段公路的长度。现在问，要从V1把货物运到V10，走哪条路最近?
引言
例1实际上，就是图论中的求最短路径问题。在现实中有很多此类问题，所以图论中求最短路径算法是一个非常经典和重要的算法。
引言
例2 下图是一个公路网，V1 ,V2,...,V10看成公路网的一个站点，若这个公路网目前被敌方占领。请分析一下，最少需要破坏其公路网的几个站点，就可摧毁敌方整个运输线
1
引言
例2属于图的连通性问题。找出图中的割顶集，就是问题的解。军事指挥中很多此类问题。
引言
例3 飞行大队有若干个来自各地的驾驶员，专门驾驶一种型号的飞机，这种飞机每架有两个驾驶员。由于种种原因，例如相互配合的间题，有些驾驶员不能在同一架飞机上飞行，问如何搭配驾驶员，才能使出航的飞机最多。
引言
例3 用V1 ,V2,...,V10代表这10个驾驶员。如果两个人可以同机飞行，就在代表他们两个之间连一条线;两个人不能同机飞行，就不连。例如V1和V2可以同机飞行，而V1和V 3就不行。
引言
例3此类问题属于图的最大匹配问题
将实际生活中的事物分析转化为图论问题的实例还很多...