אלגוריתמים

[vicz]

אלגוריתמים

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

חג שמח לכולם

, עוד מעט

ויקי

 

[johnny d]

עברית אנגלית, קצת מבלבל...

הבנתי שהגרף לא מכוון וצריך להוכיח שיש משולש או שלשה בלתי תלויה בגרף... אבל מה ידוע על הגרף לא ממש הצלחתי להבין...

 

[vicz]

אופס... אצלי זה נראה בסדר ../images/Emo10.gif

בכל אופן, קודם כל תודה על הרצון לעזור נתון גרף לא מכוון עם 6 קודקודים יש להוכיח שהגרף מכיל משולש או קבוצה של שלושה קודקודים שאין ביניהם קשת (בין אף זוג מתוך השלושה) תודה שוב ויקי

 

[johnny d]

אולי,

סתם כך עולה לי לראש, אם אין קבוצה בלתי תלויה בגודל 3, אז כל תת גרף של 3 צמתים חייב להכיל קשת. ישנם בדיוק 60 תתי גרפים כאלו, וקשת יכולה להיות מוכלת מקסימום ב4 שלשות שונות (זוג הצמתים ועוד כל אחד מה4 הנותרים), ולכן יש לפחות 15 קשתות בגרף. יכול להיות שגרף עם 6 צמתים ו15 קשתות חייב להכיל משולש מסיבה כלשהי ?

 

[vicz]

ניסיתי קומבינטוריקה

אבל זה לא הוביל לשום דבר חוץ מרצון עז לדפוק את הראש בקיר עכשיו אני מנסה כיוון שונה

 

[vicz]

אופס נשלח לי בטעות לפני שהספקתי

להגיד

על המאמץ

 

[kand100]

הפתרון שלי

מקווה שהוא נכון : יהי גרף G עם 6 קודקודים. ויהי קודקוד v כלשהו בגרף. נבחין בין שני מקרים : 1. ל-v יש לפחות 3 שכנים. נסמן את קבוצת השכנים כ-U. אם קיימים זוג קודקודים ב-U המחוברים ביניהם בקשת הרי שביחד עם קודקוד v יש לנו משולש. אחרת, אף שני קודקודים ב-U לא מחוברים. מכיוון שב-U יש לפחות שלושה קודקודים הרי שיש לנו לפחות 3 קודקודים שלא מחוברים בקשת (אף זוג מביניהם) ולכן סיימנו. 2. ל-v יש לכל היותר 2 שכנים. נסמן ב-W את קבוצת הלא שכנים של v. ב-W יש לפחות 3 קודקודים. נסתכל על 3 קודקודים ב-W. אם שלושתם מחוברים אז יש לנו משולש. אחרת, לפחות 2 אינם מחוברים וביחד עם v יש לנו 3 קודקודים לא מחוברים (קבוצה בלתי תלויה כנדרש) אני מאוד מקווה שהפתרון הזה נכון !

 

[vicz]

קודם כל תודה

אני אבדוק את הכיוון הזה נשמע נכון תודה שוב

ויקי

 

[mjune]

הבעיה היא אחת הראשונות שמודגמות

בקורס קומבינטוריקה למדמ"ח בטכניון, תחת "עקרון שובך היונים" (למעשה פותרים בעיה שקולה - גרף מלא של 6 קודקודים, הקשתות הן אדומות או כחולות; יש להוכיח שקיים משולש מונוכרומטי). הפתרון: ניקח קודקוד כלשהו a. מעקרון שובך היונים יש לנו שני מקרים: א. a מחובר לשלושה קודקודים שונים, b, c, d. בהכרח אף לא אחד מהקודקודים הללו מחובר בקשת עם קודקוד שני בקבוצה זו, שאחרת היה נוצר משולש יחד עם a. מכאן שהם שלושתם לא מחוברים בקשת. ב. a לא מחובר בקשת לשלושה קודקודים שונים. ההוכחה שקולה ל-א'.