Цикл (теория графов)

В теории графов петля (также называемая самопетлей или пряжкой ) — это ребро , соединяющее вершину с собой. Простой граф не содержит петель.

В зависимости от контекста граф или мультиграф может быть определен таким образом, чтобы разрешать или запрещать наличие петель (часто одновременно с разрешением или запрещением множественных ребер между одними и теми же вершинами):

• В тех случаях, когда графы определены таким образом, что допускают наличие петель и множественных ребер, граф без петель и множественных ребер часто отличают от других графов, называя его простым графом .
• Если графы определены таким образом, что не допускают петель и множественных ребер, то граф, имеющий петли или множественные ребра, часто отличают от графов, удовлетворяющих этим ограничениям, называя его мультиграфом или псевдографом .

В графе с одной вершиной все ребра должны быть петлями. Такой граф называется букетом .

Для неориентированного графа степень вершины равна числу смежных вершин .

Особый случай — это петля, которая добавляет два к степени. Это можно понять, если позволить каждому соединению ребра петли считаться своей собственной смежной вершиной. Другими словами, вершина с петлей «видит» себя как смежную вершину с обоих концов ребра, таким образом добавляя два, а не один, к степени.

Для направленного графа цикл добавляет единицу к степени входа и единицу к степени выхода .

• Цикл (теория графов)
• Теория графов
• Глоссарий теории графов

• Лестница Мёбиуса
• лента Мёбиуса
• Странная петля
• Бутылка Клейна

• Балакришнан, В.К.; Теория графов , McGraw-Hill; 1-е издание (1 февраля 1997 г.). ISBN  0-07-005489-4 .
• Боллобас, Бела; Современная теория графов , Springer; 1-е издание (12 августа 2002 г.). ISBN 0-387-98488-7 . 
• Дистель, Рейнхард; Теория графов , Springer; 2-е издание (18 февраля 2000 г.). ISBN 0-387-98976-5 . 
• Гросс, Джонатан Л. и Йеллен, Джей; Теория графов и ее приложения , CRC Press (30 декабря 1998 г.). ISBN 0-8493-3982-0 . 
• Гросс, Джонатан Л. и Йеллен, Джей; (редакторы); Справочник по теории графов . CRC (29 декабря 2003 г.). ISBN 1-58488-090-2 . 
• Цвиллингер, Дэниел; Стандартные математические таблицы и формулы CRC , Chapman & Hall/CRC; 31-е издание (27 ноября 2002 г.). ISBN 1-58488-291-3 . 

•  В этой статье использованы материалы, находящиеся в открытом доступе, от Пола Э. Блэка. "Self loop". Словарь алгоритмов и структур данных . NIST .