مقدمات گراف

حجم فایل : 1.1 MB
نوع فایل : پاور پوینت
تعداد اسلاید ها : 38
بنام خدا مقدمات گراف
جلسه اول اولین مقاله درباره نظریه گراف توسط اویلر در سال 1732 تحت عنوان مساله پل های کوئینز برگ مطرح شد گراف ها را در حل بسیاری از مسائل از قبیل طراحی مدارهای مختلف ترافیکی ،
الکتریکی و...برای ساده کردن مسائل بسیار کاربرد دارد. نظریه گراف گراف انواع زیادی دارد گراف های ساده – جت دار – چند گانه – وزن دار – بارئوس متناهی یا نا متناهی و..
گراف ساده :اگر مجموعه
نا تهی و متناهی باشد و مجموعه ی شامل همه ی زیر مجموعه ها ی دو عضوی Vباشد آنگاه : V: راس گراف می نامد که مجموعه ی رئوس G هستند وE : زیر مجموعه ای از مجموعه تمام زیر مجموعه های دوعضوی V است
یادآوری : تعداد مجموعه راس های مرتبه گراف
تعداد مجموعه یالهای اندازه گراف به عبارت ساده تر :اگر p نقطه در صفحه داشته باشیم وبعضی از آنها را به دلخواه بهم وصل کنیم
شکل حاصل را گراف ساده گویند.
مثال 1-در گراف مورد نظر مجموعه یالها وراس های آنرا مشخص کنید. دوراس مجاور :
دو راس UوVرا مجاور گوییم هر گاه دو سر یک یال باشند ویال مربوطه را به صورت UV یا VU نمایش می دهند.
(مجاور بودن الزاما به معنای نزدیک بودن دوراس نیست ،به معنای این است که بین دو راس یال باشد) راس منفرد(منزوی):
راسی که درجه آن صفر باشد (یعنی هیچ یالی به آن متصل نباشد)
در مثال قبل رئوس منفرد را مشخص کنید
گراف تهی :
گرافG را تهی گویند هر گاه هیچ یالی در آن یافت نشود گراف ساده طوقه ندارد ،یعنی از یک راس به خودش یالی موجود نباشد.
در گراف ساده هیچ دو راسی را نمی توان با دویال به هم وصل کرد.
گراف چند گانه :
گرافی که طوقه یا یال چند گانه داشته باشد را گویند مثال : گراف متناظر با نمای شهر کوئینربرگ را رسم کنید گراف جهت دار : زوج مرتب که در آن V مجموعه ای متناهی وناتهی (رئوس )وE زیرمجموعه ای از مجموعه تمام زوج های مرتب متشکل از اعضای v است (یال) مثال :نمودار متناظر گراف جهت دار که در آن و می باشد را رسم کنید. مثال : در یک دوره مسابقه بین تیم های a,b,c,d,e مطابق زیر برقرار شده است.هر یال بین دو تیم به معنی بازی دوتیم وجهت آن از تیم برنده به بازنده است.کدام تیم به مقام اول رسیده است ؟ شمارش تعداد گرافها ساده :
با راس a,b,c چند گراف ساده می توان ساخت؟ مثال : با چهار راس a,b,c,d چند گراف می توان ساخت؟ تذکر : نکات فوق تنها زمانی درست است که رئوس نامگذاری شده باشد در غیر این صورت باید گرافها را رسم کرد مثال : چند گراف مرتبه 3داریم؟ مثال :با 5 نقطه ...