图着色不过是用标签标记图的组成部分（如顶点、边和区域）的一种简单方法，需满足某些约束条件。在一个图中，没有两个相邻的顶点、相邻的边或相邻的区域用最少数量的颜色着色。这个数字称为色数，该图称为正确着色的图。在图着色过程中，对图设置的约束条件包括颜色、着色顺序、颜色分配方式等。颜色赋予顶点或特定区域。因此，具有相同颜色的顶点或区域构成独立集。顶点着色顶点……阅读更多

数学逻辑规则规定了推理数学语句的方法。古希腊哲学家亚里士多德是逻辑推理的先驱。逻辑推理为许多数学领域以及计算机科学提供了理论基础。它在计算机科学中有很多实际应用，例如计算机器的设计、人工智能、编程语言的数据结构定义等。主要类别数学逻辑可以大致分为三类。命题逻辑 - 命题逻辑关注的是可以赋予“真”和“假”真值的语句。其目的是分析这些语句，无论是单独分析还是组合分析。谓词……阅读更多

设 'G' 是一个具有 'n' 个顶点和 'm' 条边的连通图。G 的生成树 'T' 包含 (n-1) 条边。因此，为了得到生成树，你需要从 'G' 中删除的边数 = m-(n-1)，这称为 G 的回路秩。这个公式是正确的，因为在一个生成树中，你需要有 'n-1' 条边。在 'm' 条边中，你需要在图中保留 'n–1' 条边。因此，从 'm' 中删除 'n–1' 条边得到为了获得生成树而需要从图中删除的边，这些边不应该形成……阅读更多

树的中心是偏心率最小的顶点。树 G 中顶点 X 的偏心率是顶点 X 与树的任何其他顶点之间的最大距离。最大偏心率是树的直径。如果树只有一个中心，则称为中心树；如果树有多个中心，则称为双中心树。每棵树要么是中心树，要么是双中心树。查找树的中心和双中心的算法步骤 1 - 从给定的树中删除所有度为 1 的顶点，并……阅读更多

二分图 - 如果图 G 的顶点集可以分成两个不相交的集合 V1 和 V2，使得图中的每条边都连接 V1 中的一个顶点和 V2 中的一个顶点，并且 G 中没有边连接 V1 中的两个顶点或 V2 中的两个顶点，则图 G 称为二分图。完全二分图 - 完全二分图是一个二分图，其中第一组中的每个顶点都与第二组中的每个顶点连接。……阅读更多

图是一组点，称为节点或顶点，它们通过一组称为边的线相互连接。图的研究，或图论，是数学、工程和计算机科学领域许多学科的重要组成部分。图论定义 - 图（表示为 G = (V, E)）由一组非空顶点或节点 V 和一组边 E 组成。顶点 a 代表边的端点。边连接两个顶点 a、b，并由它连接的顶点集表示。示例 - 让我们……阅读更多

单射/一对一函数函数 $f: A \rightarrow B$ 是单射或一对一函数，如果对于每个 $b \in B$，最多存在一个 $a \in A$ 使得 $f(s) = t$。这意味着如果 $a_1 e a_2$ 意味着 $f(a1) e f(a2)$，则函数 f 是单射的。示例$f: N \rightarrow N, f(x) = 5x$ 是单射的。$f: N \rightarrow N, f(x) = x^2$ 是单射的。$f: R\rightarrow R, f(x) = x^2$ 不是单射的，因为 $(-x)^2 = x^2$满射/到函数函数 $f: A \rightarrow B$ 是满射（到），如果 f 的像等于其值域。等价地，对于每个 $b \in B$，……阅读更多

为了对量化语句得出结论，有四个推理规则，它们统称为谓词演算的推理理论。推理规则表推理规则名称$$\begin{matrix} \forall x P(x) \ \hline \therefore P(y) \end{matrix}$$规则 US：全称指定$$\begin{matrix} P(c) \text { 对于任何 c} \ \hline \therefore \forall x P(x) \end{matrix}$$规则 UG：全称泛化$$\begin{matrix} \exists x P(x) \ \hline \therefore P(c) \text { 对于任何 c} \ \end{matrix}$$规则 ES：存在指定$$\begin{matrix} P(c) \text { 对于任何 c} \ \therefore \exists x P(x) \end{matrix}$$规则 EG：存在泛化规则 US：全称指定 - 从 $(x)P(x)$，可以得出 $P(y)$。规则 US：……阅读更多

独立集用集合表示，其中任何两条边都不相邻。任何两条边之间都不能有公共顶点。任何两个顶点都不能相邻。任何两个顶点之间都不能有公共边。独立线集设 'G' = (V, E) 为一个图。E 的子集 L 称为 'G' 的独立线集，如果 L 中的任何两条边都不相邻。这样的集合称为独立线集。示例让我们考虑以下子集 -L1 = {a, b} L2 = {a, b}……阅读更多

独立集用集合表示，其中任何两条边都不相邻。任何两条边之间都不能有公共顶点。任何两个顶点都不能相邻。任何两个顶点之间都不能有公共边。独立顶点集设 'G' = (V, E) 为一个图。'V' 的子集称为 'G' 的独立集，如果 'S' 中的任何两个顶点都不相邻。示例考虑上述图中的以下子集 -S1 = {e} S2 = {e, f} S3 = {a, g, c} S4 = {e, d}显然，S1……阅读更多