Jump to content

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

(Перенаправлено с Self-loop )
Граф с циклом в вершине 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 .
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: cdf41463ef06e2d72ce032a89b9b993f__1711423860
URL1:https://arc.ask3.ru/arc/aa/cd/3f/cdf41463ef06e2d72ce032a89b9b993f.html
Заголовок, (Title) документа по адресу, URL1:
Loop (graph theory) - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)