Петля (теорія графів)
Петля́ у графі — це ребро, інцидентне одній і тій же вершині. Простий граф не містить петель.
Строго кажучи, у петлі немає орієнтації. Однак в орієнтованому графі петлям надають орієнтацію.
Так як петля з'єднує вершину саму з собою, то множина ребер Е містить пари вигляду (х, х).
У деяких підручниках граф за визначенням не може мати петель. Граф із петлями та кратними ребрами називають мультиграфом або псевдографом.
Скінченний неоднорідний граф без петель і кратних ребер називається звичайним графом.
Степінь
Для неорієнтованого графу степінь вершини дорівнює кількості сусідніх вершин.
Спеціальним випадком є петля, яка додає дві степені. Це пояснюється тим, що кожне з'єднання ребром-петлею можна розглядати як свою сусідню вершину. Інакше кажучи, вершина з петлею «бачить» себе як сусідню вершину з обох кінців краю, таким чином додаючи два, а не один, степінь.
Для орієнтованого графу цикл додає один до степеня входу і один до степеня виходу.
Див. також
Джерела інформації
- Нікольський Ю. В., Пасічник В. В., Щербина Ю. М. Дискретна математика. — К.: Видавнича група BHV, 2007. — 368 с.: іл. ISBN 966-552-201-9.
- Бардачов Ю. М., Соколова Н. А., Ходаков В. Є. Дискретна математика: Підручник. — К.: Вища школа, 2007. — 383 с.: іл. ISBN 978-966-642-343-9