第7章 图 论pptppt课件.pptVIP

第7章 图 论 7.1 问题驱动：最佳灾情巡视路线 根据必威体育精装版天气预报，某县将要遭遇特大暴雨，为预防洪涝灾情发生，提前做好预防工作，县政府决定抽调各职能部门相关人员组成三个工作组到各乡镇、村进行巡视。假设你是县政府秘书，请设计最佳巡视路线。 7.2 图论基本知识 7.2.1 起源 哥尼斯堡是东普鲁士的一座城市，第二次世界大战后划归苏联，也就是现在的加里宁格勒。 普莱格尔河流经此城市，河中有两个孤岛，有七座桥将两岛及岛与河岸相连，如图所示。当时那里的居民热衷于这样一个问题：从一个点出发，能否通过每座桥一次且仅一次，最后回到原来的出发点？ 7.2.2 图论中的一些基本概念 1.有序三元组 称为一个图。其中 （1） 是有穷非空集，称为顶点集，其中的元素叫图G的顶点。 （2） 称为边集，其中的元素叫图G的边。 （3） 是从边集到顶点集中的有序或无序的元素偶对的集合的映射，称为关联函数。 2.边有方向的图，称为有向图，边无方向的图称为无向图。连接两个顶点至多有一条边，且一条边的两个顶点不重合的图称为简单图。 6.任意两个顶点之间都有边相连的简单图，称为完备图。 7.如果图 的子图 是一棵树，且 ，则称 是 的生成树。 8.设对图 的每一条边 赋予一个实数 ，称为边的权，则称 为赋权图(或加权图)。连通的赋权图的权和最小的生成树称为的最小生成树 9.有向图 中，每边加权 ，则称这个赋权的有向图为一个网络，记作 , 其中c为容量函数，c(e)称为边e的容量，X与Y为网络的发点集与收点集，X的顶点称作发点或源，Y的顶点称作收点或汇，其余为中间点集。 10.网络 中，若函数 满足 任给` ， (2) 任给 ， ，其中 是 以为终点的边集， 是以 为起点的边集，称 为网络的一个流， 为边的流量。 7.2.3 图的矩阵表示 图的矩阵表示常用的有两种形式：邻接矩阵和关联矩阵。邻接矩阵常用于研究图的各种道路的问题，关联矩阵常用于研究子图的问题。由于矩阵的行列有固定的顺序，因此在用矩阵表示图之前，须将图的结点和边加以编号（定序），以确定与矩阵元素的对应关系。 1.邻接矩阵 设 是一简单有向图，结点集为 。构造矩阵 其中 则称A为有向图G的邻接矩阵。 这个定义也适用于无向图，只须把其中的有向表示换成无向表示就行了。 对于赋权图Ｇ，其邻接矩阵记作 ，其中： 2.关联矩阵 设 是一个无环的有向图， 。构造矩阵 ，其中 称M是G的关联矩阵。 设 是无环的无向图， 。构造矩阵 ，其中 ,称M为G的关联矩阵。 例1 图的邻接矩阵是 7.3 图论与网络模型 7.3.1最短路问题 假设给定连接若干城市的公路网，寻求从指定城市到各城去的最短路线。 设指定城市为图的一个顶点 ，其余任一城市为图的一个顶点 ，连接任意两城市的公路为图的边 ， 为边之长，即在加权图中求 两点之间的路径 ，使该路径上的边权之和最小，即 解决这一问题可以用迪克斯特拉（Dijkstra）算法， 0-1规划法、动态规划法求解。本节主要介