בשאלה זו שני סעיפים, א-ב, שאין קשר ביניהם. ענו על שני הסעיפים.

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

1. לכל עץ פורש DFS של גרף G לא מכוון יש תמיד אותו מספר עלים.
2. גובה עץ פורש BFS של גרף G לא מכוון, תמיד קטן או שווה לגובה עץ פורש DFS של אותו הגרף.
3. גרף G לא מכוון בעל n צמתים ו-(n-2) קשתות תמיד לא קשיר.
4. בכל גרף G לא מכוון שבו n צמתים ו-m קשתות, כך ש-m>=n, קיים מעגל.
5. גרף G לא מכוון שבו הדרגות של כל הקודקודים גדולות מ-0 הוא תמיד קשיר.

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

public static List<Edge> MaxSpanningTree (List<Edge> edges, int n)