第2编图论第3章ppt课件.ppt

《第2编图论第3章ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2编图论第3章图的基本概念与性质1在运筹学、网络理论、信息论、计算机学科各领域、社会、经济等方面有广泛应用。最早起源于数学游戏和难题的研究：欧拉：哥尼斯堡七桥问题、迷宫、博弈、四色猜想、哈密尔顿(环游世界)难题。克希霍夫用图论分析电路网络。发展迅速，应用广泛的一门学科。23.1图的概念与性质3.1.1图的定义与表示定义1一个图是一个序偶,记为G=,其中(1)V={v1,v2,...,vn}为有限非空集合，vi称为结点，简称点，称V为点集。(2)E={e1,e2,...,em}为有限非空的边集合，ei称为

2、边，每个ei都有V中的结点与之对应，称E为边集。如果边ei与结点无序对(u,v)相对应，则称ei为无向边，记为ei=(u,v)。如果边ei与结点有序对相对应，则称ei为有向边，记为ei=，称u为ei的始点，v为ei的终点。3每条边都是无向边的图称为无向图；每条边都是有向边的图称为有向图；在一个图中如果一些边是无向边，另一些边是有向边，则称这个图为混合图。如G=其中V={v1,v2,v3,v4,v5}E={(v1,v2),(v1,v4),(v2,v3),(v2,v4),(v3,v4)}v1v2v3v

3、4Gv5v1v2v3v4G'如G'=其中V={v1,v2,v3,v4}E={,,,,,}4如G''=其中V={v1,v2,v3,v4}E={,,,(v1,v1),(v1,v3),(v3,v4)}v1v2v3v4G''设eE(G),e是G中连接点u,v的边，称u和v与e相关联，u与v称为邻接点，否则称为不邻接。不与任何结点相邻接的结点称为孤立结点，如图G中v5；仅有孤立结点组成的

4、图称为零图；仅有一个孤立结点构成的图称为平凡图。5关联于同一结点的两边称为邻接边；关联于同一结点的一条边称为自回路或环。在有向图中，若有同始点和同终点的多条边，则这些边称为平行边；在无向图中，若两结点间有多条边，则这些边称为平行边；两结点间平行边的条数称为边的重数。含有重边的图称为多重图。非多重图称为线图。将无向图中每条边都看做是两条方向不同的有向边,无向图就转化为有向图。将有向图中每条边都看成无向边，就可得到一个无向图，称为原有向图的底图。63.1.2图的基本概念与握手定理定义21.在无向图G=中与结点v关联的边的

5、条数(自回路算两条边)，称为该点的度数，记为deg(v)。2.在有向图G=中以结点v为始点的边的条数称为该点的出度，记为deg+(v)；以结点v为终点的边的条数称为该点的入度，记为deg－(v)。v1v2v3v4v5图G=的最大度数记为(G)。图G=的最小度数记为(G)。左图中(G)=3,(G)=2.7定理1(握手定理)图G=中，结点度数之和等于边数的两倍，即证:一边关联两个结点，给每个结点的度数加1.∴度的总和=边数的两倍.■推论在任何图中，度数为奇数的结点必是偶数个。证:设

6、V1为奇数度结点集,V2为偶数度结点集。∑deg(v)+∑deg(v)=2

7、E

8、vV1vV2∵后面两项为偶数，∴第一项应该为偶数，即

9、V1

10、应该为偶数.■8定理2在有向图中，所有结点的入度之和等于所有结点的出度之和。定义3不含平行边和自回路的图称为简单图。定义4若每一对结点间都有边相连的无向简单图称为无向完全图，简称完全图，记为Kn；若每一对结点间都有方向相反的两边相连的有向简单图称为有向完全图。v1v2v3v4v5K5v1v2v39无向完全图的边数为n(n－1)/2；有向完全图的边数为n(n－1)。定义5G=为

11、具有n个结点的简单图，由G中所有结点和所有能使G成为完全图的添加边组成的图，称为G的补图，记为G。v1v2v3v4v5Gv1v2v3v4v5Gv1v2v3v4v5K510v1v2v3n=3的有向完全图：v1v2v3Hv1v2v3H11定义6已知图G=和图G'=1.若V'V,E'E,则称G'是G的子图，记作G'G.2.若G'G,且G'G,则称G'是G的真子图，记作G'G.3.若V'=V,E'E,则称G'是G的生成子图(支撑子图).4.若V'V,且V',以V'为结点，以两

12、端点均在V'中的边为边集的G的子图称为V'的导出子图。5.若G''=，使得E''=E－E'，且V''中仅包含E''的边所关联的结点，则称G''是是子图G'的相对于G的补图。12GHG的真子图RG的生成子图SR相对于G的补图TG的导出子图13定义7设G=<