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

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

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

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

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