منو
 صفحه های تصادفی
سفارش امام صادق به امانت داری و راستگویی
خانه کاریکاتور ایران
دوستی فقرا با امام علی علیه السلام
تعاریف روان‏شناختى دین
جنگل بارانی
نوسانگر هماهنگ ساده
سختی ها در زمان ظهور امام مهدی علیه السلام
دیلتیازم
علم تندرستی
درس مدارهای الکتریکی
 کاربر Online
771 کاربر online
تاریخچه ی: عدد تقاطع

||V{maketoc}||
||__~~navy:@#13::: این مطلب از بخش آموزش وب‌سایت المپیاد ریاضی رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وب‌سایت المپیاد رشد]موجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین می‌توانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا))‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.:: #@~~__||
^@#16:
!عدد تقاطع{TEX()} {(Crossing \ Number} {TEX}
دیدیم که گرافهایی هستند که می شود آنها را در صفحه رسم کرد به طوری که هیچ دو یالی همدیگر را قطع نکنند – اما اگر گرافهای نامسطح را روی صفحه رسم کنیم چند یال به اجبار همدیگر را قطع خواهند کرد. حال مساله ای که اینجا می خواهیم بررسی کنیم تعداد این تقاطع ها {TEX()} {(Crossing)} {TEX} است.
به دو گراف زیر توجه کنید:
::{picture=img/daneshnameh_up/f/f2/mco0074a.jpg}::
در واقع هر دو یک گراف را نشان می دهند، ولی در شکل (الف) تعداد تقاطع ها یکی در حالی که در (ب) 2 تا می باشند.
اما به نظر شما آیا می توان این گراف را به گونه ای رسم کرد که یک تقاطع داشته باشد – در واقع چیزی که برای ما در این فصل جالب است،‌ شکلی از گراف است که کمترین تعداد تقاطع ها در آن یافت شود – به گراف {TEX()} {K_5} {TEX} دوباره نظری می اندازیم:
::{picture=img/daneshnameh_up/5/56/mco0074b.jpg}::
در شکل بالا 5 تقاطع مشخص اند. حال همین گراف را به گونه ی زیر دوباره می کشیم:
::{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()} {(Crossing \ Number)} {TEX} یک گراف مانند {TEX()} {G} {TEX} عبارتست از کمترین مقدار ممکن برای تعداد تقاطع های یالهای گراف {TEX()} {G} {TEX} در رسم های مختلف گراف {TEX()} {G} {TEX} در صفحه و آن را با {TEX()} {C_r(G)} {TEX} نمایش می دهند.
شکل زیر نشان می دهد که عدد تقاطع {TEX()} {K_{3,3}} {TEX} برابر 1 است. چرا؟
::{picture=img/daneshnameh_up/a/a9/mco0074d.jpg}::
حال می خواهیم عدد تقاطع {TEX()} {K_6} {TEX} را بدست آوریم:
::{picture=img/daneshnameh_up/b/b3/mco0074e.jpg}::
{TEX()} {K_6} {TEX} را می توان به صورت زیر نیز کشید که تعداد تقاطع های آن در این شکل 3 می باشد.
::{picture=img/daneshnameh_up/b/b2/mco0074f.jpg}::
حال فرض می کنیم که{TEX()} {K_6} {TEX} را بتوان به گونه ای رسم کرد که دارای 2 تقاطع باشد. راس ها را شماره گذاری می کنیم.
فرض کنیم دو تقاطع مذکور به شکل زیر باشند:
::{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} نا مسطح بوده و امکان ندارد.
در نتیجه{TEX()} {K_6} {TEX} را با کمتر از 3 تقاطع نمی توان رسم کرد. پس خواهیم داشت:
@@{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_{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_{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]

#@^

تاریخ شماره نسخه کاربر توضیح اقدام
 یکشنبه 14 آبان 1385 [11:39 ]   3   زینب معزی      جاری 
 چهارشنبه 22 شهریور 1385 [11:44 ]   2   زینب معزی      v  c  d  s 
 چهارشنبه 22 شهریور 1385 [11:43 ]   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 در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..