基尔霍夫定理用于寻找可以从连通图中形成的生成树的数量。示例矩阵“A”填充如下：如果两个顶点之间存在边，则应将其设置为“1”，否则为“0”。

同构如果两个图 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 的一些边用更多顶点划分来获得，则称这两个图是同态的。请看下面的例子 - 通过添加一个顶点将边“rs”分成两条边。以下所示的图与第一个图同态。如果 G1 与 G2 同构，则 G 与 G2 同胚，但反过来不一定成立。任何具有 4 个或更少顶点的图都是平面的。任何具有 8 个或更少边的图都是平面的。完全图 Kn 是平面的，如果... 阅读更多

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

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

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