图论16--距离、直径

原创
2022/05/09 10:04
阅读数 1.4K

先介绍了距离(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 连通的无向图,图的度和(图的阶、最小度)之间的数量关系。

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
0 评论
0 收藏
0
分享
返回顶部
顶部