منو
 صفحه های تصادفی
خوارج
ترکیب رنگهای RGB
تیس
مقام حضرت علی علیه السلام در پیشگاه خداوند
روشهای اندازه گیری سختی و دوام سنگ
هیدروکسیل دار شدن، تشکیل دیولهای -1، 2
دیدار امام علی علیه السلام برای دوست و دشمن هنگام مرگ
سلاجقه کرمان
زهد در دوران زندگی
فلایویل
 کاربر Online
304 کاربر online

عدد تقاطع

تازه کردن چاپ
علوم ریاضی > علو م رایانه
(cached)


این مطلب از بخش آموزش وب‌سایت المپیاد کامپیوتر رشد،انتخاب شده که با فرمت pdf نیز در وب‌سایت المپیاد رشدموجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس فهرست مطالب کامپیوتر مراجعه کنید. همچنین می‌توانید با کلیک اینجا‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.


عدد تقاطع

دیدیم که گرافهایی هستند که می شود آنها را در صفحه رسم کرد به طوری که هیچ دو یالی همدیگر را قطع نکنند – اما اگر گرافهای نامسطح را روی صفحه رسم کنیم چند یال به اجبار همدیگر را قطع خواهند کرد. حال مساله ای که اینجا می خواهیم بررسی کنیم تعداد این تقاطع ها است.
به دو گراف زیر توجه کنید:
img/daneshnameh_up/f/f2/mco0074a.jpg

در واقع هر دو یک گراف را نشان می دهند، ولی در شکل (الف) تعداد تقاطع ها یکی در حالی که در (ب) 2 تا می باشند.
اما به نظر شما آیا می توان این گراف را به گونه ای رسم کرد که یک تقاطع داشته باشد – در واقع چیزی که برای ما در این فصل جالب است،‌ شکلی از گراف است که کمترین تعداد تقاطع ها در آن یافت شود – به گراف دوباره نظری می اندازیم:
img/daneshnameh_up/5/56/mco0074b.jpg

در شکل بالا 5 تقاطع مشخص اند. حال همین گراف را به گونه ی زیر دوباره می کشیم:
img/daneshnameh_up/6/65/mco0074c.jpg

می بینیم که گراف را طوری رسم کردیم که تنها دارای یک تقاطع می باشد. از آنجا که یک گراف نامسطح است پس کمترین مقدار ممکن برای تعداد تقاطع های رسم این گراف یک می باشد. به این عدد یعنی عدد " یک" به اصطلاح عدد تقاطع یا گراف گوییم.
تعریف. عدد تقاطع یا یک گراف مانند عبارتست از کمترین مقدار ممکن برای تعداد تقاطع های یالهای گراف در رسم های مختلف گراف در صفحه و آن را با نمایش می دهند.
شکل زیر نشان می دهد که عدد تقاطع برابر 1 است. چرا؟
img/daneshnameh_up/a/a9/mco0074d.jpg

حال می خواهیم عدد تقاطع را بدست آوریم:
img/daneshnameh_up/b/b3/mco0074e.jpg

را می توان به صورت زیر نیز کشید که تعداد تقاطع های آن در این شکل 3 می باشد.
img/daneshnameh_up/b/b2/mco0074f.jpg

حال فرض می کنیم که را بتوان به گونه ای رسم کرد که دارای 2 تقاطع باشد. راس ها را شماره گذاری می کنیم.
فرض کنیم دو تقاطع مذکور به شکل زیر باشند:
img/daneshnameh_up/3/36/mco0074g.jpg

طبق اصل لانه کبوتری حداقل دو راس از گراف در هر دو تقاطع دخالت دارند – ( اگر یالی با یال دیگر تقاطع داشته باشد،‌ دو راس لبه ی یال را گوییم در تقاطع دخالت دارند ). حال اگر از این گراف راس شماره 4 را حذف کنیم چه می شود. دقت کنید که وقتی که راسی را حذف می کنیم یالهای مرتبط با آن نیز خود به خود حذف می شوند. آنچه از گراف می ماند در واقع است. اما برسر دو تقاطع چه می آیند. مسلماً‌ با حذف راس 4 یالهای (4و1) و (4و5) نیز حذف گشته و در نتیجه هر دو تقاطع از بین می روند. یعنی توانسته ایم را روی صفحه مسطح رسم کنیم که می دانیم نا مسطح بوده و امکان ندارد.
در نتیجه را با کمتر از 3 تقاطع نمی توان رسم کرد. پس خواهیم داشت:

دیدیم که محاسبه ی عدد تقاطع یک گراف نسبتاً‌ دشوار است با این حال روابط و نامساویهای زیر برای برخی از گراف ها موجوداند که بدون اثبات آنها را ذکر می کنیم:
برای هر (1)

برای هر (2)

برای هر (3)

برای هر (4)


پیوند های خارجی

http://Olympiad.roshd.ir/computer/content/pdf/0120.pdf




تعداد بازدید ها: 10172


ارسال توضیح جدید
الزامی
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 در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..