בעיית כיסוי קבוצות
יש קבוצה של פריטים שנקראת U. יש גם אוסף של קבוצות קטנות שנקרא S. כל קבוצה ב־S מכילה חלק מהפריטים ב־U. כיסוי הוא בחירה של קבוצות מ־S כך שכל הפריטים ב־U יהיו כלולים לפחות בקבוצה אחת. נניח U = {1,2,3,4,5}. הקבוצות ב־S הן: {1,2,3}, {2,4}, {3,4} ו־{4,5}. אם בוחרים את {1,2,3} ואת {4,5}, אז כל המספרים מ...
עץ פורש מינימלי
עץ פורש מינימלי הוא דרך לחבר את כל הנקודות בגרף עם פחות עלות. גרף הוא קווים וצמתים. צומת זה נקודה; קשת זה קו שמחבר בין נקודות. משקל של קשת זה עלות או אורך שלה. חברת כבלים רוצה לחבר בתים. כל בית זה נקודה. כל כביש הוא קשת בעלות מסוימת. עץ פורש מקשר את כל הבתים בלי מעגלים. עץ פורש מינימלי מוצא את הקוו...