有向赋权图.doc

图论基本概念 重要定义： 有向图：每条边都是有向边的图。 无向图：每条边都是无向边的图。 混合图：既有有向边又有无向边的图。 自回路：一条边的两端重合。 重数：两顶点间若有几条边，称这些边为平行边，两顶点a,b间平行边的条数成为（a,b）的重数。 多重图：含有平行边的图。 简单图：不含平行边和自回路的图。 注意！一条无向边可以用一对方向相反的有向边代替，因此一个无向图可以用这种方法转化为一个有向图。 定向图：如果对无向图G的每条无向边指定一个方向由此得到的有向图D。称为的G定向图. 底图：如果把一个有向图的每一条有向边的方向都去掉，得无向图G称为的D底图。 逆图：把一个有向图D的每条边都反向由此得到的图称为D的逆图。 赋权图：每条边都赋上了值。 出度：与顶点相连的边数称为该定点的度数，以该定点为始边的边数为出度。 入度：以该定点为终边的边数为入度。 特殊！度数为零的定点称为孤立点。度数为一的点为悬挂点。 无向完全图：在阶无向图中如果任何两点都有一条边关连则称此图是无向完全图。Kn 完全有向图：在阶有向图中如果任意两点都有方向相反的有向边相连则称此图为完全有向图。 竟赛图：阶图中如果其底图是无向完全图，则程此有向完全图是竟塞图。 注意！n阶有向完全图的边数为n的平方；无向完全图的边数为n(n-1)/2。 下面介召图两种操作：删边：删去图中的某一条边但仍保留边的端点。 删点：删去图中某一点以及与这点相连的所有边。 子图：删去一条边或一点剩下的图。 生成子图：只删边不删点。 主子图：图中删去一点所得的子图称的主子图。 补图：设为阶间单无向图，在中添加一些边后，可使成为阶完全图；由这些添加边和的个顶点构成的图称为的补图。 重要定理： 定理5.1.1 设图G是具有n个顶点m条边的有向图，其中点集V=v,v,.,v deg+(vi)=deg-(vi)=m 定理5.1.2 设图G是具有n个顶点m条边的无向图，其中点集V=v,v,v,v deg(vi)=2m 推论 在无向图中，度数为积数的顶点个数为偶数。 通路和富权图的最短通路 1通路和回路 基本概念： 通路的长度：通路中边的条数。 回路：如果通路中始点与终点相同。 简单通路：如果通路中各边都不相同。 基本通路：如果通路中各顶点都不相同。显然（基本通路一定是简单通路，但简单通路不一定是基本通路） 可达：在图G中如果存在一条v到d通路则称从v到d是可达。 连通：在无向图中如果任意两点是可达的，否则是不连通的。 强连通：在有向图中如果任意两点是互可达的。 单向连通：在有向图中如果存在任意两点的通路。 弱连通：在有向图中如果其底图是连通的。 权：在图的点或边上表明某种信息的数。 赋权图：含有权的图。 赋权图的最短通路问题的算法：先求出到某一点的最短通路，然后利用这个结果再去确定到另一点的最短通路，如此继续下去，直到找到到的最短通路为止。 指标：设V是图的点集，T是V的子集，且T含有z但不含a，则称T为目标集。在目标集T中任取一个点t，由a到t但不通过目标集T中其它点所有通路中，个边权和的最小者称为点t关与T的指标记作DT(t)。 图和矩阵 住意两个的区别：AA 中元素的意义：当且仅当a 和a 都是1时，a a =1而a 和a 都为1意味着图G中有边(v ,v )和(v ,v )。于是可得如下结论：从顶点v 和v 引出的边，如果共同终止于一些顶点，则这些终止顶点的数目就是b 的值；特别对于b ，其值就是v 的出度。 A A中元素的意义：当且仅当a 和a 都为1时，a a =1，这意味着图中有边(v ,v )和(v ,v )。于是的得如下结论：从某些点引出的边，如果同时终止于v 和v ，则这样的顶点数就是的值。特别对于b ，其值就是的v 入度。 幂A 中元素的意义：当m=1时，a 中的元素=1，说明存在一条边(v ,v )，或者说从v 到v 存在一条长度为一的通路。 A 中元素a 表示从v 到v 的长度为m的所有通路的数目。 欧拉图 主要定义： 如果图中存在一条通过图中个边一次且仅一次的回路，则称此回路为欧拉回路，具有欧拉回路的图称为欧拉图。 如果图中存在一条通过图中各边一次且仅一次的通路，则称此回路为欧拉通路，具有欧拉通路的图称为半欧拉图。 主要定理：一个无向连通图是欧拉图的充要条件是图中各点的度数为偶数。 一个无向连通图是半欧拉图的充要条件是图中至多有两个奇数度点。 设图G是有向连通图，图G是欧拉图的充要条件是图中每个顶点的入度和出度相等。 设图G是有向连通图，图G是半欧拉图的充要条件是至多有两个顶点，其中一个顶点入度比它的出度大1，另一个顶点入度比它的出度少1；而其他顶点的入度和出度相等。 哈密顿图 主要定义：如果图G中存在一条通过图G中各个顶点一次且仅一次的回路，则称此回路为图的哈密顿回路；具有哈密顿回路的图称为哈密顿图。 如果图G中存在一条通过图G中各个顶点一次且仅一次的回路，则称此回路为图的哈密顿回路；具有哈密顿回路的图称为哈密顿图。 主要定理：设图G是哈密顿图，如果从G中删去个p顶点得到图G，则图G的连通分支数小于等于p。 设图G是具有n