تاریخچه ی:
عدد تقاطع
تفاوت با نگارش: 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()} {(Crossing \ Number} {TEX} |
+ | !عدد تقاطع{TEX()} {(Crossing \ Number)} {TEX} |
| دیدیم که گرافهایی هستند که می شود آنها را در صفحه رسم کرد به طوری که هیچ دو یالی همدیگر را قطع نکنند – اما اگر گرافهای نامسطح را روی صفحه رسم کنیم چند یال به اجبار همدیگر را قطع خواهند کرد. حال مساله ای که اینجا می خواهیم بررسی کنیم تعداد این تقاطع ها {TEX()} {(Crossing)} {TEX} است. | | دیدیم که گرافهایی هستند که می شود آنها را در صفحه رسم کرد به طوری که هیچ دو یالی همدیگر را قطع نکنند – اما اگر گرافهای نامسطح را روی صفحه رسم کنیم چند یال به اجبار همدیگر را قطع خواهند کرد. حال مساله ای که اینجا می خواهیم بررسی کنیم تعداد این تقاطع ها {TEX()} {(Crossing)} {TEX} است. |
| به دو گراف زیر توجه کنید: | | به دو گراف زیر توجه کنید: |
| ::{picture=img/daneshnameh_up/f/f2/mco0074a.jpg}:: | | ::{picture=img/daneshnameh_up/f/f2/mco0074a.jpg}:: |
| در واقع هر دو یک گراف را نشان می دهند، ولی در شکل (الف) تعداد تقاطع ها یکی در حالی که در (ب) 2 تا می باشند. | | در واقع هر دو یک گراف را نشان می دهند، ولی در شکل (الف) تعداد تقاطع ها یکی در حالی که در (ب) 2 تا می باشند. |
| اما به نظر شما آیا می توان این گراف را به گونه ای رسم کرد که یک تقاطع داشته باشد – در واقع چیزی که برای ما در این فصل جالب است، شکلی از گراف است که کمترین تعداد تقاطع ها در آن یافت شود – به گراف {TEX()} {K_5} {TEX} دوباره نظری می اندازیم: | | اما به نظر شما آیا می توان این گراف را به گونه ای رسم کرد که یک تقاطع داشته باشد – در واقع چیزی که برای ما در این فصل جالب است، شکلی از گراف است که کمترین تعداد تقاطع ها در آن یافت شود – به گراف {TEX()} {K_5} {TEX} دوباره نظری می اندازیم: |
| ::{picture=img/daneshnameh_up/5/56/mco0074b.jpg}:: | | ::{picture=img/daneshnameh_up/5/56/mco0074b.jpg}:: |
| در شکل بالا 5 تقاطع مشخص اند. حال همین گراف را به گونه ی زیر دوباره می کشیم: | | در شکل بالا 5 تقاطع مشخص اند. حال همین گراف را به گونه ی زیر دوباره می کشیم: |
| ::{picture=img/daneshnameh_up/6/65/mco0074c.jpg}:: | | ::{picture=img/daneshnameh_up/6/65/mco0074c.jpg}:: |
| می بینیم که گراف {TEX()} {K_5} {TEX} را طوری رسم کردیم که تنها دارای یک تقاطع می باشد. از آنجا که {TEX()} {K_5} {TEX} یک گراف نامسطح است پس کمترین مقدار ممکن برای تعداد تقاطع های رسم این گراف یک می باشد. به این عدد یعنی عدد " یک" به اصطلاح عدد تقاطع یا {TEX()} {Crossing \ Number} {TEX} گراف {TEX()} {K_5} {TEX} گوییم. | | می بینیم که گراف {TEX()} {K_5} {TEX} را طوری رسم کردیم که تنها دارای یک تقاطع می باشد. از آنجا که {TEX()} {K_5} {TEX} یک گراف نامسطح است پس کمترین مقدار ممکن برای تعداد تقاطع های رسم این گراف یک می باشد. به این عدد یعنی عدد " یک" به اصطلاح عدد تقاطع یا {TEX()} {Crossing \ Number} {TEX} گراف {TEX()} {K_5} {TEX} گوییم. |
| تعریف. عدد تقاطع یا {TEX()} {(Crossing \ Number)} {TEX} یک گراف مانند {TEX()} {G} {TEX} عبارتست از کمترین مقدار ممکن برای تعداد تقاطع های یالهای گراف {TEX()} {G} {TEX} در رسم های مختلف گراف {TEX()} {G} {TEX} در صفحه و آن را با {TEX()} {C_r(G)} {TEX} نمایش می دهند. | | تعریف. عدد تقاطع یا {TEX()} {(Crossing \ Number)} {TEX} یک گراف مانند {TEX()} {G} {TEX} عبارتست از کمترین مقدار ممکن برای تعداد تقاطع های یالهای گراف {TEX()} {G} {TEX} در رسم های مختلف گراف {TEX()} {G} {TEX} در صفحه و آن را با {TEX()} {C_r(G)} {TEX} نمایش می دهند. |
| شکل زیر نشان می دهد که عدد تقاطع {TEX()} {K_{3,3}} {TEX} برابر 1 است. چرا؟ | | شکل زیر نشان می دهد که عدد تقاطع {TEX()} {K_{3,3}} {TEX} برابر 1 است. چرا؟ |
| ::{picture=img/daneshnameh_up/a/a9/mco0074d.jpg}:: | | ::{picture=img/daneshnameh_up/a/a9/mco0074d.jpg}:: |
| حال می خواهیم عدد تقاطع {TEX()} {K_6} {TEX} را بدست آوریم: | | حال می خواهیم عدد تقاطع {TEX()} {K_6} {TEX} را بدست آوریم: |
| ::{picture=img/daneshnameh_up/b/b3/mco0074e.jpg}:: | | ::{picture=img/daneshnameh_up/b/b3/mco0074e.jpg}:: |
| {TEX()} {K_6} {TEX} را می توان به صورت زیر نیز کشید که تعداد تقاطع های آن در این شکل 3 می باشد. | | {TEX()} {K_6} {TEX} را می توان به صورت زیر نیز کشید که تعداد تقاطع های آن در این شکل 3 می باشد. |
| ::{picture=img/daneshnameh_up/b/b2/mco0074f.jpg}:: | | ::{picture=img/daneshnameh_up/b/b2/mco0074f.jpg}:: |
| حال فرض می کنیم که{TEX()} {K_6} {TEX} را بتوان به گونه ای رسم کرد که دارای 2 تقاطع باشد. راس ها را شماره گذاری می کنیم. | | حال فرض می کنیم که{TEX()} {K_6} {TEX} را بتوان به گونه ای رسم کرد که دارای 2 تقاطع باشد. راس ها را شماره گذاری می کنیم. |
| فرض کنیم دو تقاطع مذکور به شکل زیر باشند: | | فرض کنیم دو تقاطع مذکور به شکل زیر باشند: |
| ::{picture=img/daneshnameh_up/3/36/mco0074g.jpg}:: | | ::{picture=img/daneshnameh_up/3/36/mco0074g.jpg}:: |
| طبق اصل لانه کبوتری حداقل دو راس از گراف در هر دو تقاطع دخالت دارند – ( اگر یالی با یال دیگر تقاطع داشته باشد، دو راس لبه ی یال را گوییم در تقاطع دخالت دارند ). حال اگر از این گراف راس شماره 4 را حذف کنیم چه می شود. دقت کنید که وقتی که راسی را حذف می کنیم یالهای مرتبط با آن نیز خود به خود حذف می شوند. آنچه از گراف می ماند در واقع {TEX()} {K_5} {TEX} است. اما برسر دو تقاطع چه می آیند. مسلماً با حذف راس 4 یالهای (4و1) و (4و5) نیز حذف گشته و در نتیجه هر دو تقاطع از بین می روند. یعنی توانسته ایم {TEX()} {K_5} {TEX} را روی صفحه مسطح رسم کنیم که می دانیم {TEX()} {K_5} {TEX} نا مسطح بوده و امکان ندارد. | | طبق اصل لانه کبوتری حداقل دو راس از گراف در هر دو تقاطع دخالت دارند – ( اگر یالی با یال دیگر تقاطع داشته باشد، دو راس لبه ی یال را گوییم در تقاطع دخالت دارند ). حال اگر از این گراف راس شماره 4 را حذف کنیم چه می شود. دقت کنید که وقتی که راسی را حذف می کنیم یالهای مرتبط با آن نیز خود به خود حذف می شوند. آنچه از گراف می ماند در واقع {TEX()} {K_5} {TEX} است. اما برسر دو تقاطع چه می آیند. مسلماً با حذف راس 4 یالهای (4و1) و (4و5) نیز حذف گشته و در نتیجه هر دو تقاطع از بین می روند. یعنی توانسته ایم {TEX()} {K_5} {TEX} را روی صفحه مسطح رسم کنیم که می دانیم {TEX()} {K_5} {TEX} نا مسطح بوده و امکان ندارد. |
| در نتیجه{TEX()} {K_6} {TEX} را با کمتر از 3 تقاطع نمی توان رسم کرد. پس خواهیم داشت: | | در نتیجه{TEX()} {K_6} {TEX} را با کمتر از 3 تقاطع نمی توان رسم کرد. پس خواهیم داشت: |
| @@{TEX()} {C_r(K_6)=3} {TEX}@@ | | @@{TEX()} {C_r(K_6)=3} {TEX}@@ |
| دیدیم که محاسبه ی عدد تقاطع یک گراف نسبتاً دشوار است با این حال روابط و نامساویهای زیر برای برخی از گراف ها موجوداند که بدون اثبات آنها را ذکر می کنیم: | | دیدیم که محاسبه ی عدد تقاطع یک گراف نسبتاً دشوار است با این حال روابط و نامساویهای زیر برای برخی از گراف ها موجوداند که بدون اثبات آنها را ذکر می کنیم: |
| @@{TEX()} {C_r(K_n) \le \frac{1}{4} \Bigg[ \frac{n}{2} \Bigg] \Bigg[ \frac{n-1}{2} \Bigg] \Bigg[ \frac{n-2}{2} \Bigg] \Bigg[ \frac{n-3}{2} \Bigg]} {TEX}برای هر {TEX()} {n} {TEX}(1) @@ | | @@{TEX()} {C_r(K_n) \le \frac{1}{4} \Bigg[ \frac{n}{2} \Bigg] \Bigg[ \frac{n-1}{2} \Bigg] \Bigg[ \frac{n-2}{2} \Bigg] \Bigg[ \frac{n-3}{2} \Bigg]} {TEX}برای هر {TEX()} {n} {TEX}(1) @@ |
| @@{TEX()} {C_r(K_{m,n}) \le \Bigg[ \frac{m}{2} \Bigg] \Bigg[ \frac{m-1}{2} \Bigg] \Bigg[ \frac{n}{2} \Bigg] \Bigg[ \frac{n-1}{2} \Bigg]} {TEX}برای هر {TEX()} {m,n} {TEX}(2)@@ | | @@{TEX()} {C_r(K_{m,n}) \le \Bigg[ \frac{m}{2} \Bigg] \Bigg[ \frac{m-1}{2} \Bigg] \Bigg[ \frac{n}{2} \Bigg] \Bigg[ \frac{n-1}{2} \Bigg]} {TEX}برای هر {TEX()} {m,n} {TEX}(2)@@ |
| @@{TEX()} {C_r(K_{3,n})=\Bigg[ \frac{n}{2} \Bigg] \Bigg[ \frac{n-1}{2} \Bigg]} {TEX} برای هر {TEX()} {n} {TEX}(3)@@ | | @@{TEX()} {C_r(K_{3,n})=\Bigg[ \frac{n}{2} \Bigg] \Bigg[ \frac{n-1}{2} \Bigg]} {TEX} برای هر {TEX()} {n} {TEX}(3)@@ |
| @@{TEX()} {C_r(K_{4,n} )=2 \Bigg[ \frac{n}{2} \Bigg] \Bigg[ \frac{n-1}{2} \Bigg]} {TEX}برای هر {TEX()} {n} {TEX}(4)@@ | | @@{TEX()} {C_r(K_{4,n} )=2 \Bigg[ \frac{n}{2} \Bigg] \Bigg[ \frac{n-1}{2} \Bigg]} {TEX}برای هر {TEX()} {n} {TEX}(4)@@ |
| --- | | --- |
| ! پیوند های خارجی | | ! پیوند های خارجی |
| [http://Olympiad.roshd.ir/computer/content/pdf/0120.pdf] | | [http://Olympiad.roshd.ir/computer/content/pdf/0120.pdf] |
| #@^ | | #@^ |