图论与代数结构 - SJTU.ppt

《图论与代数结构 - SJTU.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、图论第一章　基本概念１．１　图的概念世界上许多事物以及他们之间的联系可以用图形直观地表示.这时人们往往用结点表示事物,用边表示它们之间的联系.这种结点和边构成的图形就是图论所研究的对象.图的概念定义1.1.1二元组(V(G),E(G))称为图。其中V(G)是非空集合，称为结点集，E(G)是V(G)诸结点之间边的集合。常用G=(V,E)表示图。我们只讨论有限图,即V和E都是有限集.给定某个图G=(V,E),如果不加特殊说名,就认为:,即结点数,边数.图的概念定义1.1.2G=(V,E)的某结点v所关联的边数称为该结点的度，用d(v)表示。如果v带有自

2、环，则自环对d(v)的贡献为２。图的概念定义1.1.3任意两结点间最多只有一条边，且不存在自环的无向图称为简单图。没有任何边的简单图叫空图，用　表示；任何两个结点间都有边的简单图称为完全图，用表示．　中每个结点的度都是n-1.图的概念性质1.1.1设G=(V,E)有n个结点，m条边，则证明：由于每条边e=(u,v)对结点u和v度的贡献各为１，因此m条边对全部结点的总贡献率为2m.图的概念性质1.1.2G中度为奇数的结点必为偶数个．证明：G中任一结点的度或为偶数或为奇数，设　是度为偶的结点集，　是度为奇的结点集，于是有因此上式左边第二项也为偶数，也即

3、度为奇数的结点必为偶数个图的概念性质1.1.3有向图G中正度之和等于负度之和．这是因为每条边对结点的正，负度贡献各为1.性质1.1.4的边数是n(n-1)/2.证明：　中各结点的度都是(n-1),由性质1.1.1就可以得到图的概念性质1.1.5非空简单图G中一定存在度相同的结点．证明：设在G中不存在孤立结点，则对n个结点的简单图，每个结点度d(v)的取值范围是1~(n-1),由抽屉原理，一定存在两个度相同的结点．若存在一个孤立的结点，亦类似可证．图的概念定义1.1.4如果图G=(V,E)的每条边　　　　　都赋以一个实数　作为该边的权，则称G是赋权图

4、．特别地，如果这些权都是正实数，就称G是正权图．图1.5就是一个正权图．权可以表示该边的长度，时间，费用或者容量等．图的概念定义1.1.5给定G=(V,E)，如果存在另一个G’=(V’,E’),满足V’V，E’E,则称G’是G的一个子图．特别地，如果V’=V,就称G’是G的支撑子图或者生成子图；如果V’V,且E’包含了G在节点子集V’之间的所有边，则称G’是G的导出子图．图的概念定义1.1.6给定两个图G1=(V1,E1),G2=(V2,E2).令G1G2=(V,E),其中V=V1V2,E=E1E2;G1G2=(V,E),其中V=V1

5、V2,E=E1E2;G1G2=(V,E),其中V=V1V2,E=E1E2;分别称为G1和G2的并，交和对称差．图的概念定义1.1.7设v是有向图Ｇ的一个结点，则称为v的直接后继集或者外邻集;相应地称为v的直接前趋集或者内邻集.图的概念在图1.6(a)中：而图1.5中：图的概念定义1.1.8两个图　　　　　　　　如果　和　之间存在双射f,而且,当且仅当,称　和　同构.记假如　　　，则必须满足：(1)．(2)和　结点度的非增序列相同．(3)存在同构的导出子图．