2020年秋《离散数学》图论测试参考答案1

【离散数学】图论测试涉及的知识点包括图的基本概念、图的代数表示、道路与回路的性质、树和森林的特性以及哈夫曼树的应用。 1. **图的基本概念** - 图分为有向图和无向图，其中无向图的邻接矩阵是对称的。 - 图的生成子图是指一个图中选取一部分顶点及其相互连接的边所构成的新图，而导出子图是去掉一个或多个顶点及与它们相关联的边所得到的图。 - 结点的度分为正度（出度）和负度（入度），在无向图中，每个结点的正度和负度相等，因为每条边连接两个顶点，对两个顶点的度各增加1。 2. **图的代数表示** - 邻接矩阵是图的一种矩阵表示，用于记录图中顶点之间的连接关系，无自环的无向图的邻接矩阵是对角线上元素为0的对称矩阵。 - 关联矩阵也可以表示图，但不能表示自环，而邻接矩阵可以表示自环。 - 结点的度可以通过查看其在邻接矩阵中对应行的非零元素个数来确定。 3. **道路与回路** - 简单道路不允许重复经过同一顶点。 - 极大联通子图是图中最大的部分，使得任何两个顶点之间都存在路径，它是图的一个导出子图。 - 连通支是图中最大的不可再分割的连通部分，对于给定的图，连通支可能不唯一。 - 二分图中的回路是由偶数条边组成的，这是二分图的一个重要特性。 4. **树和森林** - 树的特征之一是删除任意一条边会形成两个不连通的分支。 - 高度为\( k \)的满二叉树的叶子结点个数为\( 2^k - 1 \)。 - 完全二叉树的叶子结点总是位于最低层，但最低层可能不满。 - Huffman树（霍夫曼树）是一种最优二叉树，n个叶子结点的Huffman树共有\( 2n-1 \)个结点。 5. **哈夫曼树与编码** - 哈夫曼编码是基于频率的前缀编码方法，用于数据压缩。给定字符串"ihaveapenihaveanapple"，构建的哈夫曼树的带权路径总长为61。 在测试中，还需要解答实际问题，如画出图并写出其邻接矩阵，以及构造带权重的图并找到最小生成树。最小生成树问题可以通过Prim算法或Kruskal算法解决，它们的目标是找到权值之和最小的生成树。例如，给定无向图的关联矩阵，并为其边赋予权重后，需要找到这个加权图的最小生成树，并计算其所有边的权值之和。 二分图的证明题可能涉及到二分图的定义，即图中任何边的两端点都在不同的集合中，证明可能涉及染色法或反证法，展示图不能被分割成两个互不相交的子集，使得每条边都连接这两个子集的不同顶点。 这些知识点涵盖了图论的基本概念、代数表示、图的结构属性以及树的特性，是离散数学学习的重要组成部分，对理解和解决实际问题至关重要。