tree decomposition

[Pharell]

tree decomposition

אהלן שאלה, אני צריך להוכיח רוחב עץ של גרף G הוא 1 אם"ם G הוא יער דבר ראשון אני חושב שיכול להיות שהרוחב יכול להיות גם 0 אם העץ הוא יער אבל נעזוב את זה בינתיים. דבר שני, בהוכחה של הכיוון משמאל לימין, הוכחתי על דרך השלילה ונתקעתי בשלב שמראים שאם הרוחב הוא גדול מ1 אז לא יכול להיות מעגלים בגרף, מישהו יכול לעזור?

 

[Pharell]

*אם היער הוא עץ

 

[vinney]

איך מוגדר רוחב?

 

[Pharell]

הגדרה של רוחב

רוחב עץ של גרף G הוא המספר השלם הקטן ביותר k כך שקיים פירוק לעץ של G כך שכל אחד מצמתיו מכיל k+1 צמתים של G לכל היותר.

 

[ron369]

אתה בטוח שזה נכון?

 

[Pharell]

ההגדרה או מה שצריך להוכיח?

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

 

[Pharell]

מכוון ל ron369

 

[ron369]

מה הרוחב של הגרף הבא, למשל:

1 2 2 3 3 4 5 6 6 7 7 8 ?

 

[Pharell]

2

 

[Pharell]

1 התכוונתי

 

[ron369]

למה? איך?

לא ברורה לי ההגדרה.

 

[Pharell]

איך זה דיי קל

יש לנו 2 עצים ביער שנתת, אז נתחיל מהעץ הראשון לכל קשת a,b נבנה צומת בעץ שיכיל את a,b את הקשתות נגדיר כך, לכל שני צמתים בעץ, אם החיתוך שלהם לא ריק אז נוסיף קשת ביניהם. נעשה אותו דבר לעץ השני, ועכשיו נבחר שרירותית שני צמתים משני העצים שבנינו ונוסיף קשת ביניהם. נקבל פירוק לעץ מרוחב 1

 

[Pharell]

כיוון מימין לשמאל כמובן