루프(그래프 이론)

정점 1에 루프가 있는 그래프

그래프 이론에서, 루프(self-loop 또는 buckle이라고도 함)는 정점을 연결하는 가장자리이다.단순한 그래프에는 루프가 포함되지 않습니다.

상황에 따라 그래프 또는 멀티그래프는 루프의 존재를 허용 또는 거부하도록 정의할 수 있습니다(종종 같은 정점 간의 여러 에지를 허용 또는 허용하지 않음).

그래프가 루프와 다중 에지를 허용하도록 정의되어 있는 경우, 루프가 없거나 다중 에지가 없는 그래프는 종종 단순한 그래프라고 하여 다른 그래프와 구별됩니다.
그래프가 루프 및 다중 에지를 허용하지 않도록 정의되어 있는 경우, 루프 또는 다중 에지가 있는 그래프는 종종 멀티그래프 또는 의사그래프라고 하여 이러한 제약을 충족하는 그래프와 구별됩니다.

하나의 정점이 있는 그래프에서는 모든 모서리가 루프여야 합니다.이런 그래프를 꽃다발이라고 해요.

도

무방향 그래프의 경우 정점의 정도는 인접한 정점의 수와 같습니다.

특별한 경우는 루프로, 도에 2를 더합니다.이것은 루프 에지의 각 접속을 인접 정점으로 카운트하는 것으로 이해할 수 있습니다.즉, 루프가 있는 정점은 가장자리 양쪽 끝에서 인접한 정점으로 자신을 "고정"하기 때문에 도에 하나가 아닌 두 개를 추가합니다.

방향 그래프의 경우 루프는 1을 인도에, 1을 아웃도에 추가합니다.

발라크리슈난, V. K., 맥그로힐 그래프 이론, 1판(1997년 2월 1일) ISBN 0-07-005489-4.
Bollobas, Béla; 현대 그래프 이론, 스프링거; 초판(2002년 8월 12일).ISBN 0-387-98488-7.
Diestel, Reinhard, Graph Theory, Springer, 제2판(2000년 2월 18일).ISBN 0-387-98976-5.
Gross, Jonathon L 및 Yellen, Jay; Graph Theory and Its Applications, CRC Press(1998년 12월 30일).ISBN 0-8493-3982-0.
Gross, Jonathon L, Yellen, Jay; (eds); 그래프 이론 핸드북.CRC(2003년 12월 29일).ISBN 1-58488-090-2.
Zwilinger, Daniel, CRC Standard Mathemical Tables 및 공식, Chapman & Hall/CRC; 제31호(2002년 11월 27일).ISBN 1-58488-291-3.