Matlab最优化理论中的最短路问题 (2)
时间:2017-06-16 16:50 来源:毕业论文 作者:毕业论文 点击:次
为了便于读者对图论的基础知识有一个初步的了解，下面先介绍一下和本课题相关的概念。 1.1 图的概念 图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736 年发 表的“哥尼斯堡的七座桥”。 图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。 当然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。欧拉为了解决这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个有四个“点”，七条“线”的“图”。问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联，将这个判定法则应用于七桥问题，得到了“不可能走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。 1.1.1 无向图 无向图——设 是一个有 个顶点的非空集合： ； 是一个有 条无向边的集合： ，则称 和 这两个集合组成了一个无向图，记作无向图 。 中任一条边 若连接点 和 ，则记为，并称 与 为无向边的两个端点；边 与顶点 及 相关联，顶点 与顶点 相邻。 对于图 有时为说明问题， 与 也可写作 及 。 例1-1 给无向图 ，其中 ， ， 边与顶点的关系情况由表1-1给出。 根据表1-1，可作起几何图形，如图1-1所示。 在做几何图形时，仅要求表示出顶点、边以及它们之间的关联状况，而对于顶点位置的布置以及边的曲直、长短都没有任何规定。从而，同一图 ，可以有许多不同的几何图。 基于无向图 的结构特点，我们给出下列术语。 平行边——若两条不同的边 具有相同的端点，则称 为 的平行边。如图1-1中的 与 即为平行边。 简单图——若图 无平行边，则称图 为简单图。 完备图——若图 中任意两个顶点之间恰有一条边相关联，则称图 为完备图。 子图——设 ， 都是图，且 则称 为图 的子图，并记为 。 生成子图——若 ，且 ，则称 是 的生成子图。 导出子图——设图 ，非空边集 ，如果 中与 中诸边相关联的顶点全体记为 ，则子图 称为图 的由 导出的子图。记 。 链——无向图 中一个由顶点和边交错而成的非空有限序列： ,且 ，则称 为 中一条连接 与 的链。 在简单图中，链由它的顶点序列确定，所以简单图中的链可用其顶点表示： 。若 为链 中的边，可简写为 。链 中的边的全体记为 。 若 则 称为闭链。当 称 为开链。 回路——若一个闭链 ，除了第一个顶点和最后一个顶点相同外，没有相同的顶点和相同的边，则该闭链 称为回路。 连通图——若图 中任意两顶点 和 之间存在一条链（称 与 在 内连通），则称图 为连通图。否则，称为分离图。 (责任编辑：qin) |