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