湖南大学离散数学图论PPT课件.pptx

离散数学中的图论是计算机科学和数学的一个重要分支，主要研究由节点和连接这些节点的边构成的抽象结构。湖南大学的这个PPT课件深入介绍了图的概念及其相关属性。 图被定义为一个三元组 (V(G),E(G),M(E,V))，其中V(G)代表节点集合，非空且表示图中的顶点，E(G)表示边的集合，而M(E,V)描述了边与节点之间的连接关系。在实际应用中，通常简化为二元组 (V(G),E(G))，记作G=(V,E)，这足以描述图的基本结构。 图的类型分为有向图和无向图。在有向图中，边具有方向性，例如从节点vi到vj的边表示为a(i,j)=1，但反向的边不一定会存在，因此邻接矩阵可能不对称。而在无向图中，边没有方向，若节点vi与vj之间有边，则a(i,j)=1，因为无向图的边总是成对出现，所以邻接矩阵是对称的。 图还可以通过邻接矩阵或关联矩阵来表示。邻接矩阵直接表示节点间的连接，有向图的邻接矩阵元素a(i,j)为1表示有从vi到vj的边，而关联矩阵则表示节点与边的关系，有向图中如果Vi是ej的起点，则b(i,j)=1，若是终点则b(i,j)=-1。 此外，图可以是有环的或无环的，有环意味着存在一条边形成闭合路径。自环是节点与其自身相连的边，而在关联矩阵中无法表示自环，但可以表示重边，即同一对节点间有多条边。 图的一些关键性质包括度数，度数指的是一个节点关联的边的数量。在一个无向图中，节点的入度（负边）和出度（正边）之和等于其度数，即d入(A) + d出(A) = d(A)。握手定理指出，所有节点的度数之和等于边数的两倍，这是因为每条边连接两个节点，因此每增加一条边会使得两个节点的度数各增加1。 一个重要的观察是，图中度数为奇数的节点数量必须是偶数。这是因为每条边都会使得一个节点的度数增加1，所以如果图中总共有奇数条边，那么度数为奇数的节点数量也必须是奇数，这样才能保持所有节点的度数和为偶数，即2m。 总结来说，图论是离散数学的基础，它的概念和性质广泛应用于网络分析、数据结构、算法设计等多个领域。湖南大学的这个PPT课件详尽地涵盖了图的基本定义、不同类型、表示方法以及一些关键性质，为学习者提供了扎实的理论基础。