منو
 کاربر Online
1340 کاربر online

نظریه گراف (المپیاد)

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



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


گراف یکی از زیباترین مباحث ریاضیات گسسته و حتی به نظر من کل ریاضیات می باشد!
بزرگترین خصوصیت آن شهودی و ملموس بودنش می باشد به گونه ای که کمتر مطلبی در آن یافت می شود که نشود فهمیدش !
حتماً‌ تا حالا بازی های زیادی روی کاغذ انجام داده اید مانند مسابقه برای کشیدن پاکت نامه ای به صورت زیر به شرطی که قلم را از روی کاغذ بر نداریم و از یک جا شروع و به همانجا برگردیم.
img/daneshnameh_up/b/bd/mco0045a.jpg

و یا نقطه بازی به این صورت که جدولی از نقاط داریم و هر نفر در نوبت خود دو نقطه مجاور را به هم وصل می کند و ...
img/daneshnameh_up/3/3c/mco0045b.jpg

اینها همه به شکلی به نظریه گراف مربوط می گردند.
و یا مسائل پر کاربرد دیگری مانند خیابانهای یک شهر و میادین و تقاطع ها به عنوان نقاط برخورد آنها و این مسئله که ترافیک چگونه کنترل گردد یا کدام خیابانها یک طرفه و کدام ها دو طرفه بشوند نیز جزئی از همین مقوله می باشند.
به طور کلی تر گراف مجموعه ای است از نقاط یا گروه ها که ما به آنها راس خواهیم گفت و تعداد خطوط متصل کننده این رئوس یا همان خیابانهای شهر که ما به آنها یال خواهیم گفت از آنجا که در گراف فقط مجموعه رئوس و یالهاست که گراف را تعریف می کند آنگاه گراف هایی مانند
img/daneshnameh_up/4/4c/mco0045c.jpg

یکسان خواهند بود که ما به آنها یکریخت می گوییم.
از این به بعد در محل تقاطع یالهایی که در آن تقاطع راسی وجود دارد نقطه تو پر می گذاریم و گرنه آن تقاطع بیانگر وجود راس نخواهد بود مانند دو گراف زیر که به همین دلیل اولی 5 راس و دومی 4 راس دارد.
img/daneshnameh_up/2/2f/mco0045d.jpg

ضمناً حتی گراف های
img/daneshnameh_up/f/f4/mco0045e.jpg

نیز یکسان یا یکریخت می باشند زیرا با تبدیلی از رئوس اولی به دومی می توان آنها را به هم تبدیل کرد بدین صورت که در اولی فقط اندیس باید تعویض گردند. ( به تعریف دقیقتر یکریختی خواهیم پرداخت)
اما اگر از لحاظ شهودی هم بخواهیم به این موضوع بپردازیم گرافهای یکریخت گرافهایی اند که بدون قطع کردن اتصال یالها و یا افزودن یالهای جدید تنها با جابجایی رئوس و یالهای مربوط به آن ها در فضا، بتوان آنها را به هم تبدیل کرد.
مانند مثال قبل که به این صورت به هم تبدیل می گردند. ( فلش ها به معنی راستای جابجایی آن راس می باشد)
img/daneshnameh_up/b/be/mco0045f.jpg

به انیمیشنی که دو گراف یکسان را با حرکت رئوس در صفحه به یکدیگر تبدیل می کند دقت کنید:
لینک به انیمیشن شماره 6
در این میان یالها یا همان ارتباط دهنده های میان رئوس به چند صورت می توانند باشند:
یا جهت دار باشند مانند خیابانهای یکطرفه که اتصال رئوس را تنها در یک جهت معین برقرار می کنند که درشکل متناظر گراف هم با یک فلش مشخص می گردند.
یا یالهایی باشند که یک راس را به خودش متصل می کنند که به آن حلقه خواهیم گفت. یا یالهای چندگانه باشند یعنی بین دو راس خاص بیش از یک یال باشد.
و یا آنکه یال ساده باشند یعنی هیچ کدام از موارد فوق نباشد.

مثال

img/daneshnameh_up/b/ba/mco0045g.jpg

گراف جهت دار با یالهای جهت دار که در میان یالهای جهت دار آن یال حلقه نیز می‌باشد.

img/daneshnameh_up/8/85/mco0045h.jpg
:حلقه
:چند گانه
: ساده


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

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

همچنین ببینید




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


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