同构如果两个图 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，则图 G 是哈密顿图。... 阅读更多

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

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

如果这两个图都可以通过用更多顶点划分 G 的一些边从同一个图“G”获得，则两个图 G1 和 G2 被称为同态。请看下面的例子：通过添加一个顶点将边“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”… 阅读更多