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

 

مقدمه

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

 

 

 

مسئله کوتاهترین مسیر

فرض کنیدبه هر یال e ی گراف G عددی نسبت داده شده باشد، در این صورت عدد نسبت داده شده وزنهر سال و چنین گرافی راگراف وزن دارمی‌نامیم. این اعداد تعبیرهای مختلفی در کاربردهای متفاوت می‌توانند داشته باشند، مثلامی‌تواند مقدار هزینه سفر از نقطه‌ای به نقطه دیگر یا معرفی مخارج ساختن یا نگهداریخطهای ارتباطی مختلف یا حتی بیانگر شدت دوستی بین دو فرد باشد. به عنوان مثال شبکهراه آهنی را تصور کنید شهرهای مختلف را به هم وصل می‌کند، هدف ما پیدا کردن مسیریبا Min وزنی است که دو رأس را به هم وصل می کند که در اینجا وزنها معرف فاصله‌هامی‌باشند. الگوریتمی که به حل این مسئلهمی‌پردازد اولین بار توسطدیکسترا (1959) و بطور مستقلوایتینگ وهیلیه (1960) کشف کردند. اینالگوریتم نه تنها کوتاهترین مسیررا می‌یابد بلکه کوتاهترین مسیر ازبه همه رأسهای گرا ف G را نیز پیدا می‌کند.

مسئله پستچی چینی

 

یک پستچی در راستایشغلش ، نامه‌ها را از پستخانه تحویل می‌گیرد. آنها را به صاحبان نامه تحویل می‌دهدو سپس یه پستخانه بر می‌گردد. البته ، او باید در ناحیه‌اش هر خیابان را حداقل یکبار بپیماید. با توجه به این شرط ، او مایل است مسیرش را به طریقی انتخاب کند کهکمترین راه ممکن را طی کند. این مسئله به مسئلهپستچیچینیمعروف است. زیرا اولین بارکوان ، ریاضیدانچینی (1962) آن را بررسی کرد. برای حل این مسئله بدیهی است که مسئله بهیافتن مسیری با Min وزن در یک گراف همبند وزن دار با وزنهای نامنفی شباهت دارد. بهاین ترتیب که اگر گراف G را یک گراف اویلری در نظر بگیریم هر مسیری یک مسیر اپتیمالاست، زیرا یک مسیر اویلری ، مسیری است که هر یال دقیقا یکبار طی می‌شود. مسئلهپستچی به راحتی در این حالت حل می‌شود.

قضیه شور

فرض کنیدافرازی از مجموعه اعداد صحیحباشد در این صورت ، برای iیی ،، شامل سه عدد صحیح x ، y و z است که در معادلهصدق می‌کند.

برای اثبات این قضیه می‌توان گراف کاملی را در نظر گرفت که مجموعه رأسیآناست، یالهای این گراف را به رنگهای 1 ، 2 ، ... ، n با این قاعده رنگ کنید که بهیالرنگ j تخصیص یابد، اگر و تنها اگر u-v| ε S_j| در این صورت یک مثلث تکرنگ وجود دارد، یعنی به رأسی a ، b و c وجود دارند بطوری که ab ، bc و ca دارای یکرنگ ، مثلا i هستند. فرض کنید بدون اینکه به کلیت لطمه‌ای وارد شود،و بنویسید x=a-b ، y=b-c و z=a-c در این صورت x,y,z ε S_i و 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 situspertinentis (راه حل مسئله‌ای در رابطه با هندسه موقعیت) اثباتش را شرح داد.

بعدها در سال ۱۸۷۳ کارل هیرهولتزر کار او را تکمیل کرد و در سال ۱۹۳۵ جیمز نیومن مقاله تکمیلی را نوشت.

این تصویر نام هفت پل به آلمانی و معنی آن‌ها به فارسی را نشان می‌دهد.

1-2-2. پل ها

از هفت پل زمان اویلر، دوتا از پل‌ها در جریان جنگ جهانی دوم به کلی نابود شدند. یکی دیگر از آن‌ها در سال ۱۹۳۵ توسط آلمانی‌ها بازسازی شد. دوتای دیگر نیز اکنون تبدیل به اتوبان شده‌است و فقط دوتا از پل‌ها متعلق به زمان اویلر است. پنج پل باقیمانده در کالینینگراد امروزی دارای مسیری است که از یک نقطه شروع می‌شود و از تمامی پل‌ها یکبار می‌گذرد و به نقطه‌ای دیگر ختم می‌شود.

1-3-2. اهميت مسئله در تاريخ رياضيات

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

2-2. راه حل اويلر

اویلر ابتدا نقشه شهر را با نقشه‌ای که فقط خشکی‌ها، رود و پل‌ها را نشان می‌داد، جایگزین کرد. سپس هر خشکی را با یک نقطه نشان داد که رأس نامیده می‌شود و هر پل را نیز با یک خط نشان داد که یال نامیده می‌شود. این ساختار ریاضی را گراف می‌نامند.

→

 

اویلر ثابت کرد برای آنکه مسیری وجود داشته باشد که از یک رأس شروع شود و از تمامی یال‌ها یکبار بگذرد و به همان رأس بازگردد، باید گراف هم‌بند بوده و هر یک از رأس‌های آن نیز از درجه زوج باشد. چنین مسیری، دور اویلری و چنین گرافی، گراف اویلری نامیده می‌شود.

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

چون در مسئله هفت پل کونیگسبرگ چهار رأس از درجه فرد داریم پس نه دور اویلری و نه مسیر اویلری وجود دارد. اویلر ثابت نکرد که هم‌بند بودن و زوج بودن رئوس شرط کافی برای اویلری بودن گراف است. در سال ۱۸۷۳ تکمیل این اثبات منتشر شد. این تکمیل توسط کارل هیرهولتزر انجام شد که قبل از انتشار اثبات مرده بود و تنها دلیلی که اثبات منتشر شد این بود که او به همکارانش اثبات را گفته بود. نتیجه آن دو قضیه زیر بود:

• یک گراف دارای دور اویلری است اگر و تنها اگرهم‌بند بوده و رئوس آن از درجه زوج باشند.
• یک گراف دارای مسیر اویلری است (و نه دور اویلری) اگر و تنها اگرهم‌بند بوده و دقیقاٌ دو رأس از آن از درجه فرد باشند.

 

 

3-2. الگوريتم فلزي

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

 

1-3-2. شبه كد

 

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