Петля (теорія графів)

У Вікіпедії є статті про інші значення цього терміна: Петля.

Петля́ у графі — це ребро, інцидентне одній і тій же вершині. (Простий) граф не містить петель.

Граф, який містить петлю при вершині 1

Приклад петель в орієнтованому графі

Строго кажучи, у петлі немає орієнтації. Однак в орієнтованому графі петлям надають орієнтацію.

Так як петля з'єднує вершину саму з собою, то множина ребер Е містить пари вигляду (х, х).

У деяких підручниках граф за визначенням не може мати петель. Граф із петлями та кратними ребрами називають мультиграфом або псевдографом.

Скінченний неоднорідний граф без петель і кратних ребер називається звичайним графом.

Степінь

Для неорієнтованого графу степінь вершини дорівнює кількості сусідніх вершин.

Спеціальним випадком є ​​петля, яка додає дві степені. Це пояснюється тим, що кожне з'єднання ребром-петлею можна розглядати як свою сусідню вершину. Інакше кажучи, вершина з петлею «бачить» себе як сусідню вершину з обох кінців краю, таким чином додаючи два, а не один, степінь.

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

Див. також

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

Джерела інформації

• Нікольський Ю. В., Пасічник В. В., Щербина Ю. М. Дискретна математика. — К.: Видавнича група BHV, 2007. — 368 с.: іл. .
• Бардачов Ю. М., Соколова Н. А., Ходаков В. Є. Дискретна математика: Підручник. — К.: Вища школа, 2007. — 383 с.: іл.