圖論中,自環Loop)是一條頂點與自身連接的簡單圖中不包含自環。

頂點1含有自環的圖

根據上下文的不同,一個或者多重圖可能被定義為允許或不允許擁有自環(通常與允許或不允許擁有重邊一致):

  • 當允許重邊與自環存在於圖中時,沒有重邊或自環的圖通常被稱為「簡單圖」與圖區分開。
  • 當不允許重邊與自環存在於圖中時,含有重邊或自環的圖通常被稱為「多重圖」或「偽圖」與圖區分開。

在只有一個頂點的圖中,所有的邊都必須是自環。這種圖叫花束圖

無向圖中,頂點的等於相鄰頂點的個數。

自環是其中一個特殊情況,它增加了頂點兩個度。這可以針對自環邊中的每個頂點考慮其相鄰頂點都是自己來理解。換句話說,一個帶有自環的頂點從頂點的兩端「看到」自己是一個相鄰頂點,因此是添加了兩個度而不是一個。

有向圖中,自環使該頂點的入度與出度均增加一。

參見

編輯

圖論中的自環

拓撲中的自環

參考文獻

編輯
  • 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.

外部連結

編輯