مقالت حاضره مهندس میتونی نوش جان کنی!

مقدمه:

نظريه گراف شاخه اي از رياضيات است كه درباره ي اشياء خاصي دررياضي به نام گراف بحث مي كند. به صورت شهودي گراف نمودار يا دياگرافي است شامل تعدادي راس كه با يالهايي به هم متصل شده اند. تعريف دقيق تر گراف به اين صورت است كه گراف مجموعه اي از راس هاست كه توسط خانواده اي از زوج هاي مرتب كه همان يالهاست به هم مرتبط شده اند. يالها بر دو نوع ساده و جهت دار هستند كه هر كدام در جاي خود كاربرد بسياري دارد. مثلا اگر صرفا اتصال دو نقطه مانند اتصال تهران و زنجان با كمك آزاد راه مد نظر شما باشد كافيست آن دو شهر را با دو نقطه نمايش داده و اتوبان مزبور را يالي ساده نمايش دهيد. اما اگر بين دو شهر جاده اي يكطرفه وجود داشته باشد آنگاه لازمست تا شما با قرار دادن يالي جهت دار مسير حركت را در آن جاده مشخص كنيد. آغاز نظريه ي گراف به سده ي هجدهم بر مي گردد. اويلر رياضيدان بزرگ مفهوم گراف را براي حل مسئله ي پل هاي كونيگسربگ ابداع كرد، اما رشد و پويايي اين نظريه عمدتا مربوط به نيم سده ي اخير و با رشد علم داده ورزي (انفورماتيك) بوده است. مهمترين كاربرد گراف مدل سازي پديده هاي گوناگون و بررسي بر روي آنهاست. با گراف مي توان به راحتي يك نقشه بسيار بزرگ يا شبكه اي عظيم را درون يك ماتريس به نام ماتريس وقوع گراف ذخيره كرد و يا الگوريتم هاي مناسب مانند الگوريتم دايسترا يا الگوريتم كروسكال و.... را برروي آن اعمال نمود...