頂点1にループを持つグラフ

グラフ理論において、ループ（自己ループまたはバックルとも呼ばれる）とは、頂点を自身に接続する辺のことである。単純グラ​​フにはループは含まれない。

コンテキストに応じて、グラフまたはマルチグラフは、ループの存在を許可するか禁止するか（多くの場合、同じ頂点間の 複数のエッジを許可するか禁止するかと連動）を定義することができます。

  • グラフはループと多重エッジを許容するように定義されますが、ループや多重エッジのないグラフは、単純グラフと呼んで他のグラフと区別されることがよくあります。
  • グラフがループや多重エッジを許可しないように定義されている場合、ループや多重エッジを持つグラフは、マルチグラフまたは擬似グラフと呼ばれることで、これらの制約を満たすグラフと区別されることがよくあります。

頂点が1つのグラフでは、すべての辺は必ずループになります。このようなグラフはブーケと呼ばれます。

程度

無向グラフの場合、頂点の次数は隣接する頂点の数に等しくなります。

特別なケースとしてループがあり、これは次数に2を加えます。これは、ループ辺の各接続を自身の隣接頂点としてカウントすることで理解できます。言い換えれば、ループを持つ頂点は、辺の両端から自身を隣接頂点として「認識」するため、次数に1ではなく2を加えます。

有向グラフの場合、ループは入力次数に 1 を追加し、出力次数に 1 を追加します。

参照

グラフ理論では

位相幾何学において

参考文献

  • Balakrishnan, VK; Graph Theory , 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。
  • Gross, Jonathon L.、Yellen, Jay; (編); Handbook of Graph Theory . CRC (2003年12月29日). ISBN 1-58488-090-2。
  • ダニエル・ツヴィリンガー著『CRC標準数学表と公式』チャップマン＆ホール／CRC刊、第31版（2002年11月27日）。ISBN 1-58488-291-3。