Βρόγχος (θεωρία γράφων)

Αρχείο:Graph with self loop examples.svg

Γράφος με βρόγχους στις κορυφές $v_1$, $v_5$ και $v_7$.

Στην θεωρία γράφων, βρόγχος σε έναν γράφο είναι μία ακμή που συνδέει έναν κόμβο με τον εαυτό του.Πρότυπο:Rp

Πιο συγκεκριμένα, σε έναν κατευθυνόμενο γράφο $G=(V,E)$ είναι οποιαδήποτε ακμή $e$ της μορφής $e=(u,u)$ για κάποιο κόμβο $u\in V$. Σε έναν μη κατευθυνόμενο γράφο είναι οποιαδήποτε ακμή της μορφής $\{u\}$ (που είναι ίση με $\{u,u\}$).

Εφαρμογές

• Στις Μαρκοβιανές αλυσίδες για να γίνουν απεριοδικές, προστίθενται βρόγχοι σε όλους τους κόμβους.

Δείτε επίσης

• Γράφος
• Κύκλος (θεωρία γράφων)