2、,y>表示从顶点x到顶点y存在一条弧（Arc），x称为弧尾（tail）或起始点（initialnode），y称为弧头（head）或终端点（terminalnode）。这样的图被称为有向图（digraph）。如果∈E且有∈E，即E是对称的，则用无序对(x,y)代替有序对和，表示x与y之间存在一条边（edge），这样的图称为无向图（undigraph）。如图10.1所示。10.1图的定义与相关概念图G的形式化定义为：G=(V,E)，其中，V={x
3、x∈数据元素集合}，E={
4、Path(x,y)/(x∈V,y∈V)}。Path(x
5、,y)表示的意义或信息。在图10.1中，有向图G1可以表示为G1=(V1,E1)，其中，顶点的集合为V1={a,b,c,d}，边的集合为E1={,,,,,}。无向图G2可以表示为G2=(V2,E2)，其中，顶点的集合为V2={a,b,c,d}，边的集合为E2={(a,b),(a,c),(a,d),(b,c),(c,d)}。10.1图的定义与相关概念1．邻接点对于无向图G=(V,E)，若边(vi,vj)∈E，则称vi和vj互为邻接点（adjacent），即vi和vj相邻接。边(vi,vj)依附于顶点vi和vj
6、，或者说(vi,vj)与顶点vi、vj相关联。对于有向图G=(V,A)，若弧∈A，则称顶点vi邻接到顶点vj，顶点vj邻接自顶点vi。弧和顶点vi、vj相关联。无向图G2的边的集合为E={(a,b),(a,c),(a,d),(b,c),(c,d)}，顶点a和b互为邻接点，边(a,b)依附于顶点a和b。顶点c和d互为邻接点，边(c,d)依附于顶点c和d。有向图G1的弧的集合为A={,,,,,}，顶点a邻接到顶点b，弧与顶点a和b相关联。顶点c邻接自顶点d，弧与顶点d和c相
7、关联。10.1图的定义与相关概念2．顶点的度对于无向图，顶点v的度是指与v相关联的边的数目，记作TD(v)。对于有向图，以顶点v为弧头的数目称为顶点v的入度(indegree)，记作ID(v)。以顶点v为弧尾的数目称为v的出度(outdegree)，记作OD(v)。顶点v的度(degree)为TD(v)=ID(v)+OD(v)。无向图G2中顶点a的度为3，顶点b的度为2，顶点c的度为3，顶点d的度为2。有向图G1的弧的集合为A={,,,,,}，顶点a、b、c和d的入度分别为1、2、2和1，顶点a、b、c和d的出度分别
8、为2、1、2和1，顶点a、b、c和d的度分别为3、3、4和2。若图的顶点的个数为n，边数或弧数为e，顶点vi的度记作TD(vi)，则顶点的度与弧或者边数满足关系：e=10.1图的定义与相关概念3．路径无向图G中，从顶点v到顶点v’的路径（path）是从v出发，经过一系列的顶点序列到达顶点v’。如果G是有向图，则路径也是有向的，路径的长度是路径上弧或边的数目。第一个顶点和最后一个顶点相同的路径称为回路或环（cycle）。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点外，其他顶点不重复出现的回路，称为简单回路或简单环。在图10.1所示的有向图G1中，顶点序列
9、a→d→c→a构成了一个简单回路。在无向图G2中，从顶点a到顶点c所经过的路径为a，d和c（或a、b、c）。10.1图的定义与相关概念4．子图假设存在两个图G={V,E}和G’={V’,E’}，若G’的顶点和关系都是V的子集，即有V’V，E’E，则G’为G的子图。如图10.2所示。10.1图的定义与相关概念5．连通图和强连通图对于无向图G，如果从顶点vi到顶点vj存在路径，则称vi到vj是连通的。如果对于图中任意两个顶点vi、vj∈V，vi和vj都是连通的，则称G是连通图（connectedgraph）
