北航面试技巧：理解离散数学与图论概念

本文档涉及多个IT领域的知识点，包括但不限于： 1. **离散数学基础**： - 旋转矩阵：旋转矩阵是一种特殊的线性变换矩阵，在数学中用于描述二维空间中的旋转操作，它保持了向量的大小不变，仅改变方向，且对称性决定了其手性。在计算机图形学和图像处理中，旋转矩阵有着广泛应用。 2. **图论概念**： - 无向图的基本属性：无向图的总度数（每个顶点的边的数量之和）等于边数的两倍。 - 图的存储结构： - 邻接矩阵：用于表示图的邻接关系，优点是查询方便，但占用较多内存，不适合大规模稀疏图。 - 邻接表：空间效率高，适合表示稀疏图，但在极端情况下可能占用较大空间。 - 链式前向星和Vector邻接表：是邻接表的不同实现方式，适应不同场景下的查询性能优化。 3. **连通图分析**： - 连通图：任意两个顶点间存在路径的图，至少有一个路径相连。 - 强连通图：有向图中，任意两个顶点间可以双向通信，即存在从A到B和从B到A的路径。 - 极大连通子图：一个连通图中最大的连通子图，其他顶点添加后将不再是连通的。 - 连通分量：非连通图的各个互不相通的最大连通部分。 - 极小连通子图：连通图中不可或缺的最小连通子图，通常指生成树。 4. **算法与逻辑**： - 判断连通性的方法：深度优先搜索（DFS）和广度优先搜索（BFS）是常用图遍历算法，用于检查图是否连通。 - 主析取范式（CNF）和合取范式（DNF）：在逻辑代数中，命题逻辑的形式化表示，分别由有限个简单合取和析取式组成，是理论计算和自动推理的重要工具。 - 极小项和极大项：逻辑表达式的基本构成单元，由命题变元及其否定构成，它们在布尔代数和电路设计中有关键作用。 这些知识点在计算机科学特别是算法、数据结构、图形学和逻辑电路设计等领域都有实际应用，对于理解和解决实际问题有着重要的指导意义。在进行北航面试时，可能会针对这些内容进行深入讨论，以考察学生的理论知识和解决问题的能力。