زیر گراف ساده

تاریخ انتشار: 15 آذر 1399
آخرین ویرایش: 17 خرداد 1400
دسته‌بندی: گراف
امتیاز:
بازدید: 30 مرتبه

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

گراف G را در نظر بگیرید، آن‌گاه H یک زیرگراف G است، اگر:

  • V(H)V(G) یعنی راس‌های H زیر مجموعه راس‌های G باشند.
  • یعنی یال‌های H زیر مجموعه یال‌های G باشند.   

تمرین

گراف زیر را در نظر بگیرید:

زیرگراف ساده - پیمان گردلو

تعدادی از زیرگراف‌های گراف فوق را نشان دهید.

زیرگراف ساده - پیمان گردلو

تمرین

گراف زیر را در نظر بگیرید:

زیرگراف ساده - پیمان گردلو

تعدادی از زیرگراف‌های گراف فوق را نشان دهید.

زیرگراف ساده - پیمان گردلو

دریافت مثال

انواع زیرگراف

زیرگراف پُر 

فرض کنید HV',E' یک زیرگراف G=(V,E) باشد، آن‌گاه H یک زیرگراف پُر G است اگر E' شامل تمام یال‌های E باشد که دو سرآن در V' قرار دارند، در این حالت H زیرگراف G تولید شده توسط V' نام دارد.  

دریافت مثال

زیرگرافG-Vi

G-Vi زیرگراف G است که در آن V1 یک راس در G است که از حذف راس V1 از مجموعه راس VGو حذف تمام یال‌های EG به‌دست می‌آید که روی V1 قرار دارند، به بیان دیگر G-Vi یک زیرگراف پُر G است که توسط سایر راس‌ها تولید می‌شود.   

زیرگرافG-e

G-e زیرگراف G است که در آن e یک یال G است و G-e گرافی است که تنها از حذف e از مجموعه یال‌های G به‌دست می‌آید، در نتیجه:

E(G-e)=E(G)\e V(G-e)=V(G)

زیرگراف پوشا

گراف G=(V,E) و زیرگراف G1=(V1,E1) از G داده شده است، اگر V1=V آن‌گاه G1 را زیرگراف پوشای گراف G می‌گویند. 

به‌عنوان نمونه گراف G1 زیرگراف، گراف G می‌باشد.

زیرگراف ساده - پیمان گردلو 

مثال‌ها و جواب‌ها

زیر گراف ساده

100تومان
خرید فایل PDF مثال ها و جواب ها

برای ارسال نظر وارد سایت شوید