دانلود مقاله ریاضیات گسسته

بخشی از مقاله

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

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

رياضيات گسسته مقدماتي متني فشرده برابر يك دوره رياضيات گسسته در سطحي مقدماتي براي دانشجويان كارشناسي علوم كامپيوتر و رياضيات است. مولفه هاي اساسي برنامه كار ريا ضيات گسسته در سطحي مقد ماتي عبارتند از : تركيبات نظريه گرا فها همراه با كار بردهايي در چند مسئاله استاندارد

بهينه سازي شبكه ها، الگوريتمهايي براي حل اين مسائل مهم اتحاديه سازندگان ماشينهاي محاسبه و مهم كميته برنامه ريزي يراي كارشناسي ريا ضي بر نقش حياتي يك دوره درسي روشهاي گسسته در سطح كارشناسي كه دانشجويان را به حيطه رياضيات تركيباتي و ساختارهاي جبري و منطقي وارد كند و روي ارتباط متقابل علوم كامپيوتر و رياضيات تأكيد داشته باشد صحه گذاشته اند.

جايگاه و ضرورت آموزش رياضيات گسسته در نظام جديد دبيرستاني
در جريان تغيير نظام آموزش دوره هاي كارشناسي رياضي در سالهاي اخير در دانشگاهها و موسسات آموزش عالي شاهد بوديم كه درسهاي جديد به تنا سب گرايشهاي اين رشته جايگزين درسهايي از نظام قبلي شدند. درس ريا ضيات گسسته نيز به ارزش 4 واحد درسي در اين راستا بعنوان يكي از واحدهاي پايه همه گرايشهاي دوره كارشناسي رياضي در نظر گرفته شده است. در كتابهاي درسي ريا ضي نظام جديد دبيرستان نيز شاهد گنجاندن مفاهيم پايه اي مربوط به مباحث مقدماتي رياضيات گسسته مانند نظريه گراف و دنباله ها و آمار و احتمال و ... مي باشيم.

همچنين در دوره پيش دانشگاهي نيز درسي جداگانه تحت عنوان رياضيات گسسته در نظر گرفته شده است. از آنجا كه اين شاخه از رياضي نياز مند بحث و تبادل نظر از لحاظ آموزشي و تعيين جايگاه و ارتباط آن با ساير شاخه ها و موضوعات رياضي مي باشد.

مطالبي كه در اين قسمت از بحث طرح خواهد شد بيشتر بر اساس مقاله اي است كه تحت عنوان »آموزش رياضي گسسته در دوره دبيرستان« توسط پروفسور آ.كاتلين

در مجلة بين المللي رياضيات، علم و تكنولوژي 1990 درج شده است.
» انقلاب كامپيوتري، رياضيات گسسته را همانند حساب ديفرانسيل و انتگرال براي علم و تكنولوژي ضروري ساخته است.«

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

به طور كلي يك دوره رياضيات گسسته را مي توان شامل عناوين زير دانست:
منطق راضي و نظريه مجموعه ها ، ساختار هاي جبري از قبيل مباحث مربوط به گروهها و حلقه ها و ميدانها و كواتريونها، شببكه ها جبر يون، نظريه گراف، روشهاي تركيبات و شمارش، نظريه اعداد محاسبات و الگوريتمهاي عددي و تجزيه و تحليل آنها، استقرار و روابط بازگشتي معادلات تفاضلي،آمار و احتمال با فضاهاي نمونه اي گسسته.

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

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

شوند نوعاَ به صورت معادلات ديفرانسيل درآيند. اين عملكرد آنچنان موفقيت شگفت انگيزي داشته است ك نتايج حاصل از آن تقريباَبراي همه مقاصد و اهداف ذاتاَ دقيق اند و موفقيت مهندسي وصنعت در قرنهاي اخير در سراسز دنيا مرهون اين مدل سازي زيبا و دقيق و كار بردي رياضي است، خصوصاَ از زماني كه

پيدايش حسابگرهاي رقمي و سپس كامپيوترها امكان بررسي و حل عددي معادلات ديفرانسيل و ديگر معادلات را فراهم نمودند. اين آغاز شكوفايي آناليز عددي بود نمونه متعارف از مسائلي كه با استفاده از تكنيكهاي آناليز عددي حل مي شوند اين است كه فرمول بندي يك مساله فيزيكي را با استفاده از حساب ديفرانسيل و انتگرال در نظر بگيريم و سپس آن را به شكل گسسته تبديل كنيم تا با روشهاي عددي قابل حل باشد. چنانچه در نمودار سيكلي مدل سازي

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

نقش مقايسه كردني با حساب ديفرانسيل و انتگرال دارد. آناليز عددي با وجود كار بردهاي وسيع، آن موضوعي تخصصي است نمي تواند تأثير چشمكيري بر روند دآموزشي رياضيات بگذارد هر چند آناليز عددي مهمترين محل تلاقي رياضيات پيوسته گسسته است امروزه تنها يك جزء كوچك از كار بردهاي رياضيات گسسته را در‌بر‌مي‌گيرد.

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

اضافه كرد كه مدل رياضي مسائل فوق عوض اينكه به صورت معادله ديفرانسيل در آيد به صورت يك معادله تفاضلي در آمد كه چون حل معا دله تفاضلي خود به صورت مقادير گسسته مي باشد لذا نيازي به آناليز عددي و تقريب جواب نيز نمي باشد بنابر اين چون براي حل بيشتر اين مسائل به رياضيات گسسته نياز داريم در آينده رياضيات گسسته به طور فزاينده اي در مركز توجه رياضيات كاربردي قرار خواهد گرفت.نكته اين نيست كه در رياضيات كاربردي، رياضيات گسسته از آناليز مهمتر خواهد بود يا نه در هر حال مساله مهم اين است كه هردو به اندازه كا في مهم خواهند بود به طوري كه اگر كسي بخواهد در رياضيات يا هر رشته

اي كه تنگاتنگ به ريا ضيات وابسته است پيشرفتي داشته باشذنمي تواند از دانستن رياضيات كاربردي كلاسيك يا ريا ضيات گسسته يعني ريا ضيات كاربردي جديد چشم بپوشد.

چنانچه قبلانيز اشاره شد بايد توجه كرد كه ريا ضيات گسسته و پيوسته وجه تمايز قاطعي ندارند بعضي از شاخه هاي رياضيات، شامل عناصري از هر دونوع گسسته و پيوسته هستند.

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

مرور تاريخي مباحث مهم رياضيات گسسته:
• تجزيه مسائل به اجزايي كه براي حل به فرمولهاي همانند يا متفاوتي نياز دارند بينشي كليدي در پهنه هاي رياضيات گسسته و تركيباتي فراهم كرد اين چيزي شبيه به روش از بالا به پايين براي بسط الگوريتمها در زبان ساخت يا فته اي نظير زبان پاسكال است. در اين روش براي حل مساله اي مشكل ابتدا الگوريتمي را با در نظر گرفتن اجزاي فرعي مهم مسائل كه نياز به حل دارند تهيه مي كنند سپس اين اجزاي فرعي بيشتر پالائيده شده – به كارهاي انجام پذير برنامه ريزي ساده تري تقسيم مي‌شوند هر سطح پالايش، روشني، دقت و جامعيت الگوريتم را بهبود مي بخشد تا به راحتي قابل ترجمه به كد زبان برنامه ريزي شود.
مفهوم جايگشت را مي توان در اثر عبري( كتاب آفرنش) دستخوشي عرفاني كه در زماني بين 200تا600 سال قبل از ميلاد نوشته شده است يافت . اما حتي قبل از آن جالب است كه بگوئيم قضيه اي از خنوكراتس اهل جالسدون(396-314 قبل از ميلاد) در دست است كه احتمالاَممكن است شامل » اولين تلاش در ثبت حل مسأله اي مشكل در جايگشتها و تركيبها باشد.«

اولين فن حدس زدن (Ars Conjectandi) نوشته ياكوب برنولي(1654-1705 ) نخستين كتاب درسي است كه پاره اي از مطالب اين بحث را مورد بررسي قرار داده است اين كتاب در سال 1731 پس از مرگ برنولي منتشر شد و شامل چاپ تازه اولين رسالة رسمي دربارة احتمال است كه در 1675 كريستيان هوينگس نوشته است.

در 1837 پترگوستاف لوژون ديريكله (1805-1859) فرمولبندي دقيقتري را از مفاهيم متغير، تابع، و تناظر بين متغير مستقلx ومتغير وابسته y ، وقتي پي ريزي كرد كارديله بر بستگي بين دو مجموعه از اعداد تأكيد داشت و منربوط به وجود فرمول يا عبارتي كه دو مجموعه را به هم مربوط كند بشود. با پيشرفتهايي كه در نظريه مجموعه ها در طي قرنهاي نوزده و بيست صورت گرفت تعميم تابع به صورت نوعي خاص از رابطه در آمد.
ديركله علاوه بر كار اساس اش دربارة تعريف تابع در رياضيات كاربردي و در نظرية اعداد نيز كاملاَ فعال بوددر همين جا بود كه نياز به اصل لانة كبوتررا كه اغلب به آن اصل كشوي ديريكله هم مي گويند دريافت.

• اعدا استرلينگ به ا فتخار جيمز استرلينگ(1692-1770) كه در بسط تابعهاي مولد پيشگام بوده است، به اين نام خوانده شده اند.
اصل شمول و عدم شمول تاريخچة جالبي دارد كه در نوشته هاي مختلف تحت نامهايي نظير » روش غربال« يا » ا صل رده بندي حذ في« وجود دارد يك صورت نظرية مجموعه اي اين اصل كه با اجتماعها و اشتراكها سر وكار دارد در اصول شانسها (1718) كتابي درسي دربارة نظرية احتمال اثر آبرام دمواورآمده است كمي پيشتر از آن در1713 پي ريمون دمونمورانديشة زير بنايي اين اصل را در حل مسأله‌اي كه عموماَ به مسأله پريشيها معروف است به كار برد.
امتياز اين نحوة بسط و پرداختن به اين اصل، از آن جيمز جوزف سيلوستراست ولي اهميت اين تكنيك تا زماني كه نوشته هاي ويت ورت رياضيدانان را از توان واستفادة آن آگاه نكرده بود،به طور كلي درك نشده بود.

نظرية گراف
يكي از شاخه هاي مهم رياضيات در حالتي گسترده با موضوعات مختلف نظريه گراف مي باشد . نظريه گراف يكي از كاربردي ترين شاخه هاي رياضيات گسسته است يكي از محبوبترين و پربارترين شاخه هاي رياضيات و علوم كامپيوتري است.
يكي از دلايل مهم اين علاقه به نظريه گرا فها در قابليت كاربرد آن در بسياري از مسايل پيچيده و گسترده جامعه مدرن در زمينه هاي گوناگون نظير ا قتصاد، توزيع، خدمات، مديريت، بازاريابي ، مدلسازي انرژي، انتقال اطلاعات و برنامه‌ريزي حمل و نقل نهفته است، از اين جهت نظريه گرافها را نخست و قبل از همه به عنوان ابزاري براي فرمولبندي مسائل و تعريف روابط متقابل ساختاري به كار مي گيرند.رشته نظريه گرافها داراي دوشاخه متفاوت است 1- جنبه هاي جبري
2- جنبه هاي بهينه سازي
مسأله پل كونيگسبرگ:

نخستين مطلب منتشر شده درباره نظريه گرا فها از لئونهارت اويلرسوئيسي در 1736 بود مقاله او راه حل را براي مسئله اي كه بنام مسئله بل كونيكسبرگ مشهور است ارائه مي كردشهر كونيكسبرگ در روسيه كه در كنار رود پرگل واقع شده است از شاخص شمالي(N) ساحل جنوبي (S )جزيره غربي(W) و جزيره شرقي(E) تشكيل شده است. ارتباط بين اين چهار قسمت به وسيله هفت پل برقرار مي شد.دوپل بينN وW دوپل بين S وW و يك پل ازE به هر يك ازNوS وW

(مطابق شكل)مسئله اي كه اويلر مطرح كرد اين بود كه »آيا امكان دارد از جايي در شهر شروع به حركت كرد و پس از پيمودن هر پل دقيقاَيكبار به نقطه شروع بازگشت يا نه؟« اگر هر قسمت شهر بعنوان يك رأس و هر پل بعنوان يك يا ل تلقي شود. گراف با چهار رأس، هفت بال داريم كه مدلسازي مسئله نامبرده را به زبان گرافها به دست مي دهد كه مي توان مسئله را به اين شرح بيان كرد: گرافي (نه لزوماَ ساده) مفروض است، آيا امكان دارد كل نمودار اين گراف را چنان پيمود كه از روي هر بال بيش از يك بار عبور بكنيم؟

اويلر به آساني ثابت كرد كه در مورد مسئله بل كونيكسبرگ پاسخ منفي است.

- طريقه نمايش گراف

نقاطP ،Q ،R ،S ،T ،رئوس(Vertices )و خطوطي كه رئوس را با هم وصل مي كند ضلع (e d g e )ناميده مي شودتوجه داريم كه محل تلاقي QT وPS يك رأس نيست اين دياگرام را يك گراف(g r a p h ) مي ناميم. درجه (d e g r e e )يك رأس A در يك گراف ، برابر تعداد اضلاعي است كه رأس A نقطة انتهايي آنها مي باشد.لذا درجه Q برابر با4 است. يك گراف را مي توان به طرق مختلف نمايش داد مثلاَمي توانستيم ضلع S وP را خارج ا ز مستطيل رسم كنيم چون گرافي را كه مي سازيم مشخص مجموعه اي از نقاط و راههايي است كه آنها را به هم وصل مي كند خواص متريك در آنها صادق نيستند لذا از اين ديدگاه هردو گرافي كه داراي يك ساختار باشند، نمايانگر يك گراف خواهند بود مانند شكلهاي(الف و ب).

يالها ممكن است بدون جهت باشنديا جهت داشته باشند كه در حالت اخير آن را گراف جهت دار يا دي گراف مي ناميم.

گراف هاميلتوني
رياضيدان شهير ايرلندي سر ويليام هاميلتون (1805-1865) است كه وجود جوابي براي بازي » دوددينا« را مورد پژوهش قرار داد.دراين بازي از يازيكن خواسته مي شود كه راهي در امتداد يالهايي يك دوازده وجهي ( يك چند وجهي منظم با20 رأس،80 يال و12 وجه) چنان بيابد كه از هررأس دقيقاَ يك بار بگذرد و سپس به رأس شروع حركت باز گردد بدين سان اين بازي داراي جواب است اگر فقط G يك گراف هاميلتوني باشد.

تعريف: مسيري بين هر دو رأس گراف كه از هر رأس دقيقاَيك بار بگذرد.مسيرها ميلتوني گويند . مسيري بسته را كه از هر دقيقاَ يك بار بگذرد و در آن همه يالها متمايز باشند دور هاميلتوني مي نامند. گرافي را گراف هاميلتوني گويند هرگاه دور هاميلتون داشته باشد.

يكي ازمعروفترين مسائل در نظريه گراف،مسئله چهار رنگ است، هر چند كه اين مسئله در اصل مربوط به نقشه هاست نه گرا فها، اما حل آن با گراف است.

نقشه اي با 48 ايالت همجوار را در نظر بگيريد مسأله اين است كه كمترين تعداد رنگهايي كه لازم است تا نقشه را چنان رنگ آميزي كنيم كه هيچ دو ناحيه هم مرز(كه در بيش از يك نقطه هم مرزند و ناحيه يك تكه اند) رنگ مشابهي نداشته باشندد چند تاست؟ گرچه اين مسأله بيشتر از لحاظ رياضي مهم است تا از لحاظ جغرا فيايي، ولي ممكن است براي مثال بر كار نقاشي كه مي خواهد يك اطلس را رنگ آميزي كند، و بايد بداند كه چند رنگ مركب لازم خواهد داشت اثر بگذارد. قضيه چهار رنگ بيان مي دارد كه براي رنگ آميزي هر نقشه اي كه بتواند آن را بر روي كاغذ رسم كرد، چهار رنگ كافي است اين مسأله براي اولين بار در نيمه اول قرن نوزدهم مطرح شد و تنها حدود بيست سال قبل 977 با استفاده از نظريه گراف قضيه هاي فراوان و 1200 ساعت از وقت يكي از سريعترين

كامپيوترهاي زمان توسط دو رياضيدان به نامهاي كنت اپل و ولگانگ هيكن در دانشگاه ايلي نويز حل شد چگونه قضيه چهار رنگ به صورت قضيه اي در نظريه گراف مطرح مي گردد؟ اگر به جاي هر يك از نواحي نقشه، يك رأس در نظر بگيريم و سپس فقط رأسهاي مربوط به نواحي هم مرز زا به يكديگر وصل كنيم نقشه مورد نظر تبديل به يك گراف مي شودگراف حاصل با نقشه مورد نظر متناظر است. اپل و هيكن با استفاده از يك كامپيوتر سريع به بررسي تعداد زيادي از حالتهاي ممكن كه پيش از آن از طريق تحليل رياضي نشان داده شده بود كه بررسي آنها براي اثبات قضيه كفايت مي كند پرداختند و به اين ترتيب قضيه را ثابت كردند

بنابر اين مسأله اي كه بيش از نيم قرن در مقابل حمله تعدادي از برگترين رياضيدانهاي زمان مقاومت كرده بود، در برابر يك تحليل كامپيوتري كه بر پايه پيشرفتهاي رياضي نظريه گراف بنا شده بوداز پاي در امد.مي دانيم كه عدد كروماتيك (رنگي )يك گراف عبارت است از مينيمم (Minimom ) تعداد رنگي كه بتوان رئوس گراف را رنگ زد، طوري كه دو رأس همجوار داراي رنگهاي يكسان نباشند. بنابر اين عدد 4 عدد رنگي گرافي است كه متناظر با نقشهاي است كه براي نثال 48 ايالت دارد كه به وسيله عمليات جبري محاسبه مي شود.

يكي از مسائل مهم و عمده در نظريه گراف و مسائلي كه از مدل سازي رياضي سيستمهاي فيزيكي اقتصادي، اجتماعي، زيستي و... پديد مي آيند پيدا كردن عدد رنگي يك گراف مي باشد اين موضوع براي گرا فهاي با تعداد اضلاع و رئوس متناهي پايين ( براي نثال با تعداد رئوس 4و5و…)به سادگي براي انواع گرا فها محاسبه مي‌شود ولي وقتي تعداد رئوس يا اضلاع بيشتر و يامتناهي باشداز مسائل پيشرفته و پيچيده اين نظريه مي باشد.
يك روش جالب در اين مورد كه از مفاهيم مربوط به نظريه حلقه ها استفاده كرده و ارتباطي بين نظريه گراف و نظريه حلقه ها در جبر ايجاد كرده است مبتني بر مقاله اي است با عنوان» رنگ كردنن حلقه هاي جابجايي« توسط استوان بك (Istvan Bek ) مي باشد كه موضوع پايان‌نامه تحصيلي در دوره كارشناسي ارشد استاد ارجممند دكترمحمد‌جهانشاهي نيز بوده است. در اين روش با استفاده از مفاهيم نظريه حلقه ها از قبيل ايده آلها و عناصرپوچ توان در يك حلقه، عددرنگي از گرا فهاي نامتناهي را كه داراي ساختار حلقه هستند پيدا شده است.
مسائلي ازنظريه گراف: نظريه گراف شاخه اي از رياضيات گسسته است ك براي حل و فرموله كردن بسياري از مسائل اجتماعي از قبيل حمل ونقل، ترا فيك در شهرها، آلودگي، سرويسهاي شهري ژنتيكي، مسائل پليسي و مسائل مهندسي از قبيل انرژي و مدارهاي الكتريكي، مهندسي شيمي و…با كار مي رود نمي توان ادعا كرد كه نظريه گراف به تنهايي قادر به حل اين مسائل است و يا بدون نظري گراف حل اين مسا ئل غيرممكن است بلكه اين نظريه وسيله اي براي فرموله كردن اين مسائل است.
اغلب فرموله كردن دقيق مسأله به ما مشان مي دهد كه چرا مسأله دشوار است؟و براي حل آن چگونه بايد داده ها ي مسأله ر براي بازكردن موجود در مسأله، تنظيم و سازماندهي كرد بنابراين گاهي وقتها نظريه گراف مسأله را حل مي كند و يا دست كم به ما اين بصيرت را مي دهد كه چگونه از امكانات موجود براي رسيدن به هدف خاصي استفاده كنيم.
1- اگر تعداد روشهاي مختلف رنگ كردن رئوس گراف G را با رنگ مختلف نشان دهد طوري كه در هر روش هيچ دو رأس همجوار داراي رنگ يكسان نباشد در مورد هر يك از گرافها ي زير عبارتي تحليلي براي بيان بر حسب K پيدا كنيد.

حل: در مورد (الف) ملاحظه مي كنيم كه اگر نقطه مياني به K طريق رنگ شود آن گاه نقطه هاي انتهايي به طريق رنگ خواهند شد لذا براي عبارت است از:
در مورد (ب) ملاحظه مي كنيم كه شبيه حالت (الف)، مي تواند به صورت
و بالاخره در مورد (ج) اگر يكي از رئوس به K طريق رنگ شود رأس ديگر به طريق و رأس سوم به طريق رنگ خواهد شدلذا برابر است با :
همين طور براي چنين گرافي باn رأس داريم:

ملاحظه مي كنيم كه در مورد گرا فها ي(الف)و(ب)حداقل مقدارk برابر 2و در مورد گراف (ج) حداقل مقدار k برابر 3 مي باشد. كمترين مقدار ممكن k را با شرايط فوق عدد رنگي گرافG مي ناميم و با(G)X نشان مي دهيم.
2- مي خواهيم با هفت دبير دبيرستاني پنج كميتة آموزش، پژوهش، ورزش، هنرو كتابخانه چنان تشكيل دهيم كه برخي از دبيران بتوانند در بيش از يك كميته عضويت داشته باشند اگر هر كميته موظف باشد كه جلسه اي يك ساعته با حضور تمام اعضاي خودتشكيل دهد .زمان لازم براي اين كه تمام كميته ها بتوانند وظايف خود را انجام دهند چقدر بايد باشد؟

حل: فرض كنيم دبيران با a وكميته ها با نشان داده شوند همچنين اعضاي كميته ها به صورت زير مشخص شده باشند.
عضوكميته هستند .
عضو كميته هستند.
عضو كميته هستند.
عضو كميته هستند.
عضو كميته هستند.
اگر به هر كميته يك نقطه نسبت دهيم و دو نقطه را با خطي به هم وصل كنيم ، هرگاه يكدبر بخواهد در بيش از يك كميته عضويت داشته باشد، آنگاه گراف مربوط به اين وضعيت مي تواند به صورت زير باشد.