自環
 |
在圖論中，自環（Loop）是一條頂點與自身連接的邊。簡單圖中不包含自環。
根據上下文的不同，一個圖或者多重圖可能被定義為允許或不允許擁有自環（通常與允許或不允許擁有重邊一致）：
- 當允許重邊與自環存在於圖中時，沒有重邊或自環的圖通常被稱為「簡單圖」與圖區分開。
- 當不允許重邊與自環存在於圖中時，含有重邊或自環的圖通常被稱為「多重圖」或「偽圖」與圖區分開。
在只有一個頂點的圖中，所有的邊都必須是自環。這種圖叫花束圖。
度
[編輯]自環是其中一個特殊情況，它增加了頂點兩個度。這可以針對自環邊中的每個頂點考慮其相鄰頂點都是自己來理解。換句話說，一個帶有自環的頂點從頂點的兩端「看到」自己是一個相鄰頂點，因此是添加了兩個度而不是一個。
在有向圖中，自環使該頂點的入度與出度均增加一。
參見
[編輯]圖論中的自環
拓撲中的自環
參考文獻
[編輯]- Balakrishnan, V. K.; Graph Theory, McGraw-Hill; 1 edition (February 1, 1997). ISBN 0-07-005489-4.
- Bollobás, Béla; Modern Graph Theory, Springer; 1st edition (August 12, 2002). ISBN 0-387-98488-7.
- Diestel, Reinhard; Graph Theory, Springer; 2nd edition (February 18, 2000). ISBN 0-387-98976-5.
- Gross, Jonathon L, and Yellen, Jay; Graph Theory and Its Applications, CRC Press (December 30, 1998). ISBN 0-8493-3982-0.
- Gross, Jonathon L, and Yellen, Jay; (eds); Handbook of Graph Theory. CRC (December 29, 2003). ISBN 1-58488-090-2.
- Zwillinger, Daniel; CRC Standard Mathematical Tables and Formulae, Chapman & Hall/CRC; 31st edition (November 27, 2002). ISBN 1-58488-291-3.
外部連結
[編輯]
本條目引用的公有領域材料。材料來自NIST的文檔：Black, Paul E. Self loop. 演算法與資料結構辭典.
