树是一种离散结构，它表示各个元素或节点之间的层次关系。其中父节点最多只有两个子节点的树称为二叉树。树及其性质定义 - 树是一个连通的无环无向图。图 G 中每对顶点之间都有一条唯一的路径。具有 N 个顶点的树包含 (N-1) 条边。度为 0 的顶点称为树的根。度为 1 的顶点称为树的叶节点，内部节点的度…… 阅读更多

哈密顿图 - 如果存在一个包含图 G 的每个顶点的环，则连通图 G 称为哈密顿图，该环称为哈密顿环。图 G 中的哈密顿通路是一条恰好经过每个顶点一次的通路。狄拉克定理 - 如果 G 是一个具有 n 个顶点的简单图，其中 n ≥ 3，如果每个顶点 v 的 deg(v) ≥ {n}/{2}，则图 G 是哈密顿图。奥尔定理 - 如果 G 是一个具有 n 个顶点的简单图，其中 n ≥ 2，如果对于每一对不相邻的顶点 x 和 y，deg(x) + deg(y) ≥ n，则…… 阅读更多

根据顶点数、边数、互连性和整体结构的不同，图有多种类型。本章只讨论几种重要的图类型。空图没有边的图称为空图。示例在上图中，有三个顶点，名为“a”、“b”和“c”，但它们之间没有边。因此它是一个空图。平凡图只有一个顶点的图称为平凡图。示例在上图中，只有一个顶点“a”，没有其他边。因此它是一个平凡图。非定向…… 阅读更多

图可以以不同的形式存在，具有相同的顶点数、边数以及相同的边连接性。这样的图称为同构图。请注意，本章中我们主要标记图是为了便于参考和区分它们。同构图如果两个图 G1 和 G2 满足以下条件，则它们被称为同构 - 它们的组成部分（顶点和边）数量相同。它们的边连接性保持不变。注意 - 简而言之，在两个同构图中，一个是另一个的修改版本。未标记图也可以被认为是…… 阅读更多

如果两个图 G1 和 G2 可以通过在 G 的一些边中添加更多顶点来从同一个图“G”获得，则称它们为同态。请看下面的例子 - 通过添加一个顶点将边“rs”分成两条边。下面显示的图与第一个图同态。如果 G1 与 G2 同构，则 G 与 G2 同胚，但反之则不然。任何具有 4 个或更少顶点的图都是平面的。任何具有 8 个或更少边的图都是平面的。完全图 Kn 是平面图，如果…… 阅读更多

图具有各种性质，这些性质用于根据其结构对图进行表征。这些性质是用图论领域中的特定术语定义的。在本章中，我们将讨论一些所有图中都通用的基本性质。连通图的半径所有顶点中的最小离心率被认为是图 G 的半径。顶点到所有其他顶点之间所有最大距离中的最小值被认为是图 G 的半径。符号 - r(G)在图中所有顶点的离心率中，…… 阅读更多

图是点和连接到点的线的图。它至少有一条线连接一组两个顶点，没有顶点连接自身。图论中的图的概念建立在一些基本术语之上，例如点、线、顶点、边、顶点的度、图的性质等。在本章中，我们将介绍这些图论的基础知识。点点是一维、二维或三维空间中的特定位置。为了更好地理解，可以用字母表示一个点。可以用点表示它。示例这里，点…… 阅读更多

欧拉图 - 如果存在一个包含图 G 的每条边的闭合轨迹，则连通图 G 称为欧拉图。欧拉路径 - 欧拉路径是一条恰好使用图的每条边一次的路径。欧拉路径的起点和终点不同。欧拉回路 - 欧拉回路是一个恰好使用图的每条边一次的回路。欧拉回路总是从同一个顶点开始和结束。当且仅当 G 的所有顶点都是偶数度时，连通图 G 是欧拉图，…… 阅读更多

集合 S 的基数，记为 |S|，是集合的元素个数。这个数字也称为基数。如果一个集合有无限多个元素，则其基数为 ∞。示例 - |{1, 4, 3, 5}| = 4，|{1, 2, 3, 4, 5, ....}| = ∞如果存在两个集合 X 和 Y，|X| = |Y| 表示两个集合 X 和 Y 具有相同的基数。当 X 中的元素个数恰好等于 Y 中的元素个数时，就会发生这种情况。在这种情况下，存在一个双射函数“f”…… 阅读更多

图着色是将颜色分配给图 G 的每个顶点的过程，这样相邻的顶点不会获得相同的颜色。目标是在着色图时最小化颜色数量。对图 G 着色所需的最小颜色数称为该图的色数。图着色问题是一个 NP 完全问题。图着色方法对具有 n 个顶点的图 G 着色的步骤如下 - 步骤 1 - 按某种顺序排列图的顶点。步骤 2 - 选择第一个…… 阅读更多