منو
 کاربر Online
1029 کاربر online
تاریخچه ی: زیر گرافها

نگارش: 1



این مطلب از بخش آموزش وب‌سایت المپیاد ریاضی رشد،انتخاب شده که با فرمت pdf نیز در وب‌سایت المپیاد رشدموجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس فهرست مطالب کامپیوتر مراجعه کنید. همچنین می‌توانید با کلیک اینجا‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.


زیر گراف ها

مفهوم این که گراف زیر گراف گراف است یعنی توشکم جا گرفته است!!
اما تعریف دقیق آن:

تعریف

گرافرا زیر گراف گوییم اگر و فقط اگر
می‌نویسیم

تعریف. زیر گراف سره

اگر بوده ولی باشد را زیر گراف سره می نامند و می نویسند

تعریف. زیر گراف فراگیر

اگر ،را زیر گراف فراگیر می نامند ( یعنی همه رئوس درآمده)

تعریف. زیر گراف القایی

را زیر گراف القاییمی نامند اگر :
بوده و میان رئوس تمام یالهای موجود بین همین رئوس در نیز وجود داشته باشد.

مثال

img/daneshnameh_up/0/05/mco0051a.jpg

هر دو زیر گراف می باشند ولیکن زیر گراف القایی نیست زیرا یال میان در موجود نمی باشد ولیکن در موجود می باشد.


نکته

زیر گراف القاقی و فراگیر، هماناست. (چرا؟ )

تعریف

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

مثالهایی از تمام تعاریف فوق

img/daneshnameh_up/3/3d/mco0051b.jpg

img/daneshnameh_up/4/42/mco0051c.jpg
زیر گراف فراگیر

img/daneshnameh_up/f/fe/mco0051d.jpg
زیر گراف القایی

img/daneshnameh_up/3/38/mco0051e.jpg
زیر گراف القایی و

img/daneshnameh_up/a/aa/mco0051f.jpg
زیر گراف القایی و فراگیر و


تمرین

نشان دهید هر گراف ساده ، زیر گرافی از می باشد.
جواب
واضح است مجموعه رئوس هر دو یکسان بوده از طرفی گراف کامل همواره حداکثر یال ممکن را دارد پس .

تمرین

به ترتیب فرض کنید گرافی دو بخشی، کامل، تهی و منتظم باشد.
برای هر یک بررسی کنید آیا خصوصیت گفته شده به زیر گراف آن هم منتقل می شود یا نه؟
جواب
اثبات جوابهای زیر به عهده خودتان
•زیر گراف یک گراف دو بخشی همواره دو بخشی بوده
•زیر گراف یک گراف کامل همواره کامل بوده
•زیر گراف یک گراف تهی نیز همواره تهی بوده
•ولیکن زیر گراف یک منتظم الزاماً منتظم نمی باشد زیرا:
مثال نقض
img/daneshnameh_up/0/09/mco0051g.jpg
دو منتظم می‌باشد

img/daneshnameh_up/3/3c/mco0051h.jpg
منتظم نیست


پیوند های خارجی

http://Olympiad.roshd.ir/computer/content/pdf/0067.pdf





تاریخ شماره نسخه کاربر توضیح اقدام
 یکشنبه 14 آبان 1385 [11:22 ]   3   زینب معزی      جاری 
 یکشنبه 19 شهریور 1385 [10:04 ]   2   زینب معزی      v  c  d  s 
 یکشنبه 19 شهریور 1385 [06:18 ]   1   زینب معزی      v  c  d  s 


ارسال توضیح جدید
الزامی
big grin confused جالب cry eek evil فریاد اخم خبر lol عصبانی mr green خنثی سوال razz redface rolleyes غمگین smile surprised twisted چشمک arrow



از پیوند [http://www.foo.com] یا [http://www.foo.com|شرح] برای پیوندها.
برچسب های HTML در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..