تاریخچه ی:
اعمال اولیه
تفاوت با نگارش: 1
| ||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()} {v} {TEX} را از گراف{TEX()} {G} {TEX} که {TEX()} {v\in V(G)} {TEX} می باشد حذف و تمام یالهای مربوط به آن را از {TEX()} {E(G)} {TEX} کم کنیم آنچه می ماند را با {TEX()} {G-V} {TEX} نمایش داده و به این عمل حذف راس می گویند. | | اگر راس{TEX()} {v} {TEX} را از گراف{TEX()} {G} {TEX} که {TEX()} {v\in V(G)} {TEX} می باشد حذف و تمام یالهای مربوط به آن را از {TEX()} {E(G)} {TEX} کم کنیم آنچه می ماند را با {TEX()} {G-V} {TEX} نمایش داده و به این عمل حذف راس می گویند. |
| --- | | --- |
| !!حذف یال | | !!حذف یال |
| مشابه بالا با حذف فقط یک یال{TEX()} {e} {TEX} از گراف {TEX()} {G} {TEX} که {TEX()} {e\in E(G)} {TEX} می باشد به {TEX()} {G-e} {TEX} یا {TEX()} {G-\{ e \}} {TEX} می رسیم | | مشابه بالا با حذف فقط یک یال{TEX()} {e} {TEX} از گراف {TEX()} {G} {TEX} که {TEX()} {e\in E(G)} {TEX} می باشد به {TEX()} {G-e} {TEX} یا {TEX()} {G-\{ e \}} {TEX} می رسیم |
| --- | | --- |
| !!افزودن راس یا یال | | !!افزودن راس یا یال |
| برعکس دو تعریف بالا با افزودن راس به گراف{TEX()} {G+\{V \}} {TEX} به گراف{TEX()} {G+V} {TEX} می رسیم و با افزودن یک یال بین دو راس{TEX()} {G} {TEX} به گرافی می رسیم که آن را با {TEX()} {G+\{ V \}} {TEX} یا{TEX()} {G+V} {TEX}نمایش می دهند. | | برعکس دو تعریف بالا با افزودن راس به گراف{TEX()} {G+\{V \}} {TEX} به گراف{TEX()} {G+V} {TEX} می رسیم و با افزودن یک یال بین دو راس{TEX()} {G} {TEX} به گرافی می رسیم که آن را با {TEX()} {G+\{ V \}} {TEX} یا{TEX()} {G+V} {TEX}نمایش می دهند. |
| --- | | --- |
| !!زیر گراف القایی | | !!زیر گراف القایی |
| با تعریف زیرگراف القایی آشنا هستیم. | | با تعریف زیرگراف القایی آشنا هستیم. |
| لذا اگر {TEX()} {V^\prime \subseteq V(G)} {TEX} باشد، ((گراف)){TEX()} {G[V^1]} {TEX} زیر گراف القایی{TEX()} {G} {TEX} روی{TEX()} {V^1} {TEX} و گراف{TEX()} {G[V \setminus V^1]} {TEX} زیر گراف القایی روی{TEX()} {V(G)-V^\prime} {TEX} را می دهد. | | لذا اگر {TEX()} {V^\prime \subseteq V(G)} {TEX} باشد، ((گراف)){TEX()} {G[V^1]} {TEX} زیر گراف القایی{TEX()} {G} {TEX} روی{TEX()} {V^1} {TEX} و گراف{TEX()} {G[V \setminus V^1]} {TEX} زیر گراف القایی روی{TEX()} {V(G)-V^\prime} {TEX} را می دهد. |
| اگر {TEX()} {V^\prime= \{ V \}} {TEX} آنگاه{TEX()} {G[V \setminus V^1]=G-\{ V \}} {TEX} که به اختصار می نویسیم{TEX()} {G-V} {TEX} | | اگر {TEX()} {V^\prime= \{ V \}} {TEX} آنگاه{TEX()} {G[V \setminus V^1]=G-\{ V \}} {TEX} که به اختصار می نویسیم{TEX()} {G-V} {TEX} |
| --- | | --- |
| !!مکمل گیری | | !!مکمل گیری |
| با تعریف مکمل {TEX()} {G} {TEX} نیز آشناییم و آن را با {TEX()} {\overline{G}} {TEX} نمایش می دهیم. | | با تعریف مکمل {TEX()} {G} {TEX} نیز آشناییم و آن را با {TEX()} {\overline{G}} {TEX} نمایش می دهیم. |
| @@{TEX()} {V(\overline {G} )=V(G)} {TEX}@@ | | @@{TEX()} {V(\overline {G} )=V(G)} {TEX}@@ |
| @@{TEX()} {E(\overline{G} )=\{ (x,y)|x,y\in V^\prime (G) , xy \notin V(G) \}} {TEX}@@ | | @@{TEX()} {E(\overline{G} )=\{ (x,y)|x,y\in V^\prime (G) , xy \notin V(G) \}} {TEX}@@ |
| --- | | --- |
| !!مثال | | !!مثال |
| اگر{TEX()} {V(G)=\{v_1, v_2 , v_3,v_4 ,v_5 \}} {TEX} | | اگر{TEX()} {V(G)=\{v_1, v_2 , v_3,v_4 ,v_5 \}} {TEX} |
| {TEX()} {G} {TEX}به صورت روبرو باشد. | | {TEX()} {G} {TEX}به صورت روبرو باشد. |
| ::{picture=img/daneshnameh_up/2/2c/mco0053a.jpg}:: | | ::{picture=img/daneshnameh_up/2/2c/mco0053a.jpg}:: |
| داریم: | | داریم: |
| ::{picture=img/daneshnameh_up/a/a6/com0053aa.jpg} :: | | ::{picture=img/daneshnameh_up/a/a6/com0053aa.jpg} :: |
| --- | | --- |
| !!عمل پیوند دو گراف | | !!عمل پیوند دو گراف |
| پیوند {TEX()} {H,G} {TEX}، که به صورت{TEX()} {GVH} {TEX} نمایش داده می شود عبارت است از {TEX()} {G+H} {TEX} با افزودن یالهای زیر: | | پیوند {TEX()} {H,G} {TEX}، که به صورت{TEX()} {GVH} {TEX} نمایش داده می شود عبارت است از {TEX()} {G+H} {TEX} با افزودن یالهای زیر: |
| @@{TEX()} {\{uv | u\in V(G) , v \in V(H) \}} {TEX}@@ | | @@{TEX()} {\{uv | u\in V(G) , v \in V(H) \}} {TEX}@@ |
| --- | | --- |
| ! پیوند های خارجی | | ! پیوند های خارجی |
| [http://Olympiad.roshd.ir/computer/content/pdf/0085.pdf] | | [http://Olympiad.roshd.ir/computer/content/pdf/0085.pdf] |
| --- | | --- |
| !همچنین ببینید | | !همچنین ببینید |
| *((اجتماع دو گراف )) | | *((اجتماع دو گراف )) |
| *((حذف و انقباض )) | | *((حذف و انقباض )) |
| #@^ | | #@^ |