基尔霍夫定理可用于查找从连通图中可以形成的生成树的数量。示例矩阵“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 的某些边从同一个图“G”获得，则称它们是同态的。请看下面的例子 -将边“rs”分成两条边，添加一个顶点。下面显示的图与第一个图同态。如果 G1 与 G2 同构，则 G 与 G2 同胚，但反之不一定成立。任何具有 4 个或更少顶点的图都是平面的。任何具有 8 个或更少边的图都是平面的。完全图 Kn 如果是... 阅读更多

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

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

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