度-直徑問題是圖論中一個問題，目的在定下最大直徑k及最大度數d後，找出擁有最多節點的圖。
假設圖以G=(V,E)表示，某節點的度數以\deg(v)表示，節點之間的最短距離以d(u,v)表示，則度-直徑問題是規定了
:d \ge \max_{v\in V} \deg(v)
:k \ge \max_{u,v\in V} d(u,v)
求出圖G。G的大小（以節點數衡量）受制於摩爾上限，亦即節點的數目不可能多於
:1+d\sum_{i=0}^{k-1}(d-1)^i
已知在k > 1和d > 2的情況下，只有佩特森圖和，以及一個k=2、d=57的圖能達到摩爾上限，一般情況下，圖的節點數目遠少於摩爾上限所指定。
參考文獻
*
*
*
*
外部連結
评论 (0)