圖的屬性

圖具有各種屬性，這些屬性用於根據圖的結構對其進行表徵。這些屬性以與圖論領域相關的特定術語定義。在本章中，我們將討論一些所有圖中常見的基本屬性。

連通圖的半徑

所有頂點的最小離心率被認為是圖 G 的半徑。所有頂點到所有其他頂點之間最大距離中的最小值被認為是圖 G 的半徑。

符號 − r(G)

在圖中所有頂點的離心率中，連通圖的半徑是所有這些離心率中的最小值。

示例 − 在上圖中，r(G) = 2，這是“d”的最小離心率。

圖的直徑

所有頂點的最大離心率被認為是圖 G 的直徑。所有頂點到所有其他頂點之間距離中的最大值被認為是圖 G 的直徑。

符號 − d(G)

在圖中所有頂點的離心率中，連通圖的直徑是所有這些離心率中的最大值。

示例 − 在上圖中，d(G) = 3；這是最大離心率。

中心點

如果圖的離心率等於其半徑，則稱為圖的中心點。如果

e(V) = r(V)，

則“V”是圖“G”的中心點。

示例 − 在示例圖中，“d”是圖的中心點。

e(d) = r(d) = 2

中心

“G”的所有中心點的集合稱為圖的中心。

示例 − 在示例圖中，“{‘d’}”是圖的中心。

周長

“G”中最長環中的邊數稱為“G”的周長。

示例 − 在示例圖中，周長為 6，我們從最長環 a-c-f-g-e-b-a 或 a-c-f-d-e-b-a 推匯出來。

圍長

“G”中最短環中的邊數稱為其圍長。

符號 − g(G)。

示例 − 在示例圖中，圖的圍長為 4，我們從最短環 a-c-f-d-a 或 d-f-g-e-d 或 a-b-e-d-a 推匯出來。

Mahesh Parahar

更新於： 2019年8月23日

1K+ 瀏覽量

開啟你的 職業生涯

透過完成課程獲得認證

開始學習