גרף G=(V,E) לא מכוון, קשיר ופשוט, ייקרא גרף "מתחלק" אם מתקיימים בו התנאים האלה: יש בו שני צמתים לפחות; אפשר לחלק את הצמתים לשתי קבוצות, קבוצה א וקבוצה ב, באופן שבו לא יהיו שני צמתים המחוברים בקשת באותה הקבוצה. (השאלה המלאה כוללת גם סעיף א - שאלת מבוא לחקר ביצועים/תחבורה שאינה שייכת לתחום מבני הנתונים ואינה נכללת כאן; ראו SELECTION-2 להסבר.)
גרף G=(V,E) לא מכוון, קשיר ופשוט, ייקרא גרף "מתחלק" אם מתקיימים בו התנאים האלה: יש בו שני צמתים לפחות; אפשר לחלק את הצמתים לשתי קבוצות, קבוצה א וקבוצה ב, באופן שבו לא יהיו שני צמתים המחוברים בקשת באותה הקבוצה. (השאלה המלאה כוללת גם סעיף א - שאלת מבוא לחקר ביצועים/תחבורה שאינה שייכת לתחום מבני הנתונים ואינה נכללת כאן; ראו SELECTION-2 להסבר.)
שלושה גרפים לבדיקת "התחלקות" (G_c, G_b, G_a) וגרף שביעי-צמתים שאינו מתחלק
Gc: edges 1-2,1-3,1-4,3-4,3-5,3-6 (triangle 1-3-4)
Gb: edges 1-2,1-3,1-4,4-5,5-2 (4-cycle 1-2-5-4)
Ga: edges 2-3,2-1,2-5,1-4,3-7,3-6 (tree)
Not-bipartite graph (7 nodes): edges 1-2,2-3,1-6,3-6,1-4,3-5,3-7,4-5,4-7
סעיף ב
לפניך שלושה גרפים: G_c, G_b, G_a. ציין איזה מן הגרפים הוא גרף "מתחלק" ואיזה אינו. בעבור כל גרף "מתחלק" הראה את שתי קבוצות הצמתים שבו. לפניך גרף שאינו "מתחלק". מהו מספר הקשתות המינימלי שיש להסיר מהגרף כדי שהגרף יחשב "מתחלק"? כתוב אילו קשתות יש להסיר והצג את שתי הקבוצות.
שאלות ותגובות על השאלה
🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות
שאלו כאן — ותקבלו מענה מוסמך.