В теории графов , А цикл (также называемый самостоятельная петлей или пряжкой ) является краем , который соединяет вершину к себе. Простой граф не содержит петель.
В зависимости от контекста граф или мультиграф могут быть определены таким образом, чтобы разрешить или запретить наличие циклов (часто вместе с разрешением или запретом нескольких ребер между одними и теми же вершинами):
- Если графы определены таким образом, чтобы допускать петли и множественные ребра, граф без петель или множественных ребер часто отличается от других графов, называя его простым графом .
- Если графы определены таким образом, чтобы не допускать петель и множественных ребер, граф, у которого есть петли или множественные ребра, часто отличается от графов, удовлетворяющих этим ограничениям, называя его мультиграфом или псевдографом .
В графе с одной вершиной все ребра должны быть петлями. Такой граф называется букетом .
Степень [ править ]
Для неориентированного графа , то степень вершины равна числу смежных вершин .
Особый случай - это петля, которая добавляет два к степени. Это можно понять, если позволить каждому соединению края цикла считаться его собственной смежной вершиной. Другими словами, вершина с петлей «видит» себя как смежную вершину с обоих концов ребра, таким образом добавляя две, а не одну степень.
Для ориентированного графа цикл добавляет единицу к начальной степени и единицу к исходящей степени .
См. Также [ править ]
В теории графов [ править ]
В топологии [ править ]
Ссылки [ править ]
- Балакришнан, ВК; Теория графов , Макгроу-Хилл; 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 .
Внешние ссылки [ править ]
Эта статья включает материалы, являющиеся общественным достоянием из документа NIST : Black, Paul E. «Self loop» . Словарь алгоритмов и структур данных .
Эта статья включает материалы, являющиеся общественным достоянием из документа NIST : Black, Paul E. «Self loop» . Словарь алгоритмов и структур данных .