有向赋权图.doc

HYPERLINK"http://wenwen.soso.com/z/Search.e?sp=S%E5%9B%BE%E8%AE%BA&ch=w.search.yjjlink&cid=w.search.yjjlink"\t"_blank"图论基本概念重要定义：有向图：每条边都是有向边的图。无向图：每条边都是无向边的图。混合图：既有有向边又有无向边的图。自回路：一条边的两端重合。重数：两顶点间若有几条边，称这些边为平行边，两顶点a,b间平行边的条数成为（a,b）的重数。多重图：含有平行边的图。简单图：不含平行边和自回路的图。注意！一条无向边可以用一对方向相反的有向边代替，因此一个无向图可以用这种方法转化为一个有向图。定向图：如果对无向图G的每条无向边指定一个方向由此得到的有向图D。称为的G定向图.底图：如果把一个有向图的每一条有向边的方向都去掉，得无向图G称为的D底图。逆图：把一个有向图D的每条边都反向由此得到的图称为D的逆图。赋权图：每条边都赋上了值。出度：与顶点相连的边数称为该定点的度数，以该定点为始边的边数为出度。入度：以该定点为终边的边数为入度。特殊！度数为零的定点称为孤立点。度数为一的点为悬挂点。无向完全图：在阶无向图中如果任何两点都有一条边关连则称此图是无向完全图。Kn完全有向图：在阶有向图中如果任意两点都有方向相反的有向边相连则称此图为完全有向图。竟赛图：阶图中如果其底图是无向完全图，则程此有向完全图是竟HYPERLINK"http://wenwen.soso.com/z/Search.e?sp=S%E5%A1%9E%E5%9B%BE&ch=w.search.yjjlink&cid=w.search.yjjlink"\t"_blank"塞图。注意！n阶有向完全图的边数为n的平方；无向完全图的边数为n(n-1)/2。下面介召图两种操作：①删边：删去图中的某一条边但仍保留边的端点。②删点：删去图中某一点以及与这点相连的所有边。子图：删去一条边或一点剩下的图。生成子图：只删边不删点。HYPERLINK"http://wenwen.soso.com/z/Search.e?sp=S%E4%B8%BB%E5%AD%90&ch=w.search.yjjlink&cid=w.search.yjjlink"\t"_blank"主子图：图中删去一点所得的子图称的主子图。补图：设为阶间单无向图，在中添加一些边后，可使成为阶完全图；由这些添加边和的个顶点构成的图称为的补图。重要定理：定理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推论在无向图中，度数为积数的顶点个数为HYPERLINK"http://wenwen.soso.com/z/Search.e?sp=S%E5%81%B6%E6%95%B0&ch=w.search.yjjlink&cid=w.search.yjjlink"\t"_blank"偶数。通路和富权图的最短通路1通路和回路基本概念：通路的长度：通路中边的条数。回路：如果通路中始点与终点相同。简单通路：如果通路中各边都不相同。基本通路：如果通路中各顶点都不相同。显然（基本通路一定是简单通路，但简单通路不一定是基本通路）可达：在图G中如果存在一条v到d通路则称从v到d是可达。连通：在无向图中如果任意两点是可达的，否则是不连通的。强连通：在有向图中如果任意两点是互可达的。单向连通：在有向图中如果存在任意两点的通路。弱连通：在有向图中如果其底图是连通的。权：在图的点或边上表明某种信息的数。赋权图：含有权的图。赋权图的最短通路问题的算法：先求出到某一点的最短通路，然后利用这个结果再去确定到另一点的最短通路，如此继续下去，直到找到到的最短通路为止。指标：设V是图的点集，T是V的子集，且T含有z但不含a，则称T为目标集。在目标集T中任取一个点t，由a到t但不通过目标集T中其它点所有通路中，个边权和的最小者称为点t关与T的指标记作DT(t)。图和矩阵住意两个的区别：A·A中元素的意义：当且仅当a和a都是1时，aa=1而a和a都为1意味着图G中有边(v,v)和(v,v)。于是可得如下结论：从顶点v和v引出的边，如果共同终止于一些顶点，则这些终止顶点的数目就是b的值；特别对于b，其值就是v的出度。A·A中元素的意义：当且仅当a和a都为1时，aa=1，这意味着图中有边(v,v)和(v,v)。于是的得如下结论：从某些点引出的边，如果同时终止于v和v，则这样的顶点数就是的值。特别对于b，其值就是的v入度。幂A中元素的意义：当m=1时，a中的元素=1，说