پاورپوینت مقدمات گراف (pptx) 38 اسلاید
دسته بندی : پاورپوینت
نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )
تعداد اسلاید: 38 اسلاید
قسمتی از متن PowerPoint (.pptx) :
بنام خدا
مقدمات گراف
جلسه اول
اولین مقاله درباره نظریه گراف توسط اویلر در سال 1732 تحت عنوان مساله پل های کوئینز برگ مطرح شد گراف ها را در حل بسیاری از مسائل از قبیل طراحی مدارهای مختلف ترافیکی ،
الکتریکی و...برای ساده کردن مسائل بسیار کاربرد دارد.
نظریه گراف
گراف انواع زیادی دارد
گراف های ساده – جت دار – چند گانه – وزن دار – بارئوس متناهی یا نا متناهی و..
گراف ساده :اگر مجموعه
نا تهی و متناهی باشد و مجموعه ی شامل همه ی زیر مجموعه ها ی دو عضوی
V
باشد
آنگاه :
V
: راس گراف می نامد که مجموعه ی رئوس
G
هستند و
E
: زیر مجموعه ای از مجموعه تمام زیر مجموعه های دوعضوی
V
است
یادآوری :
تعداد مجموعه راس های مرتبه گراف
تعداد مجموعه یالهای اندازه گراف
به عبارت ساده تر :اگر
p
نقطه در صفحه داشته باشیم وبعضی از آنها را به دلخواه بهم وصل کنیم
شکل حاصل را گراف ساده گویند.
مثال 1-در گراف مورد نظر مجموعه یالها وراس های آنرا مشخص کنید.
دوراس مجاور :
دو راس
U
و
V
را مجاور گوییم هر گاه دو سر یک یال باشند ویال مربوطه را به صورت
UV
یا
VU
نمایش می دهند.
(مجاور بودن الزاما به معنای نزدیک بودن دوراس نیست ،به معنای این است که بین دو راس یال باشد)
راس منفرد(منزوی):
راسی که درجه آن صفر باشد (یعنی هیچ یالی به آن متصل نباشد)
در مثال قبل رئوس منفرد را مشخص کنید
گراف تهی :
گراف
G
را تهی گویند هر گاه هیچ یالی در آن یافت نشود
گراف ساده طوقه ندارد ،یعنی از یک راس به خودش یالی موجود نباشد.
در گراف ساده هیچ دو راسی را نمی توان با دویال به هم وصل کرد.
گراف چند گانه :
گرافی که طوقه یا یال چند گانه داشته باشد را گویند
مثال : گراف متناظر با نمای شهر کوئینربرگ را رسم کنید