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

יהי n >= 4 מספר זוגי. הראו כיצד לבנות עץ עם n קדקודים שבו לכל קדקוד שאינו עלה יש דרגה 3 בדיוק.
מהו מספר העלים בעץ כזה כפונקציה של n? הסבירו מדוע n חייב להיות זוגי.
הערה: לא מדובר כאן בעץ עם שורש.


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

תודה

השאלה לא קשורה לתכנות ויותר מתאימה לפורום סטודנטים.

עריכה: למען האמת אולי עדיף לפני שאתה קורא את הרמזים שנתתי שתנסה לבנות עץ כזה עם 4,6,8 קודקודים ותנסה להבין למה בלתי אפשרי לבנות עץ כזה עם 3,5,7 קודקודים. זה עשוי לתת לך כיוון.

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

צודק אולי אפשר להעביר לפורום סטודנטים. טעות שלי.

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

אתה יודע מה זה גרף? עץ הינו גרף קשיר חסר מעגלים.

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

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

הנה לדוגמא שתי נקודות המבט ביחס לאותו עץ:

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

תוספים לפורום
קורס לטינית בלעדי לפרש, בפורום שפות ובלשנות.

גרף מכוון?

לא.

צודק לגבי התחושה שלך חשבתי שעץ חייב להיות מושרש.

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

לבנות עץ בן 4 קודקודים שעונה לתנאים זו לא בעיה, נכון?

זהירות - ספויילר!

מין "כוכב" שבו קודקוד אחד שמחובר לעוד שלושה.

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

זהירות - ספויילר!

אפשר לבחור עלה כלשהו ולחבר אליו שני קודקודים חדשים.

מכאן שאתה יכול להגיע לעץ כזה עבור כל מספר זוגי כלשהו של קודקודים

זהירות - ספויילר!

פשוט להוסיף שניים בכל פעם.

ומדוע שלא נוכל עם מספר אי־זוגי?

זהירות - ספויילר!

כי התנאי למעשה אומר שיש בעץ רק עלים בעלי דרגה 1, או "צמתים" בעלי דרגה 3
כלומר הדרגה של כל קודקוד היא אי־זוגית
אך סכום כל הדרגות שווה למספר הצלעות כפול 2:

[TEX]\sum_{v \in V} \deg(v) = 2\left|E\right|[/TEX]

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

זהו.

תוספים לפורום
קורס לטינית בלעדי לפרש, בפורום שפות ובלשנות.

וואו תודה רבה!

בכיף.

תוספים לפורום
קורס לטינית בלעדי לפרש, בפורום שפות ובלשנות.

רגע, בעצם זה לא עונה על הדרישה שלא מדובר בעץ מושרש.

"כוכב" הוא מושרש..

קרא שוב את התגובה הראשונה שלי
כל עץ יכול להיות מושרש ויכול להיות לא מושרש אם תבחר בכך
ל"צורה" של הגרף אין שום משמעות.

קח עץ שאינו מושרש, בחר קודקוד כלשהו, קרא לו "שורש" – הפכת את העץ למושרש
קח עץ מושרש, אל תיתן שום חשיבות לשורש, התייחס אליו כאל כל קודקוד אחר – הפכת את העץ ללא מושרש

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

תוספים לפורום
קורס לטינית בלעדי לפרש, בפורום שפות ובלשנות.

ווקשע =]

תוספים לפורום
קורס לטינית בלעדי לפרש, בפורום שפות ובלשנות.

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

אכן זה די מבלבל. אבל בסוף הבנתי

תודה חברים

ה 'הערה' מעידה שלא מדובר על עץ סטנדרטי...

תביא בבקשה הגדרה פורמלית על איזה סוג של עץ מדובר.

ההגדרה היא גרף פשוט חסר מעגלים והיא כן נחשבת ההגדרה הסטנדרטית.

באמת?

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

מה קשה להביא הגדרה מדוייקת?

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

אז תגיד....

ההגדרה שמשתמים בה בתכנות בד"כ היא הרבה יותר Strict.

וזה שזאת ההגדרה מקורמן (למיטב זכרוני) לא אומר שזאת ההגדרה היחידה.

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

תוספים לפורום
קורס לטינית בלעדי לפרש, בפורום שפות ובלשנות.

אני ממליץ לעיין בערכים בויקיפדיה:
https://he.wikipedia.org/wiki/%D7%9...%D7%99%D7%9D%29
https://he.wikipedia.org/wiki/%D7%A...%D7%99%D7%9D%29