设 '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 ≠ a_2$ 则 $f(a1) ≠ f(a2)$。示例$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 ... 阅读更多

邻接矩阵邻接矩阵用于表示图。我们可以使用邻接矩阵表示有向图和无向图。以下是邻接矩阵的关键属性。属性邻接矩阵 A[V][V] 是大小为 V × V 的二维数组，其中 V 是无向图中顶点的数量。如果 Vx 和 Vy 之间存在边，则 A[Vx][Vy] = 1 且 A[Vy][Vx]=1，否则值为零。对于有向图，如果 Vx 和 Vy 之间存在边，则 A[Vx][Vy]=1，否则值为零。邻接矩阵…… 阅读更多

为了对量化语句得出结论，有四个推理规则，统称为谓词演算的推理理论。推理规则表推理规则名称$$\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)$。规则…… 阅读更多