שאלת מבחן במבוא למדעי המחשב - אוניברסיטת בן גוריון 2019 - גרפים

שאלה 3 (25 נקודות) בארבעת סעיפי שאלה זו עליכם להשלים שתי מחלקות היורשות את המחלקה GraphAlgorithm. הממשק Graph מתאר גרף לא מכוון וללא קשתות עצמיות (ראו נספח). יש להניח שהקלט תקין, ובפרט כי הפרמטר $\text{input} \neq \text{null}$. **סעיף א (5 נקודות)** בסעיף זה תשלימו את המחלקה TwoDegreesAlgorithm (נתונה בהמשך) שמרחיבה את המחלקה GraphAlgorithm. האלגוריתם המתואר על ידי מחלקה זו מקבל בבנאי גרף input ובהפעלת השיטה ()runAlgorithm מחזיר ערך true אם דרגת כל קודקודי הגרף היא 2 ו-false אחרת. לדוגמה: בהינתן הגרפים g1, g2 להלן, הקוד: [IMAGE] ```java GraphAlgorithm ga1 = new TwoDegreesAlgorithm(g1); System.out.println(ga1.runAlgorithm()); GraphAlgorithm ga2 = new TwoDegreesAlgorithm(g2); System.out.println(ga2.runAlgorithm()); ``` ידפיס: ``` true false ``` להלן תבנית המחלקה TwoDegreesAlgorithm שעליכם להשלימו: ```java public class TwoDegreesAlgorithm extends GraphAlgorithm { // assumes input != null public TwoDegreesAlgorithm (Graph input){ // איתחול השדות – המימוש לא רלוונטי לפתרון השאלה // אין צורך להשלים } public Object runAlgorithm() { // השלימו את הגדרת השיטה בסעיף א } } ``` להלן הגדרת המחלקה המופשטת GraphAlgorithm: ```java public abstract class GraphAlgorithm { protected Graph input; // assumes input != null public GraphAlgorithm(Graph input) { this.input = input; } abstract public Object runAlgorithm(); } ``` **סעיף ב (5 נקודות), סעיף ג (5 נקודות) וסעיף ד (10 נקודות)** הגדרה: גרף ייקרא גרף-מעגל (Cyclic-Graph) אם יש לו שלושה קודקודים לפחות, כל קודקוד הוא מדרגה 2 וכל שני קודקודים מחוברים בינהם במסלול. באופן לא פורמלי, זהו גרף בצורת מעגל. לדוגמה: הגרף g3 הוא גרף מעגל, והגרפים g1 ו-g2 אינם גרף-מעגל.

רמז: עברו על כל קודקודי הגרף ובדקו את דרגתם. ברגע שנתקלתם בקודקוד שדרגתו אינה 2, ניתן להסיק מיד את התשובה עבור הגרף כולו.

פתרון: מטרת השיטה `runAlgorithm` היא לקבוע האם **דרגתו** של **כל קודקוד** בגרף הנתון היא בדיוק 2. לשם כך, נבצע את השלבים הבאים: 1. נעבור בלולאה על כל אחד מהקודקודים בגרף. לצורך המימוש, נניח שהקודקודים מיוצגים על ידי מספרים שלמים מ-0 עד `n-1`, כאשר `n` הוא מספר הקודקודים הכולל בגרף, ושהממשק `Graph` מספק שיטות `getNumberOfVertices()` לקבלת `n` ו-`degree(i)` לקבלת דרגת הקודקוד `i`. 2. בכל איטרציה בלולאה, עבור הקודקוד הנוכחי, נבדוק את דרגתו. 3. אם נמצא קודקוד שדרגתו **שונה מ-2**, נוכל להסיק מיד שהתנאי אינו מתקיים עבור כל הגרף, ולכן נחזיר `false` ונסיים את ריצת השיטה. 4. אם הלולאה מסתיימת וכל הקודקודים שנבדקו היו בעלי דרגה 2, פירוש הדבר שהתנאי מתקיים לכל הגרף, ולכן נחזיר `true`. במקרה של גרף ריק (ללא קודקודים), הלולאה לא תתבצע כלל והשיטה תחזיר `true`, תוצאה נכונה מכיוון שהתנאי "לכל קודקוד, דרגתו היא 2" מתקיים באופן ריק. להלן המימוש המבוקש עבור השיטה: ```java public Object runAlgorithm() { // נניח שקיימת שיטה המחזירה את מספר הקודקודים בגרף int n = this.input.getNumberOfVertices(); // לולאה העוברת על כל הקודקודים (המיוצגים ע\"י המספרים 0 עד n-1) for (int i = 0; i < n; i++) { // נניח שקיימת שיטה המחזירה את הדרגה של קודקוד נתון if (this.input.degree(i) != 2) { return false; // מצאנו קודקוד שדרגתו אינה 2 } } // אם לא מצאנו אף קודקוד כזה, סימן שדרגת כולם היא 2 return true; } ``` $\blacksquare$