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

Граф с циклом в вершине 1

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

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

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

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

Степень

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

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

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

См. также

В теории графов

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

В топологии

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

Ссылки

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

Внешние ссылки

• В этой статье использованы общедоступные материалы из Пол Э. Блэк. «Автоматическая петля» . Словарь алгоритмов и структур данных . НИСТ .