第2 编图论第3 章.ppt

1第2 编图论第3 章图的基本概念与性质 2 ?在运筹学、网络理论、信息论、计算机学科各领域、社会、经济等方面有广泛应用。?最早起源于数学游戏和难题的研究: 欧拉:哥尼斯堡七桥问题、迷宫、博弈、四色猜想、哈密尔顿(环游世界)难题。?克希霍夫用图论分析电路网络。?发展迅速,应用广泛的一门学科。 3 图的概念与性质 图的定义与表示定义 1一个图是一个序偶<V,E>, 记为 G=<V,E> , 其中(1) V={v 1,v 2,...,v n}为有限非空集合, v i称为结点,简称点,称 V为点集。(2) E={e 1,e 2,...,e m}为有限非空的边集合, e i称为边,每个 e i都有 V中的结点与之对应,称 E 为边集。?如果边 e i与结点无序对(u,v) 相对应,则称 e i为无向边,记为 e i = (u,v) 。如果边 e i与结点有序对<u,v> 相对应,则称 e i为有向边,记为 e i = <u,v> ,称 u为e i的始点,v为e i的终点。 4 ?每条边都是无向边的图称为无向图;每条边都是有向边的图称为有向图;在一个图中如果一些边是无向边,另一些边是有向边,则称这个图为混合图。如 G = <V, E> 其中 V = {v 1,v 2,v 3,v 4,v 5} E={(v 1,v 2 ),(v 1,v 4 ),(v 2,v 3 ), (v 2,v 4 ),(v 3,v 4 )} v 1v 2v 3v 4G v 5v 1v 2v 3v 4 G' 如 G' = <V, E> 其中 V = {v 1,v 2,v 3,v 4} E={<v 1,v 2 >,<v 1,v 4 >,<v 2,v 3 >, <v 3,v 1 >,<v 4,v 2 >,<v 4,v 3 >} 5 如 G'' = <V, E> 其中 V = {v 1,v 2,v 3,v 4} E={<v 1,v 2 >,<v 2,v 1 >,<v 2,v 3 >, (v 1,v 1 ),(v 1,v 3 ),(v 3,v 4 )} v 1v 2v 3v 4 G'' ?设 e ? E(G), e 是 G 中连接点 u,v 的边,称 u 和v与 e 相关联,u 与v称为邻接点,否则称为不邻接。?不与任何结点相邻接的结点称为孤立结点, 如图 G中v 5;仅有孤立结点组成的图称为零图;仅有一个孤立结点构成的图称为平凡图。 6 ?关联于同一结点的两边称为邻接边;关联于同一结点的一条边称为自回路或环。?在有向图中,若有同始点和同终点的多条边,则这些边称为平行边;在无向图中,若两结点间有多条边,则这些边称为平行边; 两结点间平行边的条数称为边的重数。含有重边的图称为多重图。非多重图称为线图。?将无向图中每条边都看做是两条方向不同的有向边,无向图就转化为有向图。?将有向图中每条边都看成无向边,就可得到一个无向图,称为原有向图的底图。 7 图的基本概念与握手定理定义 2 1. 在无向图 G=<V,E> 中与结点 v关联的边的条数(自回路算两条边),称为该点的度数, 记为 deg(v) 。 2. 在有向图 G=<V,E> 中以结点 v为始点的边的条数称为该点的出度,记为 deg + (v) ;以结点 v 为终点的边的条数称为该点的入度,记为 deg - (v) 。 v 1v 2v 3v 4v 5?图 G=<V,E> 的最大度数记为?(G) 。图 G=<V,E> 的最小度数记为?(G) 。左图中?(G) = 3, ?(G) = 2. 8 定理 1(握手定理) 图 G=<V,E> 中,结点度数之和等于边数的两倍,即||2) deg( Ev Vv???证: 一边关联两个结点,给每个结点的度数加 1. ∴度的总和= 边数的两倍. ■推论在任何图中,度数为奇数的结点必是偶数个。证: 设V 1为奇数度结点集, V 2为偶数度结点集。∑ deg(v) + ∑ deg(v) = 2 |E| v?V 1v?V 2∵后面两项为偶数, ∴第一项应该为偶数, 即|V 1 | 应该为偶数. ■ 9 定理 2在有向图中,所有结点的入度之和等于所有结点的出度之和。定义 3不含平行边和自回路的图称为简单图。定义 4若每一对结点间都有边相连的无向简单图称为无向完全图,简称完全图,记为 K n; 若每一对结点间都有方向相反的两边相连的有向简单图称为有向完全图。 v 1v 2v 3v 4v 5K 5v 1v 2v 310 ?无向完全图的边数为 n(n - 1)/2 ;有向完全图的边数为 n(n -1)。定义 5 G=<V,E> 为具有 n 个结点的简单图,由 G中所有结点和所有能使 G成为完全图的添加边组成的图,称为 G的补图,记为? G。 v 1v