دانلود پاورپوینت مقدمه ای بر نظریه گراف

پاورپوینت آمادهمقدمه ای بر نظریه گراف برای رشته کامپیوتر در 85 اسلاید طراحی شده بخشی از مطالبی که در این پاورپوینت مورد بررسی قرار میگیرد به شرح زیر است:

مسأله رسم شکلی بصورت زیر بدون آنکه قلم را از روی کاغذ برداریم و از یک جا شروع و به همانجا برگردیم: 

نقطه بازی: جدولی از نقاط داشته باشیم و هر نفر در نوبت خود دو نقطه ی مجاور را به هم وصل کند:

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

تکنیک حل این مسأله بر اساس کاربردی از گراف ها است.
بدین منظور گرافی را در نظر می گیریم که هر رأس یک نفر را نشان می دهد.
یال نقطه چین بین رئوس معادل بیگانه بودن

یال ممتد بین رئوس معادل آشنایی آن دو نفر
باید نشان دهیم که همواره مثلثی با رئوس ممتد یا مثلثی با رئوس نقطه چین موجود است!

برای هر مکعب گرافی به این صورت معرفی می کنیم که دارای چهار رأس به صورت زیر است:


هر مکعب دارای 3 جفت وجه مقابل هم است: یک جفت مربوط به وجوه بالایی و پایینی، یکی مربوط به وجوه چپ و راست و دیگری مربوط به وجوه روبرو و عقب.
هر جفت از وجوه متناظر با یک یال است. پس هر گراف دارای 3 یال خواهد بود. مثلا اگر وجه چپ قرمز و وجه راست آبی باشد، دو رأس آبی و قرمز را به هم وصل می کنیم!

تمرین: برای آنکه در یک گراف ساده ی غیر تهی تعداد یالها دو برابر تعداد رئوس باشد، حداقل مرتبه گراف چند است؟
تمرین: در یک گراف ساده با مرتبه ی n و اندازه 36 کوچکترین درجه رئوس 2و بزرگترین درجه ی رئوس 6 است. حدود n را بیابید.
تمرین: در یک گراف ساده از مرتبه ی 40 و اندازه ی 84 درجه ی کلیه رئوس 3 یا 5 است. چند رأس این گراف از درجه ی 3 است؟
تمرین: گرافی با رأس های 0،2،3و9 چند یال دارد؟
تمرین: آیا گراف ساده ای یافت می شود که هر یک از رئوس آن از درجه زوج باشد؟
تمرین: در یک گراف با 20 یال که درجه هر رأس حداقل 4 است، بیشترین تعداد رئوس را بیابید.
تمرین: در یک گراف با 31 رأس که درجه هر رأس حداکثر 3 باشد، بیشترین تعداد یال را بیابید.

مؤلفه گراف G : بزرگترین زیر گراف همبند آن.
نکته: هر گراف برابر اجتماع مؤلفه های همبندی آن است.
مثال: یک گراف ساده با n راس و بیش از یال همبند است.
حل: گراف کامل دارای یال است. اگر یک رأس تنها به این یال بیفزاییم گرافی ناهمبند داریم. اگر یالی به این رأس متصل شود یک گراف همبند بدست می آید، زیرا رأس تنها را به یکی از رئوس متصل کرده است.
مثال: یک گراف با n رأس و یال رسم کنید که ناهمبند باشد.


¢ماتريس مجاورت و ماتريس وقوع هر دو علي رغم كارائي خود، خانه
هاي خالي بسياري در ماتريس خود دارند و اين علاوه بر اتلاف حافظه، موجب اتلاف زمان نيز خواهد گرديد . به عنوان مثال یک گراف تهی

100 راسي ماتريس مجاورت 100*100می خواهد که تمام خانه های آن خالي هستند.

 و... 

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

نکته ۲:پاورپوینت مقدمه ای بر نظریه گراف قابل ویرایش می باشد و می توانید آن را به دلخواه تغییر دهید

نکته 3: پاورپوینت ها برای جذابیت بیشتر شامل تصاویر می باشند.