קומבי - גרפים

[snorlax]

http://i.imgur.com/Cz68QP4.png

 

לא הבנתי את ההדרכה שלהם. למה אפשר להניח משהו על http://www.codecogs.com/gif.latex?a_0,a_k?

מישהו יכול לתת כיוון לשאלה הזאת?

[incog]

טוב אני אנסה לעזור:
1) אתה יכול להניח את זה כי זה פשוט להחליף תוויות, כלומר ישנה התאמה חח"ע בין השאלה הזו עם לבין השאלה כאשר a_0=n-1 ו- a_k=n (פשוט אם יש לך עץ עם ה- a_0 , a_k המקוריים תשלח אותו לעץ חדש על ידי החלפה בין הצומת a_0 ל- n-1  ו- a_k ל- n , זו כמובן התאמה חח"ע ועל).
 

2) לגבי הפתרון:
שים לב שברגע ש- a_0= n-1  ו- a_k=n  ויש לך מסלול כזה בין a_0  ל- a_n , אזי על פי האלגוריתם במשפט קיילי שמתאר לך את המילה, אתה לא תוריד אף אחת מהקשתות e_i (כי a_0  ו- a_k הם המספרים הגדולים ביותר), לכן לפי האלגוריתם אם קיים מסלול כזה אתה תגיע עליו אחרון, כלומר תהיה לך מילה כלשהי שתייצר ואז תגיע למסלול הזה:
a_0-a_1,...,-a_k  שייצר לך את המילה:    a_1a_2...a_k-1
כלומר ישנה התאמה חח"ע בין מספר העצים עם המסלול הנ"ל למספר המילים באורך n-2 עם n אותיות שמסתיימות במילה: a_1a_2,..,a_k-1  
(מה שהבאתי היה סקיצה של כיוון אחד, צריך עוד להראות שכל מילה כזו מייצגת עץ עם מסלול וזה הכיוון היותר קל).

אני מקווה שזה מובן, ואני לא מפספס פה משהו.

[snorlax]

תודה

[snorlax]

עוד שאלה:

 

מה מספר העצים המכוונים עם n צמתים שיש להם בדיוק 3 עלים?