מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/עצים/תרגילים/הוספת קשת ויצירת מעגל/תשובה

נניח שנוסיף לגרף את הקשת $\displaystyle (u,v)$. להלן העץ לפני הוספת הקשת.

העץ לפני הקשת

נזכור שעץ הוא קשיר עפ"י ההגדרה, ולכן לפני הוספת הקשת, היה מסלול $\displaystyle P$ מ$\displaystyle u$ ל$\displaystyle v$.

העץ לפני הקשת - מסלול מודגש

לכן, לאחר הוספת הקשת $\displaystyle (u,v),$ יש מסלול מ$\displaystyle u$ לעצמו: המסלול $\displaystyle P$ שאליו משורשרת הקשת $\displaystyle (u,v)$.

העץ לפני הקשת - המעגל