קבוצה בלתי תלויה (תורת הגרפים)
קבוצה בלתי תלויה היא קבוצה של נקודות (קודקודים) בגרף. נקודות בקבוצה כאלו לא מחוברות זו לזו. אם צובעים את הקודקודים כך ששכנים לא מקבלים את אותו צבע, כל צבע נותן קבוצה כזו. סימול נפוץ לגודל הגדול ביותר הוא α של הגרף. השאלה: האם יש קבוצה בלתי תלידה בגודל מסוים? זו שאלה קשה מאוד. ריצ'רד קארפ הראה שהי...
גרף שלם
גרף שלם (גרף מלא) הוא ציור של נקודות וקווים. נקודה = צומת. קו = קשת. בכל גרף כזה כל שתי נקודות מחוברות בקו. קוראים לגרף שלם עם n נקודות K_n. אם יש n נקודות, יש n(n-1)/2 קווים. זה אומר שכל זוג נקודות מחובר בקו אחד. הגרף קשיר, כלומר אפשר להגיע מכל נקודה לכל נקודה בדרך של קווים. אם נותנים לכל קשת חץ,...