正則圖
正則圖是每個頂點都有相同數目的鄰居的圖,即每個頂點的度相同。若每個頂點的度均為,稱為-正則圖。
0-正則圖是沒有邊的圖。1-正則圖由不相連的邊組成。2-正則圖由不相連的圈組成。3-正則圖稱為立方圖或三次圖。階為的-正則圖是完全圖。
在強正則圖,每對相鄰頂點都有相同數目 l 的共同鄰居,每對非相鄰頂點也有相同數目 m 節共同鄰居。最小的正則而非強正則的圖是6個頂點的環狀圖或圈。
- 0-正则图
- 1-正则图
- 2-正则图
- 3-正则图
性質
- 對於每個圖及每個不小於的最大度整數,存在一個有作子圖的-正則圖。
- 若有階為的-正則圖,k是偶數或n是偶數。
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.