منو
 کاربر Online
455 کاربر online
تاریخچه ی: نظریه گراف (المپیاد)

||V{maketoc}||
||__~~navy:@#13::: این مطلب از بخش آموزش وب‌سایت المپیاد کامپیوتر رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وب‌سایت المپیاد رشد]موجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین می‌توانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا))‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.:: #@~~__||
^@#16:
گراف یکی از زیباترین مباحث ((ریاضیات گسسته)) و حتی به نظر من کل ((ریاضیات)) می باشد!
بزرگترین خصوصیت آن شهودی و ملموس بودنش می باشد به گونه ای که کمتر مطلبی در آن یافت می شود که نشود فهمیدش !
حتماً‌ تا حالا بازی های زیادی روی کاغذ انجام داده اید مانند مسابقه برای کشیدن پاکت نامه ای به صورت زیر به شرطی که قلم را از روی کاغذ بر نداریم و از یک جا شروع و به همانجا برگردیم.
::{picture=img/daneshnameh_up/b/bd/mco0045a.jpg}::
و یا نقطه بازی به این صورت که جدولی از نقاط داریم و هر نفر در نوبت خود دو ((نقطه)) مجاور را به هم وصل می کند و ...
::{picture=img/daneshnameh_up/3/3c/mco0045b.jpg}::
اینها همه به شکلی به نظریه گراف مربوط می گردند.
و یا مسائل پر کاربرد دیگری مانند خیابانهای یک شهر و میادین و تقاطع ها به عنوان نقاط برخورد آنها و این مسئله که ترافیک چگونه کنترل گردد یا کدام خیابانها یک طرفه و کدام ها دو طرفه بشوند نیز جزئی از همین مقوله می باشند.
به طور کلی تر گراف مجموعه ای است از نقاط یا گروه ها که ما به آنها راس خواهیم گفت و تعداد خطوط متصل کننده این رئوس یا همان خیابانهای شهر که ما به آنها یال خواهیم گفت از آنجا که در گراف فقط مجموعه رئوس و یالهاست که ((گراف)) را تعریف می کند آنگاه گراف هایی مانند
::{picture=img/daneshnameh_up/4/4c/mco0045c.jpg}::
یکسان خواهند بود که ما به آنها یکریخت می گوییم.
از این به بعد در محل تقاطع یالهایی که در آن تقاطع راسی وجود دارد نقطه تو پر می گذاریم و گرنه آن تقاطع بیانگر وجود راس نخواهد بود مانند دو گراف زیر که به همین دلیل اولی 5 راس و دومی 4 راس دارد.
::{picture=img/daneshnameh_up/2/2f/mco0045d.jpg}::
ضمناً حتی گراف های
::{picture=img/daneshnameh_up/f/f4/mco0045e.jpg}::
نیز یکسان یا ((یکریخت)) می باشند زیرا با تبدیلی از رئوس اولی به دومی می توان آنها را به هم تبدیل کرد بدین صورت که در اولی فقط اندیس {TEX()} {V_4,V_3} {TEX} باید تعویض گردند. ( به تعریف دقیقتر ((یکریختی)) خواهیم پرداخت)
اما اگر از لحاظ شهودی هم بخواهیم به این موضوع بپردازیم گرافهای یکریخت گرافهایی اند که بدون قطع کردن اتصال یالها و یا افزودن یالهای جدید تنها با جابجایی رئوس و یالهای مربوط به آن ها در فضا، بتوان آنها را به هم تبدیل کرد.
مانند مثال قبل که به این صورت به هم تبدیل می گردند. ( فلش ها به معنی راستای جابجایی آن راس می باشد)
::{picture=img/daneshnameh_up/b/be/mco0045f.jpg}::
به انیمیشنی که دو گراف یکسان را با حرکت رئوس در صفحه به یکدیگر تبدیل می کند دقت کنید:
لینک به انیمیشن شماره 6
در این میان یالها یا همان ارتباط دهنده های میان رئوس به چند صورت می توانند باشند:
یا جهت دار باشند مانند خیابانهای یکطرفه که اتصال رئوس را تنها در یک جهت معین برقرار می کنند که درشکل متناظر ((گراف)) هم با یک فلش مشخص می گردند.
یا یالهایی باشند که یک راس را به خودش متصل می کنند که به آن ((حلقه)) خواهیم گفت. یا یالهای چندگانه باشند یعنی بین دو راس خاص بیش از یک یال باشد.
و یا آنکه یال ساده باشند یعنی هیچ کدام از موارد فوق نباشد.
---
!!مثال
::{picture=img/daneshnameh_up/b/ba/mco0045g.jpg}::
::||گراف جهت دار با یالهای جهت دار که در میان یالهای جهت دار آن یال {TEX()} {E_1} {TEX} حلقه نیز می‌باشد.||::
::||{picture=img/daneshnameh_up/8/85/mco0045h.jpg}::
::{TEX()} {E_1,E_7} {TEX} :حلقه::
::{TEX()} {E_4,E_3,E_2} {TEX}:چند گانه::
::{TEX()} {E_6,E_5} {TEX} : ساده||::
---
! پیوند های خارجی
[http://Olympiad.roshd.ir/computer/content/pdf/0059.pdf]
---
!همچنین ببینید
*((تعریف گراف ))
*((مثالهایی از گراف ها ))
*((مسیرها و دورها ))
#@^

تاریخ شماره نسخه کاربر توضیح اقدام
 یکشنبه 14 آبان 1385 [11:17 ]   6   زینب معزی      جاری 
 یکشنبه 14 آبان 1385 [11:17 ]   5   زینب معزی      v  c  d  s 
 یکشنبه 14 آبان 1385 [11:17 ]   4   زینب معزی      v  c  d  s 
 یکشنبه 19 شهریور 1385 [09:28 ]   3   زینب معزی      v  c  d  s 
 یکشنبه 19 شهریور 1385 [05:14 ]   2   زینب معزی      v  c  d  s 
 یکشنبه 19 شهریور 1385 [05:12 ]   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 در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..