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

מתוך ויקיספר, אוסף ספרי הלימוד והמדריכים החופשי.

< מבני נתונים ואלגוריתמים - מחברת קורס | גרפים | גרפים וייצוגיהם

מבני נתונים ואלגוריתמים - מחברת קורס

תוכן עניינים

1 מימוש לפונקציית המעבר על הקשתות
- 1.1 שאלה
- 1.2 תשובה
2 חישוב דרגות כניסה ויציאה
- 2.1 שאלה
3 לחיצת ידיים במסיבה
- 3.1 שאלה
- 3.2 תשובה
4 הושבה משני צידי שולחן
- 4.1 שאלה
- 4.2 תשובה

[עריכה] מימוש לפונקציית המעבר על הקשתות

[עריכה] שאלה

נתון גרף $\displaystyle G = (V, E)$ . הגרף דליל, ולכן רוצים להשתמש בייצוג רשימה. עם זאת, סיבוכיות מימוש הפונקציה E(G) שראינו בכיתה, דהיינו $\displaystyle \Theta(|E| + |V|)$ , גבוהה מדי לטעמנו.

אנא הסבר כיצד לשנות את המימוש כך שסיבוכיות הפונקציה תרד ל $\displaystyle \Theta(|E|)$ , מבלי להגדיל את סיבוכיות הפונקציות האחרות. אנא הסבר בקצרה (רצוי בתרשים) את השינויים הנדרשים, וכתוב את הפסוודו-קוד לפונקציה E(G).

מותר לך לעשות שינויים מבניים במבנה הנתונים המייצג את הגרף (דהיינו, להוסיף או לשנות שדות, או להוסיף עוד מבני-נתונים פנימיים). עם זאת, נסה לעשות מספר קטן ככל האפשר של שינויים.

[עריכה] תשובה

נוסיף עוד רשימה מקושרת, has-neighbors, המתארת את הצמתים שלהם יש שכנים.

דוגמה:

בתרשים הבא, הרשימה המקושרת has-neighbors מכילה חוליות בעלות התוכן 1, 2, 3, ו4, מפני שאלה הצמתים שלהם שכנים.

קל לראות שסיבוכיות A(G, u) וV(G) אינן מושפעות מהוספת הרשימה המקושרת (הן אינן משתמשות בו). להלן הפסוודו-קוד החדש של E(G):

Count-Num-Edges(G)
1	count = 0
 
2	lnk = G.has-neighbors.front
 
3	while lnk != Nil
4		u = lnk.value
 
5		count = count + Size( G.Vertexes[u] )
 
6		lnk = lnk.next
 
7	return count
 
 
# Returns an array of the edges of a graph (G).
E(G)
1	Edges = Make-Array( Count-Num-Edges(G) )
 
2	i = 0
 
3	lnk = G.has-neighbors.front
 
4	while lnk != Nil
5		u = lnk.value
 
6		for v in A(G, u)		
7			Edges[i++] = (u, v)
 
8		lnk = lnk.next
 
9	return Edges

פונציית-העזר Count-Num-Edges סופרת את מספר הצמתים. שורה 1 מאתחלת משתנה הסופר את מספר הצמתים ל0, ושורה 7 מחזירה אותו. הלולאה 3-6 (יחד עם 2) עוברת על כל חוליות has-neighbors. עבור כל חוליה, 4 מוצאת את מספר הצומת, ו $\displaystyle 5$ מוצאת את מספר שכניו. הפונקציה E מייצרת את המערך Edges ב1, ומחזירה אותו ב9. הלולאה 4-8 (יחד עם 3) עוברת על כל חוליות has-neighbors. עבור כל חוליה, 5 מוצאת את מספר הצומת, ו $\displaystyle 6-7$ רצות על שכניו. לכל שכן, קשת מתאימה מיתוספת לEdges.

[עריכה] חישוב דרגות כניסה ויציאה

הדף נמצא בשלבי עבודה
דף זה נמצא כעת בשלבי עריכה. הנכם מתבקשים שלא לערוך אותו בטרם תוסר הודעה זו.
במקרה שדף זה לא נערך במשך שבוע או יותר, רשאי כל משתמש להסיר הודעה זו.

[עריכה] שאלה

נתון גרף $\displaystyle G = (V, E)$ ברשימת שכנויות.

רוצים לחשב, לכל צומת $\displaystyle v \in V$ , את דרגת היציאה שלו (כלומר, כמה קשתות יוצאות ממנו). מה הסיבוכיות הנדרשת?
רוצים לחשב, לכל צומת $\displaystyle v \in V$ , את דרגת הכניסה שלו (כלומר, כמה קשתות נכנסות אליו). מה הסיבוכיות הנדרשת?

[עריכה] לחיצת ידיים במסיבה

[עריכה] שאלה

במסיבה כלשהי יש $\displaystyle n$ אנשים; חלקם לחץ ידיים זה עם זה. אנא הוכח שמספר האנשים שלחצו ידיים עם מספר אי-זוגי של אנשים - הוא זוגי.

דוגמה:

נניח שבמסיבה יש שלשה אנשים: 1,‏ 2,‏ ו3, ורק 1 ו2 לחצו ידיים זה עם זה. יש שני אנשים שלחצו ידיים עם אדם אחד; אכן יש מספר זוגי (שניים) של אנשים שלחצו ידיים עם מספר אי-זוגי (אחת) של אנשים.

רמז

צייר גרף שבו כל אדם הוא צומת. מה יקרה אם תמחק צומת כלשהו והקשתות היוצאות ממנו?

[עריכה] תשובה

נוכיח את הטענה באינדוקציה על $\displaystyle n$ , מספר הצמתים.

(בסיס האינדוקציה) אם בגרף יש צומת יחיד, אין קשתות. אם בגרף יש שני צמתים, אז או שיש קשת אחת, או שאין אף קשת. בכל אחד ממקרים אלה, בדיקה פשוטה מראה שהטענה מתקיימת. לכן הטענה נכונה עבור $\displaystyle n = 1, 2$ .

(מעבר האינדוקציה) נניח שהטענה נכונה עבור כל גרף בעל $\displaystyle n - 1$ צמתים, ונראה שהטענה נכונה עבור כל גרף בעל $\displaystyle n$ צמתים. ניקח גרף בעל $\displaystyle n$ צמתים, ונחפש צומת $\displaystyle u$ שמספר שכניו אי-זוגי. (אם אין צומת כזה, הטענה בהכרח נכונה לגרף זה.) נניח ששכניו של $\displaystyle u$ הם $\displaystyle u_1, \ldots, u_i$ . נשים לב ש $\displaystyle i$ בהכרח אי-זוגי. אם נמחק את $\displaystyle u$ והקשתות שיוצאות ממנו, הטענה נכונה מהנחת האינדוקציה. לאחר הוספת $\displaystyle u$ מחדש, כמה צמתים בעלי דרגה אי-זוגית נוצרו? $\displaystyle u$ עצמו תורם 1. כל שכן של $\displaystyle u$ בעל דרגה זוגית הופך להיות בעל דרגה אי-זוגית, וכל שכן של $\displaystyle u$ בעל דרגה אי-זוגית הופך להיות בעל דרגה זוגית. היות ש $\displaystyle i$ אי-זוגי, תרומת שכניו היא מספר אי-זוגי (חיובי או שלילי). לכן נוצר עוד מספר זוגי (חיובי או שלילי) של צמתים בעלי דרגה זוגית.

דוגמה:

בתרשים הבא, יש ל $\displaystyle u$ ‏ 3 שכנים: 2 בעלי דרגה אי-זוגית (בלעדיו), ו1 בעל דרגה זוגית (בלעדיו).

לאחר הוספת $\displaystyle u$ , יש ל $\displaystyle u$ ‏ 2 שכנים בעלי דרגה אי-זוגית (יחד אתו), ושכן יחיד בעל דרגה זוגית (יחד אתו). הוספת $\displaystyle u$ ייצרה עוד 0 צמתים בעלי דרגה אי-זוגית: $\displaystyle u$ עצמו בעל דרגה אי-זוגית, $\displaystyle u_1$ הפך להיות בעל דרגה זוגית, $\displaystyle u_2$ הפך להיות בעל דרגה אי-זוגית ו $\displaystyle u_3$ הפך להיות בעל דרגה זוגית.

[עריכה] הושבה משני צידי שולחן

[עריכה] שאלה

במסיבה כלשהי יש $\displaystyle n$ אנשים; חלקם לחץ ידיים זה עם זה. כעת יש להושיב אותם משני צידי שולחן. אנא הוכח שאפשר להושיב אותם באופן כזה כך שכל אחד יושב מול לפחות חצי מהאנשים שאתם לחץ יד.

דוגמה:

נניח שבמסיבה יש שלשה אנשים: 1,‏ 2,‏ ו3, ורק 1 ו2 לחצו ידיים זה עם זה. אכן אפשר להושיב את 1 ו3 בצד אחד של השולחן, ואת 2 בצד השני.

[עריכה] תשובה

ניצור שתי קבוצות. הקבוצה השמאלית, $\displaystyle L$ תכיל בתחילה את כל הצמתים (כלומר $\displaystyle L = V$ ); הקבוצה הימנית, $\displaystyle R$ , תהיה ריקה בתחילה (כלומר $\displaystyle R = \emptyset$ ).

נאמר שקשת כלשהי $\displaystyle e = (u, v)$ שמחה אם $\displaystyle u$ ו $\displaystyle v$ שייכות לשתי קבוצות שונות. נגדיר כ $\displaystyle E(u)$ את קבוצת הקשתות היוצאות מ $\displaystyle u$ , ונגדיר כ $\displaystyle H(u)$ את קבוצת הקשתות השמחות היוצאות מ $\displaystyle u$ . לפי הגדרות אלו:

בתחילה, אף קשת אינה שמחה. ( $\displaystyle \forall_{u \in U}|H(u)| = \emptyset$ .)
אם לפחות חצי מהקשתות היוצאות מכל צומת שמחות, פתרנו את הבעיה. (אם $\displaystyle \forall_{u \in U}|H(u)| \ge \frac{|E(u)|}{2}$ , אז פתרנו את הבעיה.)

כעת, כל עוד לא פתרנו את הבעיה, נפעל כדלהלן. נבחר שרירותית צומת כלשהו $\displaystyle u$ מבין הצמתים שרוב קשתותיהם אינו שמח. נעביר את $\displaystyle u$ לקבוצה השניה.

דוגמה:

בתרשים הבא, $\displaystyle |H(u)| = 2 < \frac{|E(u)|}{2} = \frac{5}{2}$ . לכן נעביר את $\displaystyle u$ ל $\displaystyle R$ .

המשפט הבא מראה שהתהליך הוא סופי.

משפט:

בכל פעם שמעבירים צומת כלשהו $\displaystyle u$ כמתואר לעיל, עולה מספר הקשתות השמחות.

לפני הוכחת משפט זה, הבה נבין מדוע הוא מראה שהתהליך סופי. המשפט טוען שכל עוד קיים צומת כלשהו $\displaystyle u$ שרוב קשתותיו אינו שמח - העברת $\displaystyle u$ לקבוצה השניה תגדיל את מספר הקשתות השמחות. מספר הקשתות השמחות מתחיל ב0, ויכול להגיע לכל היותר ל $\displaystyle |E|$ .

כעת נוכיח את המשפט.

הוכחה: נניח שהשכנים של $\displaystyle u$ בקבוצה שלו הם $\displaystyle u_1, \ldots, u_i$ , ושכניו בקבוצה השניה הם $\displaystyle v_1, \ldots, v_j$ . נשים לב שבהכרח $\displaystyle i > j$ .

לאחר העברת $\displaystyle u$ , מספר הקשתות השמחות גדל ב $\displaystyle i - j \ge 1$ .

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

מתוך ויקיספר, אוסף ספרי הלימוד והמדריכים החופשי.

תוכן עניינים

[עריכה] מימוש לפונקציית המעבר על הקשתות

[עריכה] שאלה

[עריכה] תשובה

[עריכה] חישוב דרגות כניסה ויציאה

[עריכה] שאלה

[עריכה] לחיצת ידיים במסיבה

[עריכה] שאלה

[עריכה] תשובה

[עריכה] הושבה משני צידי שולחן

[עריכה] שאלה

[עריכה] תשובה

צפיות

כלים אישיים

ניווט

קהילה

חיפוש

תיבת כלים

הדפסה/ייצוא