1、第八章图与网络分析ABC D哥尼斯堡 “七桥 ”难题1736年，数学家欧拉把该问题归结为下图： ABC D主要内容：第一节 图与网络的基本知识第二节 树第三节 最短路问题第四节 最大流问题第五节 最小费用流问题第一节图与网络的基本知识一、图与网络的基本概念1.图及其分类图： 是由点集 V=vi和 V中元素的无序对的一个集合 E=ek所构成的二元组，记为： G=（ V,E）。V中的元素 vi叫做 顶点 ， E中的元素 ek叫做 边 。有限图无限图无向图有向图简单图：不含 环 或 多重边 的图多重图m（ G） =|E|称为 G中的 边数， 简记为 m；n（ G） =|V|称为 G中的 顶点个数，
2、简记为 n。完全图： 每一对顶点都有边相连的无向简单图称为完全图。有 n个顶点的无向完全图记为 Kn。有向完全图： 每一对顶点间有且仅有一条有向边的简单图。二部图： 图 G（ V,E）的点集 V可以分为两个非空子集 X,Y，即 X Y=V， XY=， 使得 E中每条边的两个端点必有一个属于 X，另外一个属于 Y，则称 G为二部图。2.顶点的次顶点的次： 以点 v为端点的边数叫做点 v的次，简记为 d(v)。悬挂点 孤立点 奇点 偶点定理 1： 任何图中，顶点次数的总和等于边数的 2倍。定理 2： 任何图中，次为奇数的顶点必为偶数个。出次： 有向图中，以点 vi为始点的边数叫做点 vi的出次，简
3、记为 d+(vi)。入次： 有向图中，以点 vi为终点的边数叫做点 vi的入次，简记为 d-(vi)。vi点的出次和入次之和就是该点的次。有向图中，所有顶点的入次之和等于所有顶点的初次之和。3.子图4.网络子图： 图 G =（ V,E)，若 E是 E的子集， V是 V的子集，且 E中的边仅与 V中的顶点相关联，则称 G=(V,E)是 G的一个子图。生成子图（支撑子图）： 若 G=(V,E)是 G的一个子图，且有V=V，则 G是 G的一个生成子图。点或边带有某种数量指标的图称为 网络（赋权图） 。二、连通图链：如 v1,e1,v2,e6,v4,e7,v3,e3,v2,e5,v5；初等链：圈：初等
4、圈：v1v2v3 v4v5v6e1e2e3 e4e5e6e7e8e9e10如 v1,e1,v2,e6,v4,e10,v6,e9,v5；如 v1,e1,v2,e5,v5,e8,v4,e6,v2,e3,v3， e2， v1；如 v1,e1,v2,e6,v4,e7,v3， e2， v1.道路： 有向图中，链上的边方向相同时，称为道路。回路： 有向图中，圈上的边方向相同时，称为回路。连通图： 一个图中任意两点间至少有一条链相连，则称此图为连通图。如： v1,e2,v3,e7,v4,e8,v5是一条道路；v1,e1,v2,e5,v5,e8,v4是一条链但不是一条道路。v1v2v3 v4v5e1e2e3 e4e5e6e7e8如： v1,e2,v3,e4,v2,e1,v1是一条回路；v1,e1,v2,e6,v4,e7,v3， e2， v1是圈但不是一条回路。每一个连通图都可以分为若干个连通子图。
