Question

dfs

יהא G=(V,E)G = (V, E) גרף לא מכוון וקשיר ו-TT עץ DFS\text{DFS} שלו. נסמן את גובהו של TT ב-hh.

א. הוכיחו כי מספר הקשתות של GG הוא לכל היותר Vh|V| \cdot h.

ב. הוכיחו כי ב-GG קיים מסלול פשוט שאורכו לפחות EV\frac{|E|}{|V|}.

ג. הציעו אלגוריתם למציאת מסלול פשוט שאורכו לפחות EV\frac{|E|}{|V|} בגרף לא מכוון וקשיר. על האלגוריתם לרוץ בזמן O(V+E)O(V + E).

1

Answers

א. נזכיר כי בעץ DFS\text{DFS} של גרף לא מכוון אין קשתות חוצות, ולכן דרגת כל צומת היא לכל היותר hh (רק קשתות לצמתים על המסלול אליה מהשורש).

ב. נשים לב ש-EVVhV=h\frac{|E|}{|V|} \leq \frac{|V| \cdot h}{|V|} = h, כמו כן, אם עומק העץ הוא hh אז קיים מסלול פשוט באורך hh.

ג. האלגוריתם:

  • הרץ DFS
  • החזר את המסלול לעלה הכי עמוק בעץ

הנכונות נובעת מסעיפים א. וב. והסיבוכיות לינארית.

1
Feedback