منو
 صفحه های تصادفی
دفاع عقلانی از دين
تولید نوترون
کلیساهای تاریخی تبریز
زیارت امام حسین و جوابهای متناقض
کاسه گل
امام حسین در قرآن - توبه : 36
برکیارق سلجوقی
Quick Time
دفتر دارائی
برترین وصی نزد خداوند
 کاربر Online
683 کاربر online
تاریخچه ی: زیر گرافها

تفاوت با نگارش: 1

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