|
子图 设G=(VE)是一个图若V是V的子集E是E的子集且E中的边所关联的顶点均在V中则G=(VE)也是一个图并称其 为G的子图(Subgraph) 【例】图给出了有向图G l 的若干子图;图给出了无向图G 的若干个子图 注意 设V={v v v }E={(v l v )(v v )}显然V属于V(G )E属于E(G )但因为E中序偶对 (v v )所关联的顶点v 不在V中所以(VE)不是图也就不可能是G 的子图 路径(Path) 无向图的路径 在无向图G中若存在一个顶点序列v p v i v i …v im v q 使得(v p v i )(v i v i )…(v im v q )均属于E(G)则称顶点v p 到v q 存在一条路径(Path) 有向图的路径 在有向图G中路径也是有向的它由E(G)中的有向边…组成 路径长度 路径长度定义为该路径上边的数目 简单路径 若一条路径上除了v p 和v q 可以相同外其余顶点均不相同则称此路径为一条简单路径 【例】在图G 中顶点序列v l v v v 是一条从顶点v 到顶点v 的长度为的简单路径 【例】在图G 中顶点序列v v v v v 是一条从顶点v 到顶点v 的长度为的路径但不是简单路径; 简单回路或简单环(Cycle) 起点和终点相同(v p =v q )的简单路径称为简单回路或简单环(Cycle) 【例】图G 中顶点序列v v v v 是一个长度为的简单环 【例】有向图G 中顶点序列v v v 是一长度为的有向简单环 有根图和图的根 在一个有向图中若存在一个顶点v从该顶点有路径可以到达图中其它所有顶点则称此有向图为有根图v称作图的根 |
