زیرگراف

زیرگراف به این مفهوم می‌باشد که گراف G زیرگراف H است؛ یعنی G تو شکم H جا گرفته‌است.

تعریف دقیق تر: گراف G زیرگراف H گوییم اگر و فقط اگر   می‌نویسیم

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

زیر گراف فراگیر 
اگر  را زیر گراف فراگیر H می‌نامند. (یعنی همه رئوس H در G آمده‌است)

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

منابع 

 

نظریه گراف