图论的基本属性

图论的属性基本上用于根据图的结构来描述图。以下是图论的一些基本属性

1 两个顶点之间的距离

距离 基本上是顶点 X 和顶点 Y 之间最短路径中的边数。如果存在连接两个顶点的多条路径，则最短路径被认为是两个顶点之间的距离。两个顶点之间的距离用 d(X, Y) 表示。

示例

假设，我们想找到顶点 B 和 D 之间的距离，那么首先我们必须找到顶点 B 和 D 之间的最短路径。

从顶点 B 到顶点 D 有很多路径

• B -> C -> A -> D，长度 = 3
• B -> D，长度 = 1（最短路径）
• B -> A -> D，长度 = 2
• B -> C -> D，长度 = 2
• B -> C -> A -> D，长度 = 3

因此，顶点 B 和顶点 D 之间的最小距离为 1。

2. 顶点的离心率

顶点的离心率 是一个顶点到所有其他顶点的最大距离。 它用 e(V) 表示。

要计算顶点的离心率，我们必须找到从一个顶点到所有其他顶点的距离，并且最大距离是该特定顶点的离心率。

示例

在上面的例子中，如果我们想找到顶点“a”的最大离心率，那么

• 从顶点 a 到 b 的距离是 1（即 ab）
• 从顶点 a 到 c 的距离是 1（即 ac）
• 从顶点 a 到 f 的距离是 2（即 ac -> cf 或 ad -> df）
• 从顶点 a 到 d 的距离是 1（即 ad）
• 从顶点 a 到 e 的距离是 2（即 ab -> be 或 ad -> de）
• 从顶点 a 到 g 的距离是 3（即 ab -> be -> eg 或 ac -> cf -> fg 等）

因此，顶点“a”的最大离心率是 3，这是从顶点“a”到所有其他顶点的最大距离。

类似地，给定图的其他顶点的最大离心率是

• e(b) = 3
• e(c) = 3
• e(d) = 2
• e(e) = 3
• e(f) = 3
• e(g) = 3

3. 连接图的半径

连接图的半径是所有顶点中最小的离心率。 换句话说，顶点到所有其他顶点之间的所有距离中的最小值称为图的半径。 它用 r(G) 表示。

示例

从示例 5.2 可以看出，r(G) = 2，这是顶点“d”的最小离心率。

4. 图的直径

图的直径是所有顶点中最大的离心率。换句话说，顶点到所有其他顶点之间的所有距离中的最大值被认为是图 G 的直径。它用 d(G) 表示。

示例

从上面的例子中，如果我们看到图中所有顶点的离心率，我们会看到图的直径是所有这些离心率中的最大值。

图的直径 d(G) = 3，这是最大离心率。

5. 中心点

如果图的离心率等于其半径，则称为图的中心点。

或

如果 r(V) = e(V)，则 V 是图 G 的中心点。

示例

从上面的例子中，“d”是图的中心点。即

6. 中心

图的所有中心点的集合称为图的中心。

示例

从示例 5.2 中，{'d'} 是图的中心。

7. 周长

图 G 的最长循环中的边总数称为 G 的周长。

示例

在上面的例子中，周长是 6，它来自最长路径 a -> c -> f -> g -> e -> b -> a 或 a -> c -> f -> d -> e -> b -> a。

8. 围长

图 G 的最短循环中的边总数称为围长。它用 g(G) 表示。

示例

在上面的例子中，图的围长是 4，它来自最短循环 a -> c -> f -> d -> a、d -> f -> g -> e -> d 或 a -> b -> e -> d -> a。

9. 顶点度数和定理

对于非定向图 G = (V,E)，其中顶点集 V = {V1, V2, .... Vn}，则，

换句话说，对于任何图，顶点度数之和等于边数的两倍。

推论 1

对于有向图 G = (V, E)，其中顶点集 V = {V1, V2, ... Vn}，则，

推论 2

在任何具有奇数度的非定向图中，顶点的数量是偶数。

示例

不可能创建一个顶点数 v = 6 的图，其中顶点的度数为 1, 2, 2, 3, 3, 4。这是因为度数之和 deg(V) 是，

推论 3

在非定向图中，如果每个顶点的度数为 k，则

推论 4

如果非定向图中每个顶点的度数至少为 k，则

推论 5

如果非定向图中每个顶点的度数最多为 k，则