無向グラフの枝に関する半径・直径と直径の上界と下界

IR IR (HANDLE)

Bibliographic Information

Other Title
  • Radius and Diameter with Respect to Edges in a Nondirected Graph, and Upper and Lower Bounds for the Diameter

Search this article

Description

無向グラフGの半径，直径はグラフの基礎概念として良く知られている．この半径r(G)と直径d(G)の間にはr(G)≦d(G)≦2r(G)の不等式が成立することが知られている．これは直径の上界と下界を示しており，しかもこの上界，下界は最良であることも知られている．このグラフの半径，直径は点間の距離によって定義されている量である．一方，グラフでは点の他に枝も重要な構成要素である．ところが，枝に関する半径，直径については従来あまり考察されていないようである．小文では枝に関して定義されるグラフの半径，直径についての一つの考え方を提案する．すなわち，枝間の距離に相当する量をその二つの枝を同時に含むタイセットの最小長さで定義する．そして，その量が三角不等式を満足する準距離となることを示し，点の場合と同様に，枝に関する半径，直径の概念を導入する．さらに，枝に関する直径の上界と下界を示す不等式を導出し，その上界と下界が最良であることも示す．また，枝間の準距離をカットセットを用いて定義された場合についての直径の上界，下界についても同様の結果が得られることも述べる．

Journal

Details 詳細情報について

Report a problem

Back to top