图论 - 基本性质
图具有各种属性，这些属性用于根据图的结构对其进行表征。这些属性以与图论领域相关的特定术语定义。在本章中，我们将讨论一些所有图中都常见的基本属性。
两个顶点之间的距离
它是顶点 U 和顶点 V 之间最短路径上的边数。如果有多条路径连接两个顶点，则最短路径被视为这两个顶点之间的距离。
符号 - d(U,V)
从一个顶点到另一个顶点可能存在任意数量的路径。在其中，您只需要选择最短的一条。
例子
看一下下面的图 -
这里，从顶点“d”到顶点“e”或简称为“de”的距离为 1，因为它们之间有一条边。从顶点“d”到顶点“e”有很多路径 -
- da, ab, be
- df, fg, ge
- de（它被认为是顶点之间的距离）
- df, fc, ca, ab, be
- da, ac, cf, fg, ge
顶点的离心率
从一个顶点到所有其他顶点的最大距离被认为是该顶点的离心率。
符号 - e(V)
取从特定顶点到图中所有其他顶点的距离，在这些距离中，离心率是距离中最高的。
例子
在上图中，“a”的离心率为 3。
从“a”到“b”的距离为 1（'ab'），
从“a”到“c”的距离为 1（'ac'），
从“a”到“d”的距离为 1（'ad'），
从“a”到“e”的距离为 2（'ab'-'be'）或（'ad'-'de'），
从“a”到“f”的距离为 2（'ac'-'cf'）或（'ad'-'df'），
从“a”到“g”的距离为 3（'ac'-'cf'-'fg'）或（'ad'-'df'-'fg'）。
因此离心率为 3，这是从顶点“a”到距离最大的“ag”之间的最大值。
换句话说，
e(b) = 3
e(c) = 3
e(d) = 2
e(e) = 3
e(f) = 3
e(g) = 3
连通图的半径
所有顶点中最小离心率被认为是图 G 的半径。所有顶点到所有其他顶点的最大距离中的最小值被认为是图 G 的半径。
符号 - r(G)
在图中所有顶点的离心率中，连通图的半径是所有这些离心率中的最小值。
例子
在上图中，r(G) = 2，这是“d”的最小离心率。
图的直径
所有顶点中最大离心率被认为是图 G 的直径。所有顶点到所有其他顶点的距离中的最大值被认为是图 G 的直径。
**符号 - d(G)** - 在图中所有顶点的离心率中，连通图的直径是所有这些离心率中的最大值。
例子
在上图中，d(G) = 3；这是最大离心率。
中心点
如果图的离心率等于其半径，则称为图的中心点。如果
e(V) = r(V),
则“V”是图“G”的中心点。
例子
在示例图中，“d”是图的中心点。
e(d) = r(d) = 2
中心
“G”的所有中心点的集合称为图的中心。
例子
在示例图中，{'d'} 是图的中心。
周长
**“G”的最长环中的边数**称为“G”的周长。
例子
在示例图中，周长为 6，我们从最长环 a-c-f-g-e-b-a 或 a-c-f-d-e-b-a 中推导出。
圈数
“G”的最短环中的边数称为其圈数。
**符号：**g(G)。
**示例** - 在示例图中，图的圈数为 4，我们从最短环 a-c-f-d-a 或 d-f-g-e-d 或 a-b-e-d-a 中推导出。
顶点度数和定理
如果 G = (V, E) 是一个具有顶点 V = {V1, V2,…Vn} 的无向图，则
推论 1
如果 G = (V, E) 是一个具有顶点 V = {V1, V2,…Vn} 的有向图，则
推论 2
在任何无向图中，具有奇数度的顶点数为偶数。
推论 3
在无向图中，如果每个顶点的度数为 k，则
推论 4
在无向图中，如果每个顶点的度数至少为 k，则
| 推论 5
在无向图中，如果每个顶点的度数至多为 k，则