第6章图与网络分析6.1.pptVIP

§6.1 图与网络的基本概念 自然界和人类社会中的许多事务之间的关系都可以用点和线连结起来的图形来描述，例如在交通运输图上，产地和销地通常用点来表示，有连线就意味着这两地可以直接到达，无连线就表示不能到达，可以研究从产地到销地的最短路径或者分析运费最小的运输方案。类似地，城市规划、电视网络、信息传递等问题均可以这样用点和线连接起来的图进行模拟。我们除去这些实际问题的具体名称和含义，保留它们的共同点，便有了图的概念。 作业：P278 (1);(2) 第6章 图与网络分析 §6.1图与网络的基本概念 §6.2树与最小生成树 §6.3最短路问题 §6.4网络最大流问题 §6.5最小费用最大流问题 §6.6中国邮递员问题 §6.7运输问题 §6.8应用LINGO、MATLAB软件求解网络问题 网络模型 企业管理 组织生产 交通运输 图论 “七桥”难题: Euler 图6.0.1 图6.0.2 §6.1.1图及其分类 定义6.1.1 称二元组(V,E)为一个图， 记为G= (V,E)。 其 中 为若干个点构成的集合， 点 称为图G的顶 点。 为点与点之间的连线构成的集合，称为 边。 当V，E均为有限集时， G称为有限图， 否则，称为 无限图。 一般地， 若边 e连结顶点 u和v，则记为e=(u,v)或 e=(v, u)， 称 u和v为e的端点，且称 e与端点u和v关联， e称为u和v的关联边。 若u，v之间有一条边，则称u 和v相邻， 若两条边有一个公共端点，则称这两条边 相邻。 没有边与之关联的顶点称为孤立点。 例6.1.1 如图6.1.1， 图6.1.1 这里， 和 和 相邻， 和 和 不相邻， 和 不关联。 顶点 和 的关联边有两条： 和 而 两个端点合二为一， 的 称两个端点重合的边为环或自 回路。 这里 为环。 两个顶点之间多于一条边的，称 称为多重边，也称为平行边。 为平行边。 和 为 图6.1.1 孤立点。 在图论中，常用 m=|E|表示图的边数，用n=|V| 图的顶点个数。 若图G= (V,E)中既不含环，也不含多重边，则 称之为简单图。 若G中含有多重边，则称之为多重 图。 称这样的边为无向边，对 若G中的边没有方向， 应的图称为无向图。 而有方向的边称为弧或有向边。 在图中，用箭头表示方向。 由顶点u指向顶点 v的弧 记为a=(u,v), u称为a的始点，v称为a的终点。 此时(u, v)和(v,u)不同。 由点集 V和弧集 A构成的图记为D= (V,A)，称为有向图。 图6.1.2为有向图。 图6.1.2 定义6.1.2 每一对顶点间都有相连的无向简单图称为 完全图。 有n个顶点的无向完全图记为 点间有且仅有一条有向边的简单图称为有向完全图。 每一对顶 图6.1.3（a） 图6.1.3（b） 图6.1.3（a）为完全图，可记为 为有向完全图，图6.1.1则不是完全图。 图6.1.3（b）称 定义6.1.3 若图G=(V,E)的顶点集 V可分成两个非空 子集 X和Y，即 使得E中每条 边的两个端点必有一个端点属于X，另一个端点属于 Y，则称G为二部图，也称 G为偶图，并记 图6.1.4（a）二部图 图6.1.4（b）非二部图 §6.1.2 顶点的次 定义6.1.4 以点v为端点的边数称为点 v的次，记为 deg(v)，简记d(v)。 若 则称 为图G的次序列。 次为1的点称为悬 挂点，连结悬挂点的边称为悬挂边。 称为奇点，次为偶数的点称为偶点。 次为奇数的点 如图6.1.1中， 为悬挂点， 为悬挂边。 图6.1.1 定理6.1.1 任何图G=(V,E)中，所有顶点的次数之和 等于边数的两倍，即 证明： 由于每条边必与两个顶点关联， 在计算点的 次时， 每条边均被计算了两次， 所以顶点次数之和 等于边数的两倍。 证毕。 定理6.1.2 任何图G=(V,E)中，奇点的个数必为偶数。 证明： 设G中奇点与偶点的集合分别为 则 由定理6.1.1知 由于2|E|为偶数， 而 也为偶数， 故 亦必为偶数， 即奇点的个数为偶数。 证毕。 在有向图中， 注1： 以点v为起点的边数称为点 v的 出次， 记为 以点v为终点的边数称为点 v的入 次，记为 如图6.1.2中， 显然， 点v的出次与入次之和就是点v的次。 有向图中，所有顶点的出次之和等于所有入次之和。 而且， 在 图6.1.2 §6.1.3 子图 设有两个图G=(V,E)和 若 且对 中任意一条边 均有 则称 是G的子图，