离散实验图论与命题逻辑是计算机科学中的基础理论，主要涉及图的性质、逻辑推理以及数据压缩等概念。在这些训练题目中，我们将逐一解析关键知识点。
1. **连通性判断**：在图论中，连通图指的是图中任意两个顶点间都存在路径。对于无向图，如果可以通过路径从一个顶点到达其他所有顶点，则该图是连通的。这里使用邻接矩阵 A 来表示图，A是对称矩阵，其元素随机生成。可达矩阵 P=A+A^2+…+A^n 计算的是从任一顶点出发能到达其他顶点的概率，如果所有对角线元素均为1，那么图是强连通的。
2. **Fleury算法**：欧拉图是图中每条边恰好出现一次的闭合路径，欧拉回路则是从一个顶点出发并返回该顶点的欧拉路径。Fleury算法是一种找到欧拉回路的有效方法，它从一个任意顶点开始，每次选择一条未被使用的边，直到遍历完所有边。在程序实现时，需要先确保每个顶点的度为偶数，并确保图是连通的。
3. **Huffman算法**：Huffman编码是一种数据压缩方法，用于构建最优二叉树，使得带权路径长度最短。给定权重 w1, w2, ..., wt，算法会生成一棵树，其中叶子节点代表原始的权重，内部节点则表示合并的权重。使用一维数组 tree[] 来表示二叉树结构，通过调整树结构，使得最终的编码满足最小带权路径长度。
4. **命题逻辑**：公式 p®(ØpÙqÚr)的类型判断涉及到真值表计算。在命题逻辑中，®代表蕴含，Ø代表否定，Ù代表逻辑或。通过给定的变量赋值，可以计算公式在所有可能情况下的真假值，进而确定公式的类型，如重言式、矛盾式或非平凡式。
5. **逻辑等价**：判断(p®q) Ù (p®r) Ù (p®s)与 p® (qÙrÙs)是否等价，同样通过真值表计算，比较两个公式的计算结果是否在所有情况下都相同。如果在所有可能的变量赋值下，两个公式的真值一致，那么它们就是等价的。
6. **主析取范式与主合取范式转换**：主析取范式（DNF）是逻辑表达式的一种形式，它由若干个子句（每个子句都是若干命题变元的析取）析取得到。主合取范式（CNF）则由若干子句（每个子句是若干命题变元的合取）合取得到。给定一个主析取范式，可以通过布尔代数操作将其转换为等价的主合取范式。在输入和输出时，通常将命题变元用数字表示，联结词用特定字符代替。
以上这些实验涵盖了图论的基本概念，如图的连通性和欧拉路径，数据压缩中的Huffman编码，以及命题逻辑的基本操作，包括逻辑蕴含、逻辑等价和逻辑转换。通过这些实验，学生能够深入理解离散数学中的核心概念，并提高编程解决实际问题的能力。
