第三章 图论.ppt

第三章 图 论 3.1 图的基本概念 3.2 树 3.3 最 短 路 问 题 3.4 网 络 最 大 流 问 题 作业 3.1 图的基本概念 一、图的例子 在实际生活中，人们为了反映一些对象之间的关系，常常在纸上用点和线画出各种各样的示意图。 【例3.1】 铁路交通图 【例3.2】 有5种化学物品，其中某些是不能放在一起的，若是不能放在一起的，则在它们之间联一条线。如图所示，问最少需要几个库房？ 二、基本概念 图：由一些点及点与点之间的连线组成。 边：若点与点之间的连线没有方向，则称为边。有方向的称为弧。 无向图：如果一个图G是由点和边所构成，则称之为无向图（也简称图），记为 ，其中，V，E分别是G的点集合和边集合。一条连接点 的边记为 。 有向图：如果一个图D是由点和弧所构成，则称之为有向图，记为 ，其中，V，A分别是D的点集合和弧集合。一条方向是从 指向 的弧记为 。 图3-4是一个无向图， 其中， 图3-3是一个有向图， ,其中， 图G或D中的点数记为 ，边（弧）数记为 或 端点：若边 ，则称 的端点，也称 是相邻的。称e是点 （及点 ）的关联边。 环：若图G中，某个边e的两个端点相同，则称e是环。若两个点之间有多于一条的边，称这些边为多重边。 简单图：一个无环、无多重边的图称为简单图。 多重图：一个无环，但允许有多重边的图称为多重图。 次：以点为端点的边的个数称为v的次，记为 如图3-4中， ，环在计算次时应算作两次。如图3-5， 。 悬挂点：称次为1的点为悬挂点， 悬挂点的关联边称为悬挂边。 孤立点：称次为0的点为孤立点。 奇点：次为奇数的点，称为奇点， 否则为偶点。 链（chain）：给定一个图 ，一个点、边交错序列 ，如果满足 则称为一条连接 的链， 记为 ，称点 为中间点。 圈（cycle）：链 中，若 ，则称之为一个圈，记为 初等链：若链 中，点 都是不同的，则称之为初等链。 初等圈：若圈 中，点 都是不同的，则称之为初等圈。 简单圈：若圈中含的边均不相同，则称之为简单圈。 例如，图3-6中， 是一条链，但 不是初等链； 是一条初等链；在此图中， 不存在连接 的链； 是一个初等 圈， 是简单圈，但不是初等圈。 连通图：图G中，若任何两个点之间，至少有一条链，则称G是连通图，否则称为不连通图。若G是不连通图，它的每个连通部分称为G的一个连通分图（分图）。图3-6就是一个不连通图，它有两个连通分图。 支撑子图：给了一个图 ，如果图 使 ，则称 是G的一个支撑子图。 设 ，用 G -v 表示从图G中去掉点 及 的关联边后得到的一个图。 例如，图3-7中， 如图(c)所示；(b)是(a)的一个支撑子图。 基础图：设给了一个有向图 ，从D中去掉所有弧的箭头（方向），就得到一个无向图，称之为D的基础图，记为 。 给D中的一条弧 ，称 为a的始点， 为a的终点， 称弧a是从 指向 的。 设 是D中的一个点弧交错序列，如果这个序列在基础图中所对应的点边序列是一条链，则称这个点弧交错序列是D的一条链。类似定义圈和初等链（圈）。 路（path）：如果 是D中的一条链，且对 ，均有 称之为从 到 的一条路。若路的第一个点和最后一个点相同，则称之为回路（circuit），类似定义初等路（回路）。 是一个回路，