複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/正則圖/10038215
複製
複製成功

正則圖

鎖定
正則圖是指各頂點的度均相同的無向簡單圖。
在圖論中，正則圖中每個頂點具有相同數量的鄰點； 即每個頂點具有相同的度或價態。 正則的有向圖也必須滿足更多的條件，即每個頂點的內外自由度都要彼此相等。具有k個自由度的頂點的正則圖被稱為k度的k-正則圖。 此外，奇數程度的正則圖形將包含偶數個頂點。
中文名
正則圖
外文名
regular graph
學    科
數學
定    義
各頂點的度均相同的無向簡單圖
性    質
每個頂點具有相同數量的鄰點
相關名詞
無向簡單圖

目錄

  1. 1 簡介
  2. 2 存在性
  3. 3 代數屬性

正則圖簡介

正則圖是指各頂點的度均相同的無向簡單圖。
在圖論中，正則圖中每個頂點具有相同數量的鄰點； 即每個頂點具有相同的度或價態。正則的有向圖也必須滿足更多的條件，即每個頂點的內外自由度都要彼此相等。具有k個自由度的頂點的正則圖被稱為k度的k-正則圖。 此外，奇數程度的正則圖形將包含偶數個頂點。 [1-2] 
最多2個等級的正則圖很容易分類：0-正則圖由斷開的頂點組成，1-正則圖由斷開的邊緣組成，2-正則圖由斷開的循環和無限鏈組成，3-正則圖被稱為立方圖。
強規則圖也是常規圖，其中每個相鄰的頂點對具有相同數量的相鄰的相鄰數目，並且每個不相鄰的頂點對具有相同數量的n個相鄰的相鄰公共點。 常規但不太規則的最小圖是循環圖和6個頂點的循環圖。
對於任何Km，完整的圖m是強規則的。
納什 - 威廉姆斯的一個定理説，2k + 1個頂點上的每個k-常規圖都有一個哈密爾頓算子。
0-正則圖 0-正則圖
1-正則圖 1-正則圖
2-正則圖 2-正則圖

正則圖存在性

眾所周知，k正則圖存在的必要和充分條件是n≥k+1並且nk是偶數。 在這種情況下，通過考慮循環圖的適當參數，可以很容易地構建正則圖。 [3] 

正則圖代數屬性

令A成為正則圖的相鄰矩陣。 然後，當且僅當j={1,1,1,1,1,1}是A的特徵向量時，這個圖才是正則的。 其特徵值將是圖的不變自由度。 對應於其他特徵值的特徵向量與j正交，因此對於這樣的特徵向量v=（v1,v2......vn），我們有，
當且僅當特徵值k具有多重性k時， “唯一的”方向是門階 - 弗羅貝紐斯定理的結果。
還有一個正則和連接圖的標準：當且僅當一個J的矩陣與Jij=1時， 圖的相鄰代數（意思是A的冪的線性組合）。令G為具有直徑D和相鄰矩陣的特徵值的k正則圖 [4] 
如果G不是二分的話
參考資料
  • 1.    Chen, Wai-Kai (1997). Graph Theory and its Engineering Applications. World Scientific. p. 29. ISBN 978-981-02-1859-1.
  • 2.    Cvetković, D. M.; Doob, M.; and Sachs, H. Spectra of Graphs: Theory and Applications, 3rd rev. enl. ed. New York: Wiley, 1998.
  • 3.    Curtin, Brian (2005), "Algebraic characterizations of graph regularity conditions", Designs, Codes and Cryptography, 34 (2-3): 241–248, MR 2128333, doi:10.1007/s10623-004-4857-4.
  • 4.    Meringer, Markus (1999). "Fast generation of regular graphs and construction of cages" (PDF). Journal of Graph Theory. 30 (2): 137–146. doi:10.1002/(SICI)1097-0118(199902)30:21.0.CO;2-G.