در نظریه گراف، یک درخت گرافی است که هر دو راس آن بوسیله دقیقاً یک یال به هم متصل شده اند، یک جنگل گرافی است که دو راس آن با بیشتر از یک راس به هم متصل اند. یک جنگل در واقع از اتصال، مجموعه ای از درخت ها به وجود می آید.

تعریف ها:

یک درخت از شرایط زیر پیروی می کند.

• در آن هیچ مدار یا حلقه ای موجود نیست.
• درخت یک گراف همبند است.
• با حذف یک یال از درخت، دیگر آن گراف یک درخت نخواهد بود.
• هر دو راس در یک درحت بوسیله مسیر منحصر به فرد به هم متصل می شوند.

اگر یک جنگل با n راس باشد آن گاه از شرایط زیر پیروی می کند:

• T یک درخت است.
• T مداری ندارد و n-1 یال دارد.
• T همبند است و n-1 یال دارد.
• هر دو راس T با مسیر منحصر به فرد به هم متصل می شوند.
• T مداری ندارد و با افزودن یگ یال جدید دقیقاً یک مدار بوجود می آید.

مثال:

در شکل درختی با 6 راس و 5 یال وجود دارد مقدار یالها برابر 5 = 1- 6 است. و بین دو راس 2 و 6 دقیقاً یک مسیر وجود دارد که عبارت است از 6-5-4-2

بیشتر بدانیم:

درخت مولد گراف مانند G بزرگترین گراف درختی مانند T در G است که با افزودن یک یال از درخت بودن خارج می شود و واضح است اگر یک گراف n راس و m یال داشته باشد آن گاه درخت مولد n-1 یال داشته و باید m >= n-1 باشد.
تعداد درخت های مولد متمایز برای گراف کامل با n راس برابر است. این قضیه به قضیه کایلی معروف است.
تعداد درخت هایی که با n راس با درجات می توان ساخت برابر مقدار زیر است:

اصل لانه کبوتر که به نام های «اصل جعبه کفش» یا «اصل کشویی دیر کله» مشهور است، اغلب برای پاسخ دادن به سوالات زیر مفید است:
«آیا اشیایی وجود دارند که درخاصیت مشخصی صدق کنند؟»
اگر اصل لانه کبوتر به طور موفقیت آمیزی به کار رود، تنها وجود چنین اشیایی را ثابت می کند و چیزی درباره روش یافتن اشیا و یا مشخص کردن تعداد آنها بیان نمی کند.

شکل ساده اصل لانه کبوتری

n کبوتر در k لانه قرار می گیرند. اگر n>k ،آنگاه تعدادی از لانه ها بیش از یک کبوتر خواهند داشت.

برهان

دلیل درستی این اصل، اغلب به برهان خلف ثابت می شود. زیرا، اگر اصل برقرار نباشد، آنگاه، هر لانه حداکثر یک کبوتر دارد و در این حالت، حداکثر کبوتر وجود خواهد داشت که با فرض و وجود کبوتر متناقص است. به دلیل بدیهی بودن استدلال به عنوان اصل پذیرفته می شود. دقت کنید که این اصل، اطلاعاتی درباره آن لانه هایی که حداقل دو کبوتر دارند ارائه نمی کند و تنها وجود چنین لانه هایی را تایید می کند.
در استفاده از این اصل در حل مسایل، باید تصمیم گرفت که نقش کبوتر ها و لانه ها چگونه تعبیر شوند.

مثال

ده نفر به اتاقی وارد شده اند که نام کوچک آنها احمد، رضا و مهدی است و نام خانوادگی آنها محمدیان، رسولی و رضایی است. نشان دهید حداقل دو نفر از این ده نفر، نام و نام خانوادگی یکسانی دارند.
حل: تنها 9 امکان برای تولید اسامی متمایز وجود دارد. اگر افراد را به عنوان کبوتر اسامی را به منزله لانه کبوتر فرض کنیم، آنگاه بنا بر اصل لانه کبوتر، بعضی از اسامی (لانه ها) به حداقل دو نقر (کبوتر ها) نسبت داده می شوند.
حال مثال دیگری ذکر میکنیم:
15 نفر دریک میهمانی شرکت کرده اند. طبق این اصل حداقل دو نفر پیدا می شوند که در یک ماه به دنیا آمده اند.

یکایک شمردن یا شمارش، ممکن است به عنوان فرآیندی آشکار تلقی شود که هر دانشجو در آغاز مطالعه علم حساب فرا می گیرد. ولی به نظر می رسد که پس از آن، به تدریج که دانشجو به زمینه های «دشوارتر» ریاضیات، چون جبر، هندسه، مثلثات، و حساب دیفرانسیل و انتگرال می رسد توجه بسیار کمتری به گسترش بیشتر مفهوم شمارش مبذول می شود.
یکایک شمردن محدود به حساب نیست. کاربردهایی نیز در زمینه هایی چون نظریه کدگذاری، حساب احتمالات، و آمار (درریاضیات) و در تحلیل الگوریتمها (در علم کامپیوتر) دارد.

قواعد

مطالعه خود را در ریاضیات گسسته و ترکیباتی با دو اصل اساسی شمارش آغاز می کنیم قاعده های حاصل جمع و حاصل ضرب، بیان این قاعده ها و کاربردهای اولیه آنها نسبتاً ساده به نظر می رسد. هنگام تحلیل مسائل پیچیده تر، غالباً قادریم مساله را به بخشهایی قسمت کنیم که با به کارگیری این اصول اساسی قابل حل است. هدف ما ایجاد قدرت «تجزیه»ی این گونه مسائل و ترکیب راه حلهای جزئی برای رسیدن پاسخ نهایی است. یک راه مناسب برای انجام این امر، تجزیه و تحلیل و حل تعداد زیادی از مسائل گوناگون مربوط به شمردن است. ضمن اینکه تمام مدت باید اصولی را که در راه حلها به کار می روند در نظر داشت. این همان رهیافتی است که ما در اینجا دنبال خواهیم کرد.

اصل اول

اصل نخست شمارش را می توان به صورت زیر بیان کرد:

توجه داشته باشید که وقتی می گوییم رویدادی خاص، مثلاً کاری از نوع نخست، می تواند به m طریق دهد، فرض بر این است که این m طریق متمایرند، مگر آنکه خلاف آن بیان شود.

مثال 1 کتابخانه دانشکده ای کتاب درسی درباره جامعه شناسی و 50 کتاب درسی در باره انسان شناسی دارد. بنابر قاعده حاصل جمع، دانشجویی که در این دانشکده تحصیل می کند، به منظور فراگیری بیشتر درباره این یا آن موضوع، می تواند بین 90 = 50 + 40 کتاب درسی انتخاب به عمل آورد.
مثال 2 قاعده بالا را می توان به بیشتر از دو کار تعمیم داد مشروط برآنکه هیچ جفتی از کارها را نتوان همزمان انجام داد. به عنوان مثال، یک مدرس علم  که در هر یک از زمینه ها اپل، بیسیک، فرترن، و پاسکال مثلاً پنج کتاب مقدماتی وارد، می تواند هر یک از این 20 کتاب را به دانشجوی علاقه مند به فراگیری نخستین و برنامه نویسی توصیه کند.

اصل دوم

مثال زیر مدخلی برای معرفی اصل دوم شمارش است.
مدیر کارخانه ای به منظور اتخاذ تصمیمی درباره توسعه کارخانه، 12 نفر از کارمندان خود را در دو گروه گرد آورد. گروه A مرکب از پنج عضو است و بناست درباره نتایج مساعد احتمالی چنین توسعه تحقیقاتی به عمل آورد. گروه دیگر، یعنی گروه Bکه مرکب از هفت کارمند است درباره نتایج نامساعد احتمالی بررسیهایی به عمل خواهد آورد. اگر، قبل از اتخاذ تصمیم، مدیر نامبرده بخواهد فقط با یکی از این اعضا درباره تصمیم صحبت کند، آنگاه بنابر قانون حاصل جمع، می تواند 12 کارمند را احضار کند. ولی، به منظور قضاوت بی طرفانه مدیر نامبرده تقسیم می گیرد که روز دوشنبه با عضوی از گروه Aو سپس روز سه شنبه با عضوی از گروه B صحبت کند تا به اتخاذ تصمیمی نائل گردد. با به کارگیری اصل زیر، ملاحظه می کنیم که او می تواند به 35 = 7 * 5 طریق دو کارمند متعلق به گروههای دو گانه را برگزیند و با آنها صحبت کند.

گاهی این قاعده را اصل انتخاب نیز می نامند.