頂点1にループを持つグラフグラフ理論において、ループ（自己ループまたはバックルとも呼ばれる）とは、頂点と頂点自身を結ぶ辺のことである。単純グラフにはループは存在しない。
文脈によっては、グラフまたはマルチグラフは、ループの存在を許可するか許可しないかのいずれかとなるように定義される場合がある（多くの場合、同じ頂点間の複数のエッジを許可するか許可しないかと同時に行われる）。
- グラフがループや多重エッジを許容するように定義されている場合、ループや多重エッジを持たないグラフは、他のグラフと区別するために単純グラフと呼ばれることが多い。
- グラフがループや多重辺を禁止するように定義されている場合、ループや多重辺を持つグラフは、これらの制約を満たすグラフと区別するために、多重グラフまたは擬似グラフと呼ばれることが多い。
頂点が1つしかないグラフでは、すべての辺はループでなければなりません。このようなグラフはブーケと呼ばれます。
程度
無向グラフの場合、頂点の次数は隣接する頂点の数に等しい。
ループは特殊なケースで、次数に2が加算されます。これは、ループの辺の各接続点をそれぞれ隣接頂点として数えることで理解できます。つまり、ループを持つ頂点は、辺の両端から見て自身を隣接頂点と「認識」するため、次数に1ではなく2が加算されるのです。
有向グラフの場合、ループは入次数に 1、出次数に 1 を加えます。
参考文献
- Balakrishnan, VK;グラフ理論、McGraw-Hill; 第1版（1997年2月1日）。ISBN 0-07-005489-4。
- ボロバス、ベラ。現代グラフ理論、シュプリンガー;初版（2002年8月12日）。ISBN 0-387-98488-7。
- ラインハルト・ディーステル著『グラフ理論』、シュプリンガー社、第2版（2000年2月18日）。ISBN 0-387-98976-5。
- グロス、ジョナサン・L、イェレン、ジェイ著、『グラフ理論とその応用』、CRC Press（1998年12月30日）。ISBN 0-8493-3982-0。
- グロス、ジョナサン・L、イェレン、ジェイ（編）；グラフ理論ハンドブック。CRC（2003年12月29日）。ISBN 1-58488-090-2。
- ズウィリンガー、ダニエル著；CRC標準数学表と公式集、チャップマン＆ホール/CRC；第31版（2002年11月27日）。ISBN 1-58488-291-3。
この記事は、ポール・E・ブラック著「Self loop」、『Dictionary of Algorithms and Data Structures』、NIST のパブリックドメイン資料を組み込んでいます。