||V{maketoc}||
||__~~navy:@#13::: این مطلب از بخش آموزش وب‌سایت المپیاد ریاضی رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وب‌سایت المپیاد رشد]موجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین می‌توانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا))‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.:: #@~~__||
^@#16:
!زیر گراف ها
مفهوم این که گراف {TEX()} {G} {TEX} زیر گراف گراف {TEX()} {H} {TEX} است یعنی {TEX()} {G} {TEX} توشکم {TEX()} {H} {TEX} جا گرفته است!!
اما تعریف دقیق آن:
---
!تعریف
گراف{TEX()} {G} {TEX}را زیر گراف{TEX()} {H} {TEX} گوییم اگر و فقط اگر
{TEX()} {E(G) \subseteq E(H) , V(G) \subseteq V(G)} {TEX} می‌نویسیم{TEX()} {G \subseteq H} {TEX}
---
!تعریف. زیر گراف سره
اگر{TEX()} {G \subseteq H} {TEX} بوده ولی{TEX()} {G \neq H} {TEX} باشد{TEX()} {G} {TEX} را زیر گراف سره {TEX()} {H} {TEX} می نامند و می نویسند{TEX()} {G\subseteq H} {TEX}
---
!تعریف. زیر گراف فراگیر
اگر{TEX()} {G\subseteq H} {TEX}{TEX()} {G,V(G)=V(H)} {TEX} ،را زیر گراف فراگیر{TEX()} {H} {TEX} می نامند ( یعنی همه رئوس {TEX()} {H} {TEX} در{TEX()} {G} {TEX}آمده)
---
!تعریف. زیر گراف القایی
{TEX()} {G} {TEX} را زیر گراف القایی{TEX()} {H} {TEX}می نامند اگر :
{TEX()} {V(G) \subseteq V(H)} {TEX} بوده و میان رئوس {TEX()} {V(G)} {TEX} تمام یالهای موجود بین همین رئوس در {TEX()} {H} {TEX} نیز وجود داشته باشد.
---
!!مثال
::{picture=img/daneshnameh_up/0/05/mco0051a.jpg}::
{TEX()} {G_2,G_1} {TEX}هر دو زیر گراف {TEX()} {H} {TEX} می باشند ولیکن {TEX()} {G_1} {TEX}زیر گراف القایی {TEX()} {H} {TEX} نیست زیرا یال {TEX()} {e_3} {TEX} میان {TEX()} {v_3,v_1} {TEX}در {TEX()} {G_1} {TEX} موجود نمی باشد ولیکن در {TEX()} {H} {TEX} موجود می باشد.

---
!!نکته
زیر گراف القاقی و فراگیر{TEX()} {G} {TEX}، همان{TEX()} {G} {TEX}است. (چرا؟ )
---
!تعریف
اگر مجموعه رئوس {TEX()} {V,G} {TEX} بوده و {TEX()} {V^1CV} {TEX} باشد.
زیر گراف القایی{TEX()} {G(V/V^1)} {TEX}، زیر گراف القایی از{TEX()} {G} {TEX} می باشد که شامل رئوس {TEX()} {V-V^1} {TEX} باشد.
زیر گراف القایی{TEX()} {G(V/V^1)} {TEX} را به صورت {TEX()} {G-V_1} {TEX} نیز نشان می دهند.
---
!!مثالهایی از تمام تعاریف فوق
::{picture=img/daneshnameh_up/3/3d/mco0051b.jpg}::
::||{picture=img/daneshnameh_up/4/42/mco0051c.jpg}::
::{TEX()} {G_1} {TEX} زیر گراف فراگیر {TEX()} {H} {TEX}||::
::||{picture=img/daneshnameh_up/f/fe/mco0051d.jpg}::
::{TEX()} {G_2} {TEX} زیر گراف القایی {TEX()} {H} {TEX}||::
::||{picture=img/daneshnameh_up/3/38/mco0051e.jpg}::
::{TEX()} {G_3} {TEX} زیر گراف القایی {TEX()} {H} {TEX}و{TEX()} {G_3=G-\{V_3 \}} {TEX}||::
::||{picture=img/daneshnameh_up/a/aa/mco0051f.jpg}::
::{TEX()} {G_4} {TEX} زیر گراف القایی و فراگیر {TEX()} {H} {TEX}و{TEX()} {G_4=H} {TEX}||::
---
!تمرین
نشان دهید هر ((گراف ساده)) ، زیر گرافی از{TEX()} {K_{|V(G)|} {TEX} می باشد.
__جواب__
واضح است مجموعه رئوس هر دو یکسان بوده از طرفی گراف کامل همواره حداکثر یال ممکن را دارد پس {TEX()} {E(G) \subseteq E(K_{(V(G))})} {TEX}.
---
!تمرین
به ترتیب فرض کنید {TEX()} {G} {TEX}گرافی دو بخشی، کامل، تهی و {TEX()} {-k} {TEX}منتظم باشد.
برای هر یک بررسی کنید آیا خصوصیت گفته شده به زیر گراف آن هم منتقل می شود یا نه؟
__جواب__
اثبات جوابهای زیر به عهده خودتان
•زیر گراف یک گراف دو بخشی همواره دو بخشی بوده
•زیر گراف یک گراف کامل همواره کامل بوده
•زیر گراف یک گراف تهی نیز همواره تهی بوده
•ولیکن زیر گراف یک {TEX()} {-k} {TEX}منتظم الزاماً {TEX()} {-k} {TEX} منتظم نمی باشد زیرا:
__مثال نقض__
::||{picture=img/daneshnameh_up/0/09/mco0051g.jpg} ::
:: {TEX()} {H} {TEX}دو منتظم می‌باشد||::
::||{picture=img/daneshnameh_up/3/3c/mco0051h.jpg}::
::{TEX()} {G\subset H} {TEX}منتظم نیست||::
---
! پیوند های خارجی
[http://Olympiad.roshd.ir/computer/content/pdf/0067.pdf]
---
!همچنین ببینید
*((همبندی ))
*((گرافهای یکریخت ))
#@^