1. צבע את העץ והשתמש בכמה שפחות צבעים.

צביעה נכונה היא צביעת כל קודקוד בצורה כזו , שכל שני קודקודים צמודים יהיו בצבעים שונים.

2. נתונים N מספרים שלמים וחיובים D1, D2, ... ,DN אשר D1+D2+DN=2N-2

יש לבנות עץ עם N קודקודים שלכל I קיים קודקוד עם בדיוק DI צלעות

-מבחינת עצים , אני מכיר אלגוריתמים של BFS , הופמן וPRIM אם זה עוזר לפיתרון

תודה..

הועבר לפורום תכנות כללי.

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

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

האמת שניסיתי לחשוב ואני קצת מתקשה בנושא...

בקשר לשאלה השניה , לא אין עוד נתון..

1. רמז: מספיקים שני צבעים.

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

אתה מתכוון להפרדת צבעים בין עלה ימין ושמאל לבין האבא שלהם ?

נגיד אבא לבן , בן ימני ובן שמאלי אפור ?

לא יודע, תאמר לי אתה

(חוץ מזה, עץ כללי הוא לא בהכרח בינארי - לקודקוד יכולים להיות כמה בנים)

אני גם לא יודע

לכן אני שואל

ניסיתי לרמוז לך שהתשובה שלך נכונה, ושתגיע למסקנה (ותוכיח אותה) בעצמך.