先考虑无向图G=(V,E),如果图G中，一条边的两个端点是相同的那么称这条边是环，如图中 的边v3,v3是环。 如果两个点之间有两条以上的边，那么称它们为多重边，如图中的边v1,v2,2,v1]. 一个无环，无多重边的图称为简单图。 一个无环，有多重边的图称为多重图 以点v为端点的边的个数称为点v的次，记作d( 次为零的点称为弧立点：次为1的点弥为县挂点： 悬挂点的边称为悬挂边；次为奇数的点称为奇点 次为偶数的点称为偶点 链：由两两相邻的点及其相关联的边构成的点边序列： 圈：v0=vn的链称为圈或闭链； 初等圈：圈中所含的点均不相同： 简单圈：圈中所含的边均不相同。 连通图：图中任意两点之间均至少有一条链，否则称作不连通图。 连通分支： 支撑子图（生成子图） 如果V2=/1.E2E1称G2是G1的古堂子图（生成子图） 有向图相关概念 基础图：有向图中去掉所有弧上的箭头，得到的无向图。 弧：有向图的边a=(u,),起点u,终点v; 路：若有从u到v不考虑方向的链，且各方向一致，则称之为从u到的路； 初等路：各顶点都不相同的路： 初等回路：u=V的初等路 无向图的性质 定理1（握手定理）所有顶点次数之和等于所有边数的2倍。 定理2在任一图中，奇点的个数必为偶数。 6.2最小支撑树 （一）树的概念及性质 树：无圈连通图。 树的性质：设G=（V,E),V=(v1,v2,…vm),E=(e1,e2…en),下列关于树的命题相互等 价： （1)G为树： (2)G连通，且边数=点数-1； (3)G无圈，且边数=点数-1： (4)G连通，且删去G中任一条边后不连通； (5)任意两个顶点之间恰有一条链 图的支撑树： 若一个图G=(V,E)的支撑子图T=(V,E)构成树，则称T为G的支撑树，又称生成树、部分 树 定理3图G有支撑树充要条件是图G是连通。 如何找一个图的支撑树？ 先考虑无向图 G =（V，E ）。如果图G 中，一条边的两个端点是相同的,那么称这条边是环，如图中 的边[v3 ,v3]是环。 如果两个点之间有两条以上的边，那么称它们为多重边，如图中的边[v1,v2],[v2,v1]。 一个无环，无多重边的图称为简单图。 一个无环，有多重边的图称为多重图。 以点v为端点的边的个数称为点v的次，记作d(v) 。 次为零的点称为弧立点; 次为1的点称为悬挂点; 悬挂点的边称为悬挂边; 次为奇数的点称为奇点; 次为偶数的点称为偶点。 链：由两两相邻的点及其相关联的边构成的点边序列; 圈：v0 = vn 的链称为圈或闭链； 初等圈：圈中所含的点均不相同； 简单圈：圈中所含的边均不相同。 连通图：图中任意两点之间均至少有一条链，否则称作不连通图。 连通分支: 支撑子图（生成子图）: 如果 V2 = V1 , E2 E1 ,称 G2 是 G1 的支撑子图（生成子图）。 有向图相关概念 基础图：有向图中去掉所有弧上的箭头，得到的无向图。 弧：有向图的边a=(u ,v),起点u,终点v； 路：若有从 u 到 v 不考虑方向的链,且各方向一致,则称之为从u到v的路； 初等路: 各顶点都不相同的路； 初等回路:u = v 的初等路; 无向图的性质 定理1 (握手定理)所有顶点次数之和等于所有边数的2倍。 定理2 在任一图中，奇点的个数必为偶数。 6.2 最小支撑树 （一）树的概念及性质 树: 无圈连通图。 树的性质：设G=（V，E），V=（v1,v2,…vm），E=（e1,e2,…en），下列关于树的命题相互等 价： （1）G为树； （2）G连通，且边数=点数-1； （3）G无圈，且边数=点数-1； （4）G连通，且删去G中任一条边后不连通； （5）任意两个顶点之间恰有一条链。 图的支撑树： 若一个图 G =（V , E）的支撑子图 T=（V , E´） 构成树，则称 T 为G的支撑树，又称生成树、部分 树。 定理3 图G有支撑树充要条件是图G是连通。 如何找一个图的支撑树？