同构如果两个图 G 和 H 包含相同数量的顶点并以相同的方式连接，则称它们为同构图（表示为 G ≅ H）。检查非同构比检查同构更容易。如果出现以下任何条件，则两个图是非同构的 -连通分量的数量不同顶点集的基数不同边集的基数不同度数序列不同示例以下图是同构的 -同态从图 G 到图 H 的同态是映射（可能不是双射映射）h: G → H，使得 - (x, y) ∈ E(G) → (h(x), h(y)) ∈ ... 阅读更多

树是一种离散结构，表示各个元素或节点之间的层次关系。其中父节点最多有两个子节点的树称为二叉树。树及其属性定义 - 树是连通的无环无向图。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” ... 阅读更多