בעיית צביעת גרפים

[otherside3]

בעיית צביעת גרפים

הי, אני מקווה שזה הפורום הנכון לשאול שאלות מסוג זה..
העניין הוא כזה: נתון לי גרף כלשהוא, בו דרגת היציאה של כל צומת חסומה ע"י 2.
אני צריך לתאר אלגוריתם שצובע את הגרף הזה בלכל היותר 9 צבעים.
קראתי קצת באינטרנט ומצאתי הוכחה שמספר הצבעים המינימלי שצריך (כרומטי) במקרה הזה, קטן או שווה ל-5, כלומר עבור כל גרף כללי אני אצטרך לפחות 1,2,3,4,5 צבעים..
הבעיה היא - האינטואיצהי שלי עד כה אומרת שהמספר המקסימלי המינימלי (כי ברור שאני יכול גם לצבוע את כל הגרף ב-n צבעים) של צבעים שבהם אצטרך להשתמש בגרף כללי מסוג זה הוא 4, אבל אני לא ממש מצליח להוכיח את זה פורמלית (אם אצליח להוכיח שזה 4, או לפחות להוכיח שזה קטן/שווה מ-8, אז יש לי אלגוריתם שיפתור את הבעיה..)
(ע"פ השאלה עצמה, כנראה שיש איזשהיא דרך להוכיח שזה באמת קטן או שווה ל-9, ואז כנראה שיש דרך להוכיח שזה אפילו קטן ממש מ-9.. השאלה היא איך..)

אשמח לרעיונות

תודה ושבוע טוב!

 

[אורי769]

זה הפורום הנכון

שלום לך,
זה הפורום הנכון, אבל השאלה שלך מאד לא ברורה. נתחיל מזה שלא ברור הנתון. הגרף הוא גרף מכוון או לא מכוון (מה הכוונה בדרגת יציאה)? האם הכוונה לצביעה של קודקודים או צביעה של צלעות?
חוץ מזה, אתה לא מפרש נכון דברים: אם כתוב שמספר הצביעה הוא 5 עבור גרף כלשהו, זה אומר שצריך לכל היותר חמישה צבעים, לא לפחות חמישה צבעים.

 

[otherside3]

סליחה, אתה צודק!

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

לגבי ההערה האחרונה - לא בטוח שהבנתי.
אנחנו למדנו שמספר כרומטי של גרף זה מספר הצבעים *המינימלי* הנדרש כדי לצבוע אותו בצביעה חוקית (כזאת שכל 2 קודקודים שמחוברים בקשת לא יהיו צבועים באותו צבע), כלומר אם המספר הכרומטי של גרף הוא נניח, 4, אז אני *לא אוכל* לצבוע אותו ב-1/2/3 צבעים (כלומר הוא לא 1-צביע, 2-צביע, 3-צביע) אלא אצטרך 4 (או יותר) צבעים כדי לצבוע אותו..

יכול להיות (most likely) שלא הבנתי 100% את ההגדרה:
אם מצאתי שעבור גרף המקיים תכונות מסויימות (נניח גרף מכוון שדרגת היציאה שלו חסומה ע"י 2) המספר הכרומטי הוא 4, אז עבור *כל קלט אקראי* שיקיים את התכונות האלה מובטח שאני אוכל לצבוע את הגרף באמצעות 4 צבעים (או יותר אם ממש מתחשק לי...), או שזה רק חסם תחתון ויכול להיות שעבור קלט מסוים כלשהוא אני אצטרך נניח 6 צבעים?
כלומר אם עבור משפחת הגרפים הנתונה בשאלה הגעתי להוכחה כי המספר הכרומטי שלהם הוא לכל היותר 5, אז מובטח לי שאין שום קלט שיכולים לתת לי שעבורו אני אצטרך מספר צבעים הגדול/שווה ל-6? (כי אם כן, זה פותר לי 100% את בעיית האלגוריתם, שמבטיח לי צביעה בעד 8 צבעים)

 

[אורי769]

תיקון

צודק... אני התבלבלתי במה שכתבתי (זה מה שקורה כשעונים בשעות לא שעות)
אם מספר הצביעה של G הוא 5 אז זה אומר שצריך לפחות חמישה צבעים. מה שכן, אם מסתכלים על משפחה של גרפים, נניח כל הגרפים שדרגת היציאה של קודקוד היא לכל היותר 2, ואומרים שאפשר לצבוע אותם ב-9 צבעים, אז הכוונה שלכל היותר נדרש ל-9 צבעים.

 

[otherside3]

נכון, הבעיה היא שזה בגדול מה שאני צריך להוכיח

כלומר השאלה טוענת כי עבור כל גרף העונה על התנאים, ניתן לצבוע אותו בלכל היותר 9 צבעים ואני צריך להוכיח את זה
(איך שאני מבין את "הכיוון של כותב השאלה", אני *מניח* שהמטרה היא להוכיח שהחסם העליון של זה הוא 8 (או כל מספר אחר שקטן ממנו), הבעיה היא שאני לא כ"כ יודע איך פורמלית ניתן להוכיח את זה, מצד שני יכול להיות שזה לא נכון ובאמת יש איזשהוא קלט שעבורו אצטרך 9 צבעים, למרות שאינטואיטיבית אני קצת לא מאמין בזה...)

 

[otherside3]

בינתיים הגרף עם הכי הרבה צבעים שהצלחתי למצוא זה 5

אבל עדיין לא הצלחתי להגיע להסבר/הוכחה פורמלית למה מספר הצבעים המקסימלי שיפתור לי את הבעיה הוא 9 או פחות..

 

[אורי769]

הנה

נתון גרף לא מכוון G, וקיים ל-G כיוון של הצלעות כך שדרגת היציאה של כל קודקוד היא לכל היותר 2. אם אני מבין נכון, זה הנתון, ושואלים מה מספר הצביעה של G.

במקרה זה באמת קל להוכיח שהתשובה היא - 5.
הנה הוכחה:
מאחר ויש כיוון של הצלעות כך שמכל קודקוד יוצאות לכל היותר שתי צלעות (אבל יכולות להכנס יותר) אז מספר הצלעות E ומספר הקודקודים V מקיימים E <= 2V.
נשים לב שבכל גרף (לא מכוון) הדרגה הממוצעת של קודקוד היא
Davg = 2E/V
ולכן במקרה זה
Davg <= 4V/V = 4
כלומר הדרגה הממוצעת של הקודקודים היא לכל היותר 4. בפרט קיים קודקוד שדרגתו 4 או פחות.
כעת נוכיח באינדוקציה את מספר הצביעה - נניח שניתן לצבוע כל גרף הקטן מ-G. נוציא מ-G את הקודקוד v בעל דרגה =< 4 ונצבע בחמישה צבעים. מאחר ואחד הצבעים אינו צובע את אף אחד משכניו של v יש צבע פנוי ל-v.

לא ברור לי מאיפה המספר 9 נכנס לסיפור, או שלא הבנתי את השאלה.

 

[otherside3]

יכול להיות שה-9 זה סתם מסיח של כותב השאלה

כיוון שמה שאנחנו למדנו זה אלגוריתם שצובע בעד 8 צבעים, ובגלל שכאן המקסימום הוא 5 אז זה הופך את השאלה ל"לא מעניינת" ולכן בחרו איזשהוא מספר אקראי הגדול מ-8

קודם כל, תודה רבה על העזרה וההסברים עד כה!

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

 

[עריסטו]

גם העובדה שכל דרגות היציאה קטנות או שוות 2 מטעה

כי אין צורך בזה. מספיק שדרגת היציאה הממוצעת תהיה קטנה או שווה 2.

 

[עעעערררר]

צריך שזה יישמר בכל תת-גרף

ולכן לא מספיק לדרוש על הממוצע.

 

[עריסטו]

נכון

 

[אורי769]

תשובות

- כוונתי לצביעה ב-5 צבעים כמובן.
- למדת מה זו דרגה ואתה יודע מה זה ממוצע... אז אתה יודע מה זאת דרגה ממוצעת. אין כאן משהו שמישהו צריך ללמד אותך במיוחד. והטיעון שלי הוא בסיסי: אם גובהו של גבר ממוצע בישראל הוא 1.80 אז יש לפחות גבר אחד שגובהו לכל היותר 1.80 ויש לפחות אחד שגובהו לפחות 1.80.
לשאלתך - אני לא יכול לחשוב כרגע על הוכחה אלטרנטיבית.