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

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

Γράφος με βρόγχους στις κορυφές $v_{1}$, $v_{5}$ και $v_{7}$.

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

Εφαρμογές

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

Δείτε επίσης

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