كاربرد گراف دررياضي گسسته

كاربرد گراف دررياضي گسسته

کاربردهای گراف ( Usages of Geraph )

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

مسئله کوتاهترین مسیر
فرض کنید به هر یال e ی گراف G عددی نسبت داده شده باشد، در این صورت عدد نسبت داده شده وزن هر سال و چنین گرافی را گراف وزن دار می‌نامیم. این اعداد تعبیرهای مختلفی در کاربردهای متفاوت می‌توانند داشته باشند، مثلا می‌تواند مقدار هزینه سفر از نقطه‌ای به نقطه دیگر یا معرفی مخارج ساختن یا نگهداری خطهای ارتباطی مختلف یا حتی بیانگر شدت دوستی بین دو فرد باشد. به عنوان مثال شبکه راه آهنی را تصور کنید شهرهای مختلف را به هم وصل می‌کند، هدف ما پیدا کردن مسیری با Min وزنی است که دو رأس را به هم وصل می کند که در اینجا وزنها معرف فاصله‌ها می‌باشند. الگوریتمی که به حل این مسئله می‌پردازد اولین بار توسط دیکسترا (1959) و بطور مستقل وایتینگ و هیلیه (1960) کشف کردند. این الگوریتم نه تنها کوتاهترین مسیر را می‌یابد بلکه کوتاهترین مسیر از به همه رأسهای گرا ف G را نیز پیدا می‌کند.
مسئله پستچی چینی
یک پستچی در راستای شغلش ، نامه‌ها را از پستخانه تحویل می‌گیرد. آنها را به صاحبان نامه تحویل می‌دهد و سپس یه پستخانه بر می‌گردد. البته ، او باید در ناحیه‌اش هر خیابان را حداقل یک بار بپیماید. با توجه به این شرط ، او مایل است مسیرش را به طریقی انتخاب کند که کمترین راه ممکن را طی کند. این مسئله به مسئله پستچی چینی معروف است. زیرا اولین بار کوان ، ریاضیدان چینی (1962) آن را بررسی کرد. برای حل این مسئله بدیهی است که مسئله به یافتن مسیری با Min وزن در یک گراف همبند وزن دار با وزنهای نامنفی شباهت دارد. به این ترتیب که اگر گراف G را یک گراف اویلری در نظر بگیریم هر مسیری یک مسیر اپتیمال است، زیرا یک مسیر اویلری ، مسیری است که هر یال دقیقا یکبار طی می‌شود. مسئله پستچی به راحتی در این حالت حل می‌شود.
قضیه شور
فرض کنید افرازی از مجموعه اعداد صحیح باشد در این صورت ، برای iیی ، ، شامل سه عدد صحیح x ، y و z است که در معادله صدق می‌کند.
برای اثبات این قضیه می‌توان گراف کاملی را در نظر گرفت که مجموعه رأسی آن است، یالهای این گراف را به رنگهای 1 ، 2 ، ... ، n با این قاعده رنگ کنید که به یال رنگ j تخصیص یابد، اگر و تنها اگر u-v| ε Sj| در این صورت یک مثلث تک رنگ وجود دارد، یعنی به رأسی a ، b و c وجود دارند بطوری که ab ، bc و ca دارای یک رنگ ، مثلا i هستند. فرض کنید بدون اینکه به کلیت لطمه‌ای وارد شود، و بنویسید x=a-b ، y=b-c و z=a-c در این صورت x,y,z ε Si و x+y=z. بدین ترتیب توانستیم یکی دیگر از کاربردهای گراف را بیان کنیم.
مسئله جدول زمانی
در یک مدرسه ، m معلم و n کلاس وجود دارند. اگر بدانیم از معلم خواسته شده است که در کلاس برای دوره‌های تدریس کند، جدول زمانی کاملی را با Min تعداد دوره‌های ممکن برنامه ریزی کنید. مسئله فوق به مسئله جدول زمانی مشهور است و می‌توان آن را با استفاده از نظریه رنگ آمیزی یالی توسط گراف دوبخش G با بخشهای (X,Y) حل کرد که در آن } و } و رأسهای به وسیله یالهای به هم متصل می‌شوند. اکنون در هر دوره ، یک معلم حداکثر می‌تواند در یک کلاس تدریس کنید و تدریس در هر کلاس به وسیله حداکثر یک معلم می‌تواند انجام شود. لذا برنامه ریزی آموزشی برای یک دوره متناظر با جور سازی در گراف است و برعکس هر جورسازی ، متناظر با تخصیص ممکن از معلمان به کلاسها برای یک دوره است. بنابراین مسئله ما یافتن افراز یالهای G به کمترین جور سازیهای ممکن. که آن ، رنگ آمیزی مناسب یالهای G با کمترین رنگ ممکن است.
در مطالب فوق به تعدادی از کاربردهای گراف در بخشهای مختلف اشاره شد البته شایان ذکر است که گراف دارای کاربردهای متنوع دیگری نیز هست. زیباترین و جالب ترین کاربرد گراف در علم ژنتیک است که توسط گراف به نتایج حیرت آوری می‌رسیم.

1-الگوريتم كروسكال
در نظریه گراف، الگوریتم کروسکال الگوریتمی برای یافتن یک زیرگراف فراگیر همبند با کمترین وزن در یک گراف وزن‌دار است (در یک گراف وزن دار، به هر یال وزنی نسبت داده شده‌است).
به عنوان مثال فرض کنید یک شبکه راه آهن که تعدادی شهر را به یکدیگر متصل می‌کند در دست احداث است می‌خواهیم با داشتن هزینه مربوط به احداث خط مستقیم بین شهرهای شبکه را طوری طراحی کنیم که مجموع هزینه‌های ساخت به کمترین مقدار خود برسد. با در نظر گرفتن هر شهر به عنوان یک راس از گراف وزن دار با وزن‌های مسئله به یافتن یک زیر گراف فراگیر همبند با کمترین وزن در یک گراف منجر می‌شود.
فرض کنید وزن‌ها نامنفی هستند بنابراین می‌توانیم تصور کنیم که زیر گراف فراگیر با کمترین وزن یک درخت فراگیر T از G است حال الگوریتم زیر را برای این کار ارائه می‌دهیم.
۱-یال پیوندی را طوری انتخاب کن که وزن آن کوچکترین مقدار ممکن باشد.
۲-اگر یال‌های انتخاب شده‌اند یال را از میان به گونه‌ای انتخاب کن که:
الف)زیرگراف با یال‌های بدون دور باشد.
ب)از میان یال‌های صادق در شرط (الف) وزن دارای کمترین مقدار ممکن باشد.
۳-در صورتی که مرحله ۲ دیگر قابل اجرا نیست توقف کن.
2-1. اثبات
ثابت می‌کنیم هردرخت فراگیر U با یال‌های که با الگوریتم کروسکال ساخته شود یک درخت بهینه‌است.
از طریق تناقض: به ازای هر درخت فراگیر T از G به غیر از U کوچکترین مقدار i را به طوری که در T نباشد با(f(t نمایش می‌دهیم. اکنون فرض کنید که U یک درخت بهینه نباشد و T را به عنوان درخت بهینه در نظر بگیرید که در آن(f(t دارای بزرگترین مقدار ممکن باشد. فرض کنید f(t)=k این بدان معنی است که هم در T و هم در U هستند. ولی در T نیست پس شامل یک دور یکتای C می‌باشد. فرض کنید یالی از C باشد که در T هست ولی در U نیست. پس یال برشی ازT+ نیست. بنابراین یک گراف همبند با v-۱ یال بوده در نتیجه درخت فراگیر دیگری برای G خواهد بود. روشن است که:
ولی در الگوریتم کروسکال به عنوان یالی با کمترین وزن طوری انتخاب شده‌است که زیرگراف G با یال‌های بدون دور باشد. چون زیرگراف G با یال‌های زیر گرافی از T است. بنابرین ان هم بدون دور است و نیتجه می‌گیریم که:
≥
پس
≤
پس هم یک درخت بهینه خواهد بود در صورتی که داریم:

که این با T انتخاب در تناقض است. بنابرین T=U و در نتیجه U یک درخت بهینه‌است.
1-    مسئله پل هاي كونيگسبرگ
مسئله پل‌های کونیگسبرگ یکی از مشهورترین مسائل در نظریه گراف است که در مکان و شرایط واقعی طرح شده‌است. در اوایل سده ۱۸ ساکنین کونیگسبرگ در پروسیا (در حال حاضر کالینینگراد در روسیه) در روزهای یکشنبه پیاده‌روی‌هایی طولانی در شهر داشتند. رود پرگل شهر را به چهار قسمت تقسیم می‌کرد که با هفت پل به هم مربوط بودند. ساکنین سعی می‌کردند مسیری بیابند که از نقطه‌ای در شهر شروع کنند و از تمامی پل‌ها فقط یکبار بگذرند و به نقطه شروع بازگردند.

1-2. تاريخچه
1-1-2. حل مسئله
در سال ۱۷۳۶ لئونارد اویلر، ریاضیدان سوئیسی ثابت کرد که چنین مسیری وجود ندارد. او که در آن زمان استاد دانشگاه سن پترزبورگ بود، در مقاله‌ای با عنوان Solutio problematis ad geometriam situs pertinentis (راه حل مسئله‌ای در رابطه با هندسه موقعیت) اثباتش را شرح داد.
بعدها در سال ۱۸۷۳ کارل هیرهولتزر کار او را تکمیل کرد و در سال ۱۹۳۵ جیمز نیومن مقاله تکمیلی را نوشت.

این تصویر نام هفت پل به آلمانی و معنی آن‌ها به فارسی را نشان می‌دهد.
1-2-2. پل ها
از هفت پل زمان اویلر، دوتا از پل‌ها در جریان جنگ جهانی دوم به کلی نابود شدند. یکی دیگر از آن‌ها در سال ۱۹۳۵ توسط آلمانی‌ها بازسازی شد. دوتای دیگر نیز اکنون تبدیل به اتوبان شده‌است و فقط دوتا از پل‌ها متعلق به زمان اویلر است. پنج پل باقیمانده در کالینینگراد امروزی دارای مسیری است که از یک نقطه شروع می‌شود و از تمامی پل‌ها یکبار می‌گذرد و به نقطه‌ای دیگر ختم می‌شود.
1-3-2. اهميت مسئله در تاريخ رياضيات
راه‌حل اویلر باعث شکل‌گیری بهتر شاخه جدیدی از ریاضیات به نام توپولوژی شد که پیشتر توسط لایبنیتز مطرح شده بود اما مهمتر از آن، راه‌حل اویلر در تاریخ ریاضیات به عنوان اولین قضیه در نظریه گراف شناخته شده‌است که امروزه شاخه‌ای بسیار کاربردی در ریاضیات محسوب می‌شود.
2-2. راه حل اويلر
اویلر ابتدا نقشه شهر را با نقشه‌ای که فقط خشکی‌ها، رود و پل‌ها را نشان می‌داد، جایگزین کرد. سپس هر خشکی را با یک نقطه نشان داد که رأس نامیده می‌شود و هر پل را نیز با یک خط نشان داد که یال نامیده می‌شود. این ساختار ریاضی را گراف می‌نامند.
→
اویلر ثابت کرد برای آنکه مسیری وجود داشته باشد که از یک رأس شروع شود و از تمامی یال‌ها یکبار بگذرد و به همان رأس بازگردد، باید گراف هم‌بند بوده و هر یک از رأس‌های آن نیز از درجه زوج باشد. چنین مسیری، دور اویلری و چنین گرافی، گراف اویلری نامیده می‌شود.
برای آنکه از یک رأس بگذریم، باید از یک یال به آن رأس وارد شویم و چون باید از هر یال یکبار عبور کنیم، باید از یال دیگری که از آن عبور نشده‌است از آن رأس خارج شویم. پس همواره رئوسی که از آنها عبور می‌کنیم از درجه زوج هستند زیرا در هر گذر درجه آن رأس به اضافه دو می‌شود. حال اگر نقطه شروع و پایان یکی باشد، تمام رئوس از درجه زوج خواهند بود و دور اویلری طی کرده‌ایم. اگر نقطه شروع و پایان یکی نباشد، فقط این دو رأس از درجه فرد و بقیه رئوس از درجه زوج خواهند بود. چنین مسیری را مسیر اویلری می‌نامند.
چون در مسئله هفت پل کونیگسبرگ چهار رأس از درجه فرد داریم پس نه دور اویلری و نه مسیر اویلری وجود دارد. اویلر ثابت نکرد که هم‌بند بودن و زوج بودن رئوس شرط کافی برای اویلری بودن گراف است. در سال ۱۸۷۳ تکمیل این اثبات منتشر شد. این تکمیل توسط کارل هیرهولتزر انجام شد که قبل از انتشار اثبات مرده بود و تنها دلیلی که اثبات منتشر شد این بود که او به همکارانش اثبات را گفته بود. نتیجه آن دو قضیه زیر بود:
•    یک گراف دارای دور اویلری است اگر و تنها اگرهم‌بند بوده و رئوس آن از درجه زوج باشند.
•    یک گراف دارای مسیر اویلری است (و نه دور اویلری) اگر و تنها اگرهم‌بند بوده و دقیقاٌ دو رأس از آن از درجه فرد باشند.

3-2. الگوريتم فلزي
برای تولید یک دور اویلری در گراف حاوی این دور می‌توان از این الگوریتم که در سال ۱۸۸۳ معرفی شد، استفاده کرد.

1-3-2. شبه كد
1 ConstructEulerCircuit(){ 2 circuitpos = 0 3 EulerCircuit(start) //The starting vertex 4 } 5 EulerCircuit(u){ 6 if (there is no adjacent vertex to u){ 7 circuit[circuitpos] = u 8 circuitpos++ 9 }else{ 10 for (each vertex v adjacent to u){ 11 DeleteEdge(u,v) 12 EulerCircuit(v) 13 } 14 circuit[circuitpos] = u 15 circuitpos++ 16 } 17

2-    الگوريتم هاي تصادفي
در شکل بالا نحوه ی عملکرد الگوریتم های تصادفی را می‌توانید مشاهده کنید در این مقاله با جزییات این نوع ادر این مقاله شما با الگوریتم های تصادفی و همچنین تحلیل تصادفی آشنا می شوید سپس میزان اطمینان آن(Reality) را بررسی می کنیم و همچنین انواع الگوریتم های تصادفی و تاریخچه ی آن ها را در این مقاله می خوانیم. در ضمن در انتها چند مثال از الگوریتم های تصادفی را بررسی می کنیم.
بطور خلاصه، تحلیل احتمالی ، استفاده از احتمال در تحلیل مسئله می‌باشد این موضوع معمولا موقعی به کار می‌رود که بدترین حالت الگوریتم(Worst case) دارای احتمال ناچیزی می‌باشد و می خواهیم کارایی برنامه را در حالت متوسط (Average case) بدست بیاوریم و این موضوع را می‌توان با تحلیل احتمالی به راحتی بدست آورد.
الگوریتم تصادفی به الگوریتمی گفته می‌شود که رفتارش نه تنها به ورودی اش بلکه همچنین با مقادیر تولید شده توسط یک مولد تصادفی تعیین می‌شود.بنابراین در این نوع الگوریتم فرض می کنیم که ماشینی که در آن الگوریتم خود را پیاده سازی می کنیم باید دارای تولید کننده ی اعداد تصادفی باشد.
الگوريتم تصادفي الگوریتمی است که در آن به ماشین تولید اعداد تصادفی دسترسی دارد و از آن در الگوریتم خود استفاده می‌کند. این الگوریتم نوعاً با هدف بالا بردن کارایی در حالت‌های معمول از یک ورودی دودویی کمکی برای رفتارهای خود استفاده می‌کند. کارایی الگوریتم با یک متغیر تصادفی که به بیت‌های تصادفی داده شده بستگی دارد، تغییر می‌یابد که (امیدوارانه) امید ریاضی خوبی را شامل می‌شود. احتمال وقوع بدترین حالت آنقدر کم است که می‌توان از آن صرفنظر کرد.

میزان نزدیکی به واقعیت در مورد الگوریتم های تصادفی
1-3. میزان Reality الگوریتم های تصادفی
در این قسمت می خواهیم در مورد مطلب بسیار مهم میزان اطمینان به این نوع الگوریتم صحبت کنیم. همان طور که در شکل مشاهده می نمایید با افزایش محور افقی می‌توانیم با احتمال نزدیک به 100 درصد نتیجه ی حاصل نزدیک به واقعیت می‌باشد. (برای اطلاعات بیشتر از نحوه ی بدست آوردن این صفحه می‌توانید به لینک آن مراجعه نمایید.)
2-3. يك مثال از الگوريتم تصادفي
به عنوان یک مثال واقعی ، Quick Sort یکی از مهمترین الگوریتم هایتصادفی می‌باشد که بدترین حالت خیلی کم اتفاق می افتد و با تحلیل احتمالی این موضوع را ثابت می کنیم و همچنین نوع Randomize Quick Sort که یک الگوریتم تصادفی می‌باشد و صرفا به ورودی آرایه ای مربوط نمی‌باشد بلکه به یک عدد تصادفی تولید شده نیز مربوط می‌باشد.
به عنوان یک مثال فرض کنید در آرایه ای که شامل اعداد 0 و1 می‌باشد بطوری که نصف آن ها 0 و نیمی دیگر 1 می‌باشند حال می خواهیم با جستجو کردن از ابتدای آرایه اولین عنصر با مقدار 1 را بیابیم در مسئله در بدترین حالت باید N/2 تا خانه را چک کنیم تا 1 را پیدا کنیم ولی این حالت بسیار خاص می‌باشد و در حالت متوسط مشاهده می کنیم تعداد حالت جستجو برای این موضوع بسیار کمتر از این مقدار است.
3-3. موارد استفاده از الگوريتم هاي تصادفي
1. الگوریتم‌های تصادفی بویژه در مواردی استفاده دارند که با یک دشمن یا مهاجم بد خواهی! مواجهیم که از روی عناد ورودی بدی را برای ما فراهم می‌کند(آنالیز رقابتی). به همین دلیل انتخاب تصادفی پایه رمزنگاری را تشکیل می‌دهد. این بدین معنی است که دشمن شما(!) نمی‌تواند با یک ورودی خاص بدترین حالت (Worst Case)شما را پدید بیاورد چون که به اعداد تصادفی تولید شده نیز مربوط می‌باشد.
2. از الگوریتم‌های تصادفی معمولا برای بررسی پدیده‌هایی مورد استفاده قرار می‌گیرند که در آنها تعداد زیاد باشد.برای مثال واپاشی یک هسته پرتوزا را در نظر می‌گیریم.برای بررسی این پدیده که چه زمانی یک اتم از آن واپاشی می‌کند ناچار به استفاده از احتمال هستیم.یعنی بهتر است بگوییم احتمال واپاشی این اتم چه قدر است.حالا اگر تعداد اتمها زیاد باشد، دیگر مسئله را از طریق تحلیلی نمی‌توان حل کرد.بلکه باید به روش‌های عددی روی آورد.در حقیقت الگوریتم‌های تصادفی، راهی برای حل عددی اینگونه مسائل هستند.
4-3. انواع الگوريتم هاي تصادفي
در مثال بالا الگوریتم تصادفی همیشه درست جواب می‌دهد تنها احتمال کوچکی وجود دارد که زمان زیادی برای رسیدن به پاسخ صرف کند. در بعضی مواقع ما از الگوریتم با اجازه دادن ایجاد احتمال کمی خطا انتظار سرعت بالاتر را داریم. الگوریتمهای از نوع اول را لاس وگاس (Las Vegas algorithms) و نوع اخیر را مونت کارلو (Monte Carlo algorithms) می‌نامند. مشاهده می‌کنیم که هر الگوریتم لاس وگاس با گرفتن جوابی احتمالاً نادرست در زمانی مشخص و محدود شده به الگوریتم مونت کارلو تبدیل می‌شود.
از الگوریتم‌های تصادفی معمولا برای بررسی پدیده‌هایی مورد استفاده قرار می‌گیرند که در آنها تعداد زیاد باشد.برای مثال واپاشی یک هسته پرتوزا را در نظر می‌گیریم.برای بررسی این پدیده که چه زمانی یک اتم از آن واپاشی می‌کند ناچار به استفاده از احتمال هستیم.یعنی بهتر است بگوییم احتمال واپاشی این اتم چه قدر است.حالا اگر تعداد اتمها زیاد باشد، دیگر مسئله را از طریق تحلیلی نمی‌توان حل کرد.بلکه باید به روش‌های عددی روی آورد.در حقیقت الگوریتم‌های تصادفی، راهی برای حل عددی اینگونه مسائل هستند.
در آزمایشگاه لوس آلاموس در آمریکا دانشمندانی که بر روی پروژه سری منهتن کار می‌کردند، برای بررسی سیستم‌هایی که درآنها تعداد ذرات بالااست، مجبور به ابداع روش و یا الگوریتمی شدند که بعدها نام «مونت کارلو» بر آن قرار دادند.این الگوریتم برای نمونه گیری آماری از سیستم‌هایی با تعداد فضای فاز بالا به کار می‌رود.همچنین از این الگوریتم برای حل معادلات دیفرانسیل و انتگرال گیری معین استفاده می‌شود. دوالگوریتم مشهور مونت کارلو عبارتند از:
1.    الگوریتم متروپلیس
2.    الگوریتم مونت کارلو جنبشی یا n-fold way
این الگوریتم‌ها بیشتر بر این مبنا کار می‌کنند که:ابتداء یک پیکر بندی از سیستم مورد بررسی انتخاب می‌شود.سپس راه‌های موجود برای اینکه سیستم به آنها گذار کند مشخص احتمال آنها محاسبه می‌شود.آنگاه با تولید یک عدد تصادفی احتمالات موجود مورد سنجش قرار می‌گیرند، و سیستم به یکی از حالات ممکن گذار می‌کند.دوباره قسمت دیگری از سیستم انتخاب شده و مراحل قبلی تکرار می‌شود.

3-    مسئله فروشنده دوره گرد
مسئله فروشنده دوره‌گرد (به انگلیسی: Travelling salesman problem ، به‌اختصار: TSP ) مسئله‌ای مشهور است که ابتدا در سده ۱۸ مسائل مربوط به آن توسط ویلیام همیلتون و توماس کرکمن مطرح شد و سپس در دهه ۱۹۳۰ شکل عمومی آن به وسیله ریاضیدانانی مثل کارل منگر از دانشگاه هاروارد و هاسلر ویتنی از دانشگاه پرینستون مورد مطالعه قرار گرفت.

شرح مسئله بدین شکل است:
تعدادی شهر داریم و هزینه رفتن مستقیم از یکی به دیگری را می‌دانیم. مطلوب است کم‌هزینه‌ترین مسیری که از یک شهر شروع شود و از تمامی شهرها دقیقاٌ یکبار عبور کند و به شهر شروع بازگردد.
تعداد کل راه‌حل‌ها برابر است با برای n>۲ که n تعداد شهرها است. در واقع این عدد برابر است با تعداد دورهای همیلتونی در یک گراف کامل با n رأس.
1-4. مسئله هاي مرتبط
•    مسئله معادل در نظریه گراف به این صورت است که یک گراف وزن‌دار کامل داریم که می‌خواهیم کم‌وزن‌ترین دور همیلتونی را پیدا کنیم.
•    مسئله تنگراه فروشنده دوره‌گرد (به انگلیسی: Bottleneck traveling salesman problem، به‌اختصار: bottleneck TSP ) مسئله‌ای بسیار کاربردی است که در یک گراف وزن‌دار کم‌وزن‌ترین دور همیلتونی را می‌خواهد که شامل سنگین‌ترین یال باشد.
•    تأمیم‌یافته مسئله فروشنده دوره‌گرد دارای ایالت‌هایی است که هر کدام حداقل یک شهر دارند و فروشنده باید از هر ایالت دقیقاٌ از یک شهر عبور کند. این مسئله به « مسئله سیاستمدار مسافر» نیز شهرت دارد.
2-4. الگوريتم ها
مسئله فروشنده دوره‌گرد جزء مسائل NP-hard است. راه‌های معمول مقابله با چنین مسائلی عبارتند از:
•    طراحی الگوریتم‌هایی برای پیدا کردن جواب‌های دقیق که استفاده از آنها فقط برای مسائل با اندازه کوچک صورت می‌گیرد.
•    استفاده از الگوریتم‌های مکاشفه‌ای که جواب‌هایی به‌دست می‌دهد که احتمالاٌ درست هستند.
•    پیدا کردن زیرمسئله‌هایی از مسئله یعنی تقسیم مسئله به مسئله‌های کوچکتر تا بشود از الگوریتم‌های مکاشفه‌ای بهتر و دقیق‌تری ارائه کرد.
3-4. الگوريتم هاي دقيق
سرراست ترین راه حل امتحان کردن تمامی جایگشت‌های ممکن برای پیدا کردن ارزان‌ترین مسیر است که چون تعداد جایگشت‌ها !n است، این راه حل غیرعملی می‌شود. با استفاده از برنامه‌نویسی پویا مسئله می‌تواند با مرتبه زمانی حل شود. راه‌های دیگر استفاده از الگوریتم‌های انشعاب و تحدید برای ۴۰ تا ۶۰ شهر، استفاده از برنامه‌نویسی خطی برای کوچکتر از ۲۰۰ شهر و استفاده از روش برش-صفحه برای اندازه‌های بزرگ است.
4-4. الگوريتم هاي مكاشفه اي
الگوریتم‌های تقریبی متنوعی وجود دارند که خیلی سریع جواب‌های درست را با احتمال بالا به‌دست می‌دهند که می‌توان آنها را به صورت زیر دسته‌بندی کرد:
•    مکاشفه‌ای سازنده
•    بهبود تکراری
o    مبادله دوبه‌دو
o    مکاشفه‌ای k-opt
o    مکاشفه‌ای V-opt
•    بهبود تصادفی
4-    تصوير نقشه هاي رنگي
يك نقشه رنگي بر اساس يكسري رنگها طراخي شده كه هر رنگ به يكي از عوارض نقشه تخصيص داده مي شود. ارزش دسته هاي تك رنگ درطيف رنگ نقشه هاي قابل تغيير خواهد بود و براي تغيير رنگ تصوير روي هر رنگ دو بار كليك مي كنيم با بكار بردن ديالوگ color palette رنگ مورد نظر را انتخاب كنيد.
•   Adjust : ديالوگ Adjust cotormap براي تنظيم درجه رنگها آبي، سبز وقرمز كه در نقشه به كاربرده مي شود، استفاده مي شود.
• Ramp : با انتخاب اين گزينه درجاتي از رنگ را بين دو رنگ انتخاب شده ايجاد مي كند. اگر سبز تيره اي براي گونه پايين تر وسفيد براي گونه بالاتر انتخاب شده باشد Ramp درجه روشن تر سبز را براي هر دسته تا رسيدن به رنگ سفيد انتخاب مي كند.
• Random : يك رنگي به صورت تصادفي انتخاب مي كند.
• Gray : يك طيف رنگي كه از سياه شروع شده و به طرف سفيد مي رود و سايه هاي خاكستري مابين اين دو طيف رنگ نشان مي دهد.
• Nominal : يك طيف از16 رنگ است كه درجات اين طيف از0 تا 15 مي باشد كه به صورت چرخشي نمايش داده مي شوند.(رنگ 16= رنگ0) (رنگ17= رنگ1وغيره) اين نوع طيف رنگي براي عوارضي مجزاغ همچون زمينها و يا خاكها به كار مي رود.
نمايش ارزشهاي بدون داده (No Data)
داده هايي كه هيچ گونه ارزشي به آنها نسبت داده نشده و يا اصلا" داراي ارزشي   نمي باشند.
تنظيم رنگ داده هاي بدون ارزش No Data   در جدول به اين صورت است كه محل هر سلول هنگامي كه اطلاعاتي داده نشده به مقدار No Data نسبت داده مي شود.
No Data به اين معنا نيست كه ارزش سلول صفر مي باشد داده بدون ارزش را
مي توان به صورت يك سمبل ساده و با يك رنگ نمايش داد ولي تصوير را ديگر نمي توان به راحتي درك وتفسير نمود؛ بنابراين براي نشانه گذاري داده هاي بدون ارزش سمبلي بدون رنگ يعني No Data را از (Color Palette) انتخاب نمود (مربع رنگي بايك * علامت گذاري مي شود.)

2-5. تنظيم گستردگي تصوير
اجزاي Definitionدر ديالوگThme properties براي تنظيم گستردگي نمايش به كار مي رود تعويض گستردگي نمايش امكان اينكه يك قسمت كوچكي از يك تصوير براي نمايش انتخاب كرده بنابراين زمان ترسيم افزايش مي يابد يا تصويري روي يك نقشه متمركز شده نيز مانند نقشه اسكله يك هواپيما يا محدوده از شهر كه مراكز شغلي.Extent Limit : ليست كركره اي Extent Limit براي تنظيم گستردگي تصويرمي باشد به صورت پيش فرض نقشه كه در پنجره نما نمايش داده شود داراي گستردگي به اداره پنجره نما برده است. از ليست كركره اي Extent Limit گزينه Specified را انتخاب كنيد تا مختصات چپ، راست، پايين و بالا را از گسترده مشخص تنظيم نماييد.

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

درخواست پایان نامه خود را از اینجا ثبت کنید

كاربرد گراف دررياضي گسسته

مطالب مشابه :

دانلود پایان نامه رنگ آمیزی گراف با الگوریتم ژنتیک

الگوریتم رنگ آمیزی آزمند

كاربرد گراف دررياضي گسسته

کاربردهای گراف

مقالات شبیه سازی شده رشته برق در متلب MATLAB

پروژه ها و مقالات شبیه سازی شده در متلب- پردازش سیگنال و هوش مصنوعی

نتایج داوری مقالات

الگوریتم کلونی مورچگان