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

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

שאלה

נתון גרף $\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)$ ברשימת שכנויות.

1. רוצים לחשב, לכל צומת $\displaystyle v\in V$, את דרגת היציאה שלו (כלומר, כמה קשתות יוצאות ממנו). מה הסיבוכיות הנדרשת?
2. רוצים לחשב, לכל צומת $\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$. לפי הגדרות אלו:

1. בתחילה, אף קשת אינה שמחה. ($\displaystyle \forall _{u\in U}|H(u)|=\emptyset$.)
2. אם לפחות חצי מהקשתות היוצאות מכל צומת שמחות, פתרנו את הבעיה. (אם $\displaystyle \forall _{u\in U}|H(u)|\geq {\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\geq 1$.