グラフ理論的言い換え - 186 @ hatenablogこの時間帯に書き直しました。 グラフ理論を知っている人用の書き方をすると 直径2かつk-正則グラフの頂点数nの最大値 直径2かつk-正則平面グラフの頂点数nの最大値 を求めたいという問題です。定義から平面グラフか一般のグラフか分からなかったので両方用意しました。 用語説明しておくと、 直径 任意の2頂点間の最短パスの長さの最大値 k-正則 頂点の次数が全てk (各頂点から辺がk本出ているということ) 平面グラフ 頂点を適当に置き換えて辺を伸ばせば、辺が交差することなく平面に書けるということ (K_{3,3}またはK_5を含むとそれはもう平面グラフでは無い) 関連研究, 自明な上限, 具体例 Moore's boundにより, 直径2で最大次数Δのグラフの頂点数の最大値はΔ^2+1が上界であることが知られています。直径をD, 最大次数をΔとしたときの頂点数最大のグラフを構成する問題は、“de
