שאלה בנוגע לאלגוריתם

[F1M]

שאלה בנוגע לאלגוריתם

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

 

[vinney]

המם...

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

 

[vinney]

(זה בהנחה ואין סדר בתוך רמה אחת)

(אם יש סדר, כמו למשל עצי מיון, אז הדוגמא שלך לא טובה, העצים לא איזומורפיים)

 

[F1M]

העצים הם עצים כלליים...

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

 

[F1M]

אגב... מה קורה במקרה שהעצים הוא לא מושרשים?

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

 

[vinney]

מה זה מושרשים?

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

 

[F1M]

אוקי והפתרון שלי נכון?

...

 

[vinney]

לא

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

 

[F1M]

לא הבנת אותי...

נגיד נסמן בk את גובה העץ. נקח 2 מערכים בגודל k. עבור כל עומק נספור עבור כל עץ בנפרד במערך שלו כמה עלים יש באותו עומק.. לדוגמא לעץ א' יש 3 עלים בעומק 6 ו2 עלים בעומק 5 (לא בטוח שהדוגמא שלי נכונה אבל זה אינטואיטיבי) לעץ ב' כנ"ל יש 3 עלים בעומק 6 ו2 עלים בעומק 5 אז הטענה שלי שאם 2 המערכים הם שווים אז העצים הם איזומורפיים...

 

[F1M]

קיבלתי עדכון...

אמרו לי: The trees should not be rooted זה אומר שאני לא יודע היכן השורש אני צודק?

 

[vinney]

כן

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

 

[F1M]

קיבלתי הודעה כזו...

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

 

[vinney]

קשיר, לא מכוון וחסר מעגלים

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

 

[F1M]

במקרה זה יש לך פתרון לתרגיל?

יש לך רעיון לאגלוריתם שפותר את התרגיל?

 

[vinney]

מה, עוד לא סיימת עם זה?

נו באמת...

 

[F1M]

לא ממש הבנתי...

איך אתה מתחשב בעובדה שלא ידוע לך היכן נמצא השורש? חוץ מזה למה הכוונה tweak קטן? לא ממש הבנתי מה אמרת...

 

[vinney]

אבל אין שורש בעץ לא מכוון!

אין כזה דבר "שורש" בעץ שהוא גרף לא מכוון. אין במה להתחשב. tweak קטן = התאמה קטנה. אתה צריך לעשות התאמה שתתחשב במקרה הזה.