פורטל:מתמטיקה/חידות קשות/7

מה מספר העצים הפורשים של גרף מלא בעל n קודקודים?

הבהרת מושגים למי שלא מכיר:

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

לדוגמה עבור הגרף המלא בגודל 3, קל לראות שיש 3 עצים פורשים.