半徑(圖論中的半徑)

半徑(圖論中的半徑)

本詞條是多義詞,共4個義項
更多義項 ▼ 收起列表 ▲

離散數學對半徑的定義與幾何數學中的定義相似但不相同。

在離散數學的圖論部分中,半徑是指圖上的“中心點”(中心點可以不只一個)在可到達任意一點需要的最小值。當存在無法到達的情況,則視為∞。當該圖的邊沒有附加權重時,兩點之間的距離為1,且半徑不一定等於直徑的一半。

基本介紹

  • 中文名:半徑
  • 外文名:radius
  • 適用領域:圖論
  • 所屬學科離散數學
定義,性質,

定義

一個頂點位於圖𝐺的中心,如果它與其他頂點的最大距離最小,則該最大距離為圖𝐺的半徑,用rad(G)表示。

性質

rad(G)≤diam(G)≤2rad(G)
diam(G)表示圖G的直徑,即圖G最長的path
圖的半徑和最大度可以控制圖的規模。
當半徑為r,最大度為x(x≥3)時,圖的點數小於
半徑
半徑

相關詞條

熱門詞條

聯絡我們