جزوه خلاصه نکات جبرواحتمال و گسسته موسسه علوی

جزوه خلاصه نکات جبرواحتمال و گسسته موسسه علوی

جزوه خلاصه نکات جبرواحتمال و گسسته موسسه علوی

یک جزوه بسیار عالی از خلاصه نکات ریاضیات گسسته جبر و احتمال مخصوص کنکوری های عزیز

کمی از داخل جزوه :

نکته : هر گرافی همیلتنی همبند است.

نکته : اگر یک گراف همیلتنی باشد ، با حذف یک یال گراف همبند می ماند.

نکته : اگر با حذف یک یال گراف ناهمبند شود ، آنگاه همیلتنی نیست.

نکته : اگر گراف همیلتنی است ، آنگاه درجه ی هر راس بزرگتر یا مساوی ۲ است.

نکته : اگر g یک گراف همیلتنی باشد ، بین هر دو راس متمایز آن حداقل دو مسیر وجود دارد و فاصله دو راس متمایز حداکثر برابر با [p/2] است.

جزوه خلاصه نکات جبرواحتمال و گسسته موسسه علوی

گراف بازه ها :

نکته : هر گراف کامل گراف بازه ها است.

نکته : اگر از گراف kp یک یال حذف کنیم ، گراف حاصل گراف بازه ها است.

نکته : اگر از گراف kp ، هر چند یال از یک راس را حذف کنیم ، گذاف حاصل گراف بازه ها است.

تعرف حفره : در گراف ها ، چهار ضلعی بدون قطر را حفره می گویند (به عبارت دیگر هر n>4  ضلعی بدون قطر را حفره می گویند.)

نکته : اگر در گراف g ، یک حفره وجود داشته باشد ، آن گراف آ گراف بازه ای نمی باشد.

جزوه خلاصه نکات جبرواحتمال و گسسته موسسه علوی

درخت :

درخت (T) : گرافی همبند و بدون دور

نکته : در هر درخت ، بین هر دو راس فقط یک مسیر وجود دارد.

نکته : با حذف هر یال از درخت T ، درخت ناهمبند می شود.

نکته : هر درختی که بیش از یک راس دارد ، حداقل دو راس درجه یک دارد.

ماتریس مجاورت گراف (۱)

هر گراف ساده G با p راس با یک ماتریس مربع از مرتبه P مانند A متناظر است که ماتریس مجاورت گراف نامند و دارای خواص زیر است :

۱- درایه های روی قطر اصلی همگی صفر هستند.

۲- هر درایه ماتریس A ، صفر یا یک است.

۳- ماتریس مجاورت گراف ساده متقارن است.

۴- جمع درایه های سطر i ام (ستون i ام) درجه راس i می باشد.

۵- اگر درایه های سطر i ام صفر باشد ، سطر i ام یک راس تنها است.

۶- تعداد یک های ماتریس مجاورت گراف برابر با ۲q است.