图论与代数结构BasicStudiesinComputingScience图论与代数结构计算机科学基础研究.ppt

图论,第一章基本概念 图的概念,世界上许多事物以及他们之间的联系可以用图形直观地表示.这时人们往往用结点表示事物,用边表示它们之间的联系.这种结点和边构成的图形就是图论所研究的对象.,图的概念,定义1.1.1二元组(V(G),E(G)称为图。其中V(G)是非空集合，称为结点集，E(G)是V(G)诸结点之间边的集合。常用G=(V,E)表示图。我们只讨论有限图,即V和E都是有限集.给定某个图G=(V,E),如果不加特殊说名,就认为:,即结点数,边数.,图的概念,定义1.1.2 G=(V,E)的某结点v所关联的边数称为该结点的度，用d(v)表示。如果v带有自环，则自环对d(v)的贡献为。,图的概念,定义1.1.3 任意两结点间最多只有一条边，且不存在自环的无向图称为简单图。没有任何边的简单图叫空图，用表示；任何两个结点间都有边的简单图称为完全图，用表示中每个结点的度都是n-1.,图的概念,性质1.1.1设G=(V,E)有n个结点，m条边，则证明：由于每条边e=(u,v)对结点u和v度的贡献各为，因此m条边对全部结点的总贡献率为2m.,图的概念,性质1.1.2 G中度为奇数的结点必为偶数个证明：G中任一结点的度或为偶数或为奇数，设是度为偶的结点集，是度为奇的结点集，于是有因此上式左边第二项也为偶数，也即度为奇数的结点必为偶数个,图的概念,性质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是赋权图特别地，如果这些权都是正实数，就称G是正权图图1.5就是一个正权图权可以表示该边的长度，时间，费用或者容量等,图的概念,定义1.1.5给定G=(V,E)，如果存在另一个G=(V,E),满足VV，E E,则称G是G的一个子图特别地，如果V=V,就称G是G的支撑子图或者生成子图；如果VV,且E包含了G在节点子集V之间的所有边，则称G是G的导出子图,图的概念,定义1.1.6 给定两个图G1=(V1,E1),G2=(V2,E2).令 G1G2=(V,E),其中V=V1V2,E=E1E2;G1G2=(V,E),其中V=V1V2,E=E1E2;G1G2=(V,E),其中V=V1 V2,E=E1E2;分别称为G1和G2的并，交和对称差,图的概念,定义1.1.7设v是有向图的一个结点，则 称为v的直接后继集或者外邻集;相应地 称为v的直接前趋集或者内邻集.,图的概念,在图1.6(a)中：而图1.5中：,图的概念,定义1.1.8 两个图如果和之间存在双射f,而且,当且仅当,称和同构.记假如，则必须满足：(1)(2)和 结点度的非增序列相同(3)存在同构的导出子图,