图论 - 基本属性
图具有各种属性，这些属性可用于根据图的结构来表征图。这些属性以与图论领域相关的特定术语来定义。在本章中，我们将讨论所有图中常见的一些基本属性。
两个顶点之间的距离
它是顶点 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，则
