图论基本教程总结(全).doc

目录 图的基本概念 图的定义图（ Graph ）是由一个用线或边连接在一起的顶点或节点的集合。是一种比线性表和树更为复杂的非线性数据结构，可称为图状结构或网状结构，前面讨论的线性表和树都可以看成是图的简单情况。??? 　图G由两个集合V和E组成，记为：??????? G=(V，E)　　其中：　　V是顶点的有穷非空集合，　　E是V中顶点偶对(称为边)的有穷集。??? 　通常，也将图G的顶点集和边集分别记为V(G)和E(G)。E(G)可以是空集。若E(G)为空，则图G只有顶点而没有边。有向图和无向图1．有向图??? 　如图7.1 G2所示每条边都是有方向的，则称G为有向图(Digraph)。??? ??? ?????? （1）有向边的表示??? 　有向边又称为弧，通常用尖括弧表示一条有向边， v,w 表示从顶点 v 到 w 的一段弧， v 称为边的始点 ( 或尾顶点 ) ， w 称为边的终点， ( 或头顶点 )， v,w 和 w,v 代表两条不同的弧。 ? 【例】vi，vj表示一条有向边，vi是边的始点(起点)，vj是边的终点。注意: vi，vj和vj，vi是两条不同的有向边。（2）有向图的表示? 【例】上面7.1图中G2是一个有向图。图中边的方向是用从始点指向终点的箭头表示的，该图的顶点集和边集分别为：顶点集V={v 1 ,v 2 ,v 3 }弧集E={ v 1 ,v 2 ,v 1 ,v 3 , v 2 ,v 3 ,v 3 ,v 2 } 。注意:v 3 ,v 2 与v 3 ,v 2 表示两条不同的边。 2．无向图??? 　如图7.1G1中所示的每条边都是没有方向的，则称G为无向图(Undigraph)。（1）无向边的表示??? 　通常用圆括号表示无向边， (v,w) 表示顶点 v 和 w 间相连的边。在无向图中 (v,w) 和 (w,v) 表示同一条边，如果顶点 v,w 之间有边 (v,w) ，则 v,w 互称为邻接点。 ? 【例】无序对(vi，vj)和(vj，vi)表示同一条边。（2）无向图的表示? 【例】上面7.1图中的G1是无向图，它们的顶点集和边集分别为：顶点集：V={v 1 ,v 2 ,v 3 ,v 4 }边集：E={(v 1 ,v 2 ), (v 1 ,v 3 ), (v 1 ,v 4 ), (v 2 ,v 3 ), (v 3 ,v 4 )} 注意:(v 2 ,v 1 ) 与（ v 1 ,v 2 ）表示同一条边， (v 2 ,v 3 ) 与 (v 3 ,v 2 ) 也表示同一条边，等等。 ???3．图G的顶点数n和边数e的关系（1）若G是无向图，则0≤e≤n(n-1)/2??? 　恰有n(n-1)/2条边的无向图称无向完全图(Undireet-ed Complete Graph)（2）若G是有向图，则0≤e≤n(n-1)。??? 　恰有n(n-1)条边的有向图称为有向完全图(Directed Complete Graph)。? 注意：??? 　完全图具有最多的边数。任意一对顶点间均有边相连。4.对图的讨论中我们对图作一些限制：第一，图中不能有从顶点自身到自身的边（即自身环），就是说不应有形如（vx,vx)的边或 vx,vx 的弧。第二，两个顶点vt和vu之相关联的边不能多于一条。图的基本术语 （1）完全图(complete graph)：完全无向图：　　有n个顶点无向图，若有n(n-1)/2条边，则称。如图7.3所示的图G1完全有向图：　　有n个顶点有向图，若有n(n-1)条边，则称。如图7.3所示的图G2（2）权(weight)：　　边（弧）上具有与它相关的系数，称之为权。 这些权可以表示从一个顶点到另一个顶点的距离、花费的代价、所需的时间和次数等。这种带权图也被称为网络(network)。（3）邻接顶点(adjacent vertex)：　　在无向图中，若(u，v)是E(G)中的一条边，则称u和v互为邻接顶点。　　　　边(u，v)依附于顶点u和v。　　　　边u,v与顶点u和顶点v相关联。（4）顶点的度(Degree)　无向图中顶点v的度(Degree)　??? 无向图中顶点v的度(Degree)是关联于该顶点的边的数目，记为D(v)。【例】下图G2中顶点v1的度为3有向图顶点v的入度(InDegree)　??? 有向图中，以顶点v为终点的边的数目称为v的入度(Indegree)，记为ID(v)。【例】下图G1中顶点v2的入度为l有向图顶点v的出度(Outdegree)　??? 有向图中，以顶点v为始点的边的数目，称为v的出度(Outdegree)，记为OD(v)【