先介绍了距离(distance)、直径(diameter)的定义。
例1.5.1 求强连通有向图的直径和顶点数v以及\(\Delta\)(还不清楚它的含义)的关系。
例1.5.2 \(\Delta\)是图的最大度,知道了。这两个例题看起来就是先口语化地分情况讨论,然后分情况计算结果。
说了图的两个度量,最大度和直径。
最大度为\(\Delta\)且直径最多为k的图记为\((\Delta,k)\)图。
前两例中式子给出的\((\Delta,k)\)有向图和\((\Delta,k)\)无向图阶的上界,称为\((\Delta,k)\)-Moore界。
\((\Delta,k)\)-Moore有向图:达到 \((\Delta,k)\)-Moore界的有向图。
\((\Delta,k)\)-Moore无向图:达到 \((\Delta,k)\)-Moore界的无向图。
例1.5.4 连通的无向图,图的度和(图的阶、最小度)之间的数量关系。