کاربرد نظریه گراف
از گرافها برای حل مسایل زیادی در ریاضیات و علوم کامپیوتر استفاده
میشود. ساختارهای زیادی را میتوان به کمک گرافها به نمایش در آورد. برای
مثال برای نمایش چگونگی رابطه وب سایت‌ها به یکدیگر میتوان از گراف جهت
دار استفاده کرد. به این صورت که هر وب سایت را به یک راس در گراف تبدیل
می‌کنیم و در صورتیکه در این وب سایت لینکی به وب سایت دیگری بود، یک یال
جهت دار از این راس به راسی که وب سایت دیگر را نمایش می‌دهد وصل می‌کنیم.
از گرافها همچنین در شبکه‌ها، طراحی مدارهای الکتریکی، اصلاح هندسی
خیابان‌ها برای حل مشکل ترافیک، و…. استفاده میشود. مهم‌ترین کاربرد
گراف مدل‌سازی پدیده‌های گوناگون و بررسی بر روی آنهاست. با گراف میتوان
به راحتی یک نقشه بسیار بزرگ یا شبکه‌ای عظیم را در درون یک ماتریس به نام
ماتریس وقوع گراف ذخیره کرد و یا الگوریتمهای مناسب مانند الگوریتم دایسترا
یا الگوریتم کروسکال و … را بر روی آن اعمال نمود. در این جا به بررسی
گراف‌هایی می‌پردازد که میتوان آنها را به نحوی روی صفحه کشید که یال‌ها
جز در محل راس‌ها یکدیگر را قطع نکنند. این نوع گراف در ساخت جاده‌ها و حل
مساله کلاسیک و قدیمی سه خانه و سه چاه آب به کار می‌رود.
کاربرد گراف بازه‌ها از گرافها برای حل مسایل زیادی در ریاضیات و علوم
کامپیوتر استفاده میشود. ساختارهای زیادی را میتوان به کمک گرافها به
نمایش در آورد.
درخت و ماتریس درخت در رشته‌های مختلفی مانند شیمی مهندسی برق و علم
محاسبه کاربرد دارد . کیرشهف در سال ۱۸۴۷ میلادی هنگام حل دستگاههای
معادلات خطی مربوط به شبکه‌های الکتریکی درختها را کشف و نظریه درختها را
بارور کرد. کیلی در سال ۱۸۵۷ میلادی درختها را در ارتباط با شمارش
ایزومرهای مختلف هیدروکربنها کشف کرد وقتی مثلا میگوییم در ایزومر مختلف
c4h۱۰ وجود دارد منظورمان این است که دو درخت متفاوت با ۱۴ راس وجود دارند
که درجه ۴ راس از این ۱۴ راس جهار و درجه هر یک از ۱۰ راس باقیمانده یک
است. اگر هزینه کشیدن مثلا راه آهن بین هر دو شهر ازp شهر مفروض مشخص باشد
ارزانترین شبکه ای که این p شهر را به هم وصل می‌کند با مفهوم یک درخت از
مرتبه p ارتباط نزدیک دارد. به جای مساله مربوط به راه آهن میتوان وضعیت
مربوط به شبکه‌های برق رسانی و لوله کشی نفت و لوکشی گاز و ایجاد کانالهای
آبرسانی را در نظر گرفت . برای تعیین یک شبکه با نازلترین هزینه از قاعده
ای به نام الگوریتم صرفه جویی استفاده میشود که کاربردهای فراوان دارد. از
گرافها می توان به عنوان کدهای کمکی نام برد که به DVB Playerها در بالا
بردن قابلیت‌های آنها کمک میکنند. گرافها دارایی مزایای مختلفی هستند که
شفاف تر کردن و واضحتر کردن تصویر و کاهش مصرف CPU به عنوان یکی از
اصلی‌ترین مزایای آنها بشمار می رود.
کاربردهای گراف
| مقدمه | !مقدمه | ||
| بسیاری از وضعیتهای دنیای واقعی را میتوان به راحتی به وسیله نموداری متشکل از مجموعه‌ای از نقاط و خطوطی که زوجهای معینی از این نقاط را به هم وصل میکنند، توصیف کرد. مثلا نقاط می‌توانند معرف افراد باشند و خطوط واصل بین زوجها می‌توانند معرف دستها باشند یا هر چیز دیگر که در اطراف خود می‌بینیم. مثل اینکه نقاط معرف اهداف ما و خطوط واصل می‌تواند راههای رسیدن به اهداف باشند. توجه کنید در چنین نمودارهایی آنچه بیشتر مورد توجه ما قرار می‌گیرد این است که آیا بین دو نقطه مفروض یک خط وصل شده است یا خیر. شیوه وصل مهم نیست. تجرید ریاضی وضعیتهایی از این نوع به پیدایش گراف منجر شده است. این نمودارها دارای کاربردهای بسیار وسیعی در علم کامپیوتر و انواع مهندسی ، ((رسم نمودارها در فیزیک|علوم پایه)) به خصوص ((ژنتیک)) می‌باشند. در واقع اهمیت و قابل لمس بودن این بخش از ریاضیات غیر قابل انکار است. |
بسیاری از وضعیتهای دنیای واقعی را میتوان به راحتی به وسیله نموداری متشکل از مجموعه‌ای از نقاط و خطوطی که زوجهای معینی از این نقاط را به هم وصل میکنند، توصیف کرد. مثلا نقاط می‌توانند معرف افراد باشند و خطوط واصل بین زوجها می‌توانند معرف دستها باشند یا هر چیز دیگر که در اطراف خود می‌بینیم. مثل اینکه نقاط معرف اهداف ما و خطوط واصل می‌تواند راههای رسیدن به اهداف باشند. توجه کنید در چنین نمودارهایی آنچه بیشتر مورد توجه ما قرار می‌گیرد این است که آیا بین دو نقطه مفروض یک خط وصل شده است یا خیر. شیوه وصل مهم نیست. تجرید ریاضی وضعیتهایی از این نوع به پیدایش گراف منجر شده است. این نمودارها دارای کاربردهای بسیار وسیعی در علم کامپیوتر و انواع مهندسی ، ((رسم نمودارها در فیزیک|علوم پایه)) به خصوص ((ژنتیک)) می‌باشند. در واقع اهمیت و قابل لمس بودن این بخش از ریاضیات غیر قابل انکار است. |
||
| !مسئله کوتاهترین مسیر | !مسئله کوتاهترین مسیر | ||
| فرض کنید به هر یال e ی گراف G عددی نسبت داده شده باشد، در این صورت عدد نسبت داده شده وزن هر سال و چنین گرافی را ~~green:گراف وزن دار~~ می‌نامیم. این اعداد تعبیرهای مختلفی در کاربردهای متفاوت می‌توانند داشته باشند، مثلا می‌تواند مقدار هزینه سفر از نقطه‌ای به نقطه دیگر یا معرفی مخارج ساختن یا نگهداری خطهای ارتباطی مختلف یا حتی بیانگر شدت دوستی بین دو فرد باشد. به عنوان مثال شبکه راه آهنی را تصور کنید شهرهای مختلف را به هم وصل می‌کند، هدف ما پیدا کردن مسیری با Min وزنی است که دو رأس را به هم وصل می کند که در اینجا وزنها معرف فاصله‌ها می‌باشند. ((الگوریتم|الگوریتمی)) که به حل این مسئله می‌پردازد اولین بار توسط ((دانشمندان ریاضی|دیکسترا)) (1959) و بطور مستقل ((دانشمندان ریاضی|وایتینگ)) و ((دانشمندان ریاضی|هیلیه)) (1960) کشف کردند. این الگوریتم نه تنها کوتاهترین مسیر {TEX()} {(u_0 , v_0)} {TEX} را می‌یابد بلکه کوتاهترین مسیر از {TEX()} {u_0} {TEX} به همه رأسهای گرا ف G را نیز پیدا می‌کند. |
فرض کنید به هر یال e ی گراف G عددی نسبت داده شده باشد، در این صورت عدد نسبت داده شده وزن هر سال و چنین گرافی را ~~green:گراف وزن دار~~ می‌نامیم. این اعداد تعبیرهای مختلفی در کاربردهای متفاوت می‌توانند داشته باشند، مثلا می‌تواند مقدار هزینه سفر از نقطه‌ای به نقطه دیگر یا معرفی مخارج ساختن یا نگهداری خطهای ارتباطی مختلف یا حتی بیانگر شدت دوستی بین دو فرد باشد. به عنوان مثال شبکه راه آهنی را تصور کنید شهرهای مختلف را به هم وصل می‌کند، هدف ما پیدا کردن مسیری با Min وزنی است که دو رأس را به هم وصل می کند که در اینجا وزنها معرف فاصله‌ها می‌باشند. ((الگوریتم|الگوریتمی)) که به حل این مسئله می‌پردازد اولین بار توسط ((دانشمندان ریاضی|دیکسترا)) (1959) و بطور مستقل ((دانشمندان ریاضی|وایتینگ)) و ((دانشمندان ریاضی|هیلیه)) (1960) کشف کردند. این الگوریتم نه تنها کوتاهترین مسیر {TEX()} {(u_0 , v_0)} {TEX} را می‌یابد بلکه کوتاهترین مسیر از {TEX()} {u_0} {TEX} به همه رأسهای گرا ف G را نیز پیدا می‌کند. |
||
| !مسئله پستچی چینی | !مسئله پستچی چینی | ||
| یک پستچی در راستای شغلش ، نامه‌ها را از پستخانه تحویل می‌گیرد. آنها را به صاحبان نامه تحویل می‌دهد و سپس یه پستخانه بر می‌گردد. البته ، او باید در ناحیه‌اش هر خیابان را حداقل یک بار بپیماید. با توجه به این شرط ، او مایل است مسیرش را به طریقی انتخاب کند که کمترین راه ممکن را طی کند. این مسئله به مسئله ~~green:پستچی چینی~~ معروف است. زیرا اولین بار ((دانشمندان ریاضی|کوان ، ریاضیدان چینی)) (1962) آن را بررسی کرد. برای حل این مسئله بدیهی است که مسئله به یافتن مسیری با Min وزن در یک گراف همبند وزن دار با وزنهای نامنفی شباهت دارد. به این ترتیب که اگر گراف G را یک __گراف اویلری__ در نظر بگیریم هر مسیری یک مسیر اپتیمال است، زیرا یک مسیر اویلری ، مسیری است که هر یال دقیقا یکبار طی میشود. مسئله پستچی به راحتی در این حالت حل میشود. |
یک پستچی در راستای شغلش ، نامه‌ها را از پستخانه تحویل می‌گیرد. آنها را به صاحبان نامه تحویل می‌دهد و سپس یه پستخانه بر می‌گردد. البته ، او باید در ناحیه‌اش هر خیابان را حداقل یک بار بپیماید. با توجه به این شرط ، او مایل است مسیرش را به طریقی انتخاب کند که کمترین راه ممکن را طی کند. این مسئله به مسئله ~~green:پستچی چینی~~ معروف است. زیرا اولین بار ((دانشمندان ریاضی|کوان ، ریاضیدان چینی)) (1962) آن را بررسی کرد. برای حل این مسئله بدیهی است که مسئله به یافتن مسیری با Min وزن در یک گراف همبند وزن دار با وزنهای نامنفی شباهت دارد. به این ترتیب که اگر گراف G را یک __گراف اویلری__ در نظر بگیریم هر مسیری یک مسیر اپتیمال است، زیرا یک مسیر اویلری ، مسیری است که هر یال دقیقا یکبار طی میشود. مسئله پستچی به راحتی در این حالت حل میشود. |
||
| !قضیه شور | !قضیه شور | ||
| – | فرض کنید {TEX()} {(s_1,s_2,s_3,…,s_n)} {TEX} افرازی از مجموعه اعداد صحیح {TEX()} {(1,r,…,rn)} {TEX} باشد در این صورت ، برای iیی ، {TEX()} {S_i} {TEX} ، شامل سه عدد صحیح x ، y و z است که در معادله {TEX()} {x+y=z} {TEX} صدق می‌کند. برای اثبات این قضیه میتوان گراف کاملی را در نظر گرفت که مجموعه رأسی آن {TEX()} {(1,r,…,r_n)} {TEX} است، یالهای این گراف را به رنگهای 1 ، 2 ، … ، n با این قاعده رنگ کنید که به یال {TEX()} {u_v} {TEX} رنگ j تخصیص یابد، اگر و تنها اگر {TEX()} {|u-v| ε Sj} {TEX} در این صورت یک مثلث تک رنگ وجود دارد، یعنی به رأسی a ، b و c وجود دارند به طوری که ab ، bc و ca دارای یک رنگ ، مثلا i هستند. فرض کنید بدون اینکه به کلیت لطمه‌ای وارد شود، {TEX()} {ci و x+y=z. بدین ترتیب توانستیم یکی دیگر از کاربردهای گراف را بیان کنیم. |
+ | فرض کنید {TEX()} {(s_1,s_2,s_3,…,s_n)} {TEX} افرازی از مجموعه اعداد صحیح {TEX()} {(1,r,…,rn)} {TEX} باشد در این صورت ، برای iیی ، {TEX()} {S_i} {TEX} ، شامل سه عدد صحیح x ، y و z است که در معادله {TEX()} {x+y=z} {TEX} صدق می‌کند. برای اثبات این قضیه میتوان گراف کاملی را در نظر گرفت که مجموعه رأسی آن {TEX()} {(1,r,…,r_n)} {TEX} است، یالهای این گراف را به رنگهای 1 ، 2 ، … ، n با این قاعده رنگ کنید که به یال {TEX()} {u_v} {TEX} رنگ j تخصیص یابد، اگر و تنها اگر u-v| ε Sj| در این صورت یک مثلث تک رنگ وجود دارد، یعنی به رأسی a ، b و c وجود دارند بطوری که ab ، bc و ca دارای یک رنگ ، مثلا i هستند. فرض کنید بدون اینکه به کلیت لطمه‌ای وارد شود، {TEX()} {ci و x+y=z. بدین ترتیب توانستیم یکی دیگر از کاربردهای گراف را بیان کنیم. |
| !مسئله جدول زمانی | !مسئله جدول زمانی | ||
| – | در یک مدرسه ، m معلم {TEX()} {X_m , … , X_2 , X_1} {TEX} و n کلاس {TEX()} {Y_n,…,Y_2,Y_1} {TEX} وجود دارند. اگر بدانیم از معلم {TEX()} {X_i} {TEX} خواسته شده است که در کلاس {TEX()} {Y_j} {TEX} برای دوره‌های {TEX()} {P_{ij}} {TEX} تدریس کند، جدول زمانی کاملی را با Min تعداد دوره‌های ممکن برنامه ریزی کنید. مسئله فوق به مسئله جدول زمانی مشهور است و میتوان آن را با استفاده از نظریه رنگ آمیزی یالی توسط گراف دو بخش G با بخشهای (X,Y) حل کرد که در آن {TEX()} {X={TEX()} {X_m , … , X_2 , X_1} {TEX}} {TEX} و {TEX()} {Y={TEX()} {Y_n,…,Y_2,Y_1} {TEX}} {TEX} و رأسهای {TEX()} {y_i , x_i} {TEX} به وسیله یالهای {TEX()} {P_{ij}} {TEX} به هم متصل می‌شوند. اکنون در هر دوره ، یک معلم حداکثر می‌تواند در یک کلاس تدریس کنید و تدریس در هر کلاس به وسیله حداکثر یک معلم می‌تواند انجام شود. لذا برنامه ریزی آموزشی برای یک دوره متناظر با جور سازی در گراف است و برعکس هر جورسازی ، متناظر با تخصیص ممکن از معلمان به کلاسها برای یک دوره است. بنابراین مسئله ما یافتن افراز یالهای G به کمترین جور سازیهای ممکن. که آن ، رنگ آمیزی مناسب یالهای G با کمترین رنگ ممکن است. در مطالب فوق به |
+ | در یک مدرسه ، m معلم {TEX()} {X_m , … , X_2 , X_1} {TEX} و n کلاس {TEX()} {Y_n,…,Y_2,Y_1} {TEX} وجود دارند. اگر بدانیم از معلم {TEX()} {X_i} {TEX} خواسته شده است که در کلاس {TEX()} {Y_j} {TEX} برای دوره‌های {TEX()} {P_{ij}} {TEX} تدریس کند، جدول زمانی کاملی را با Min تعداد دوره‌های ممکن برنامه ریزی کنید. مسئله فوق به مسئله جدول زمانی مشهور است و میتوان آن را با استفاده از نظریه رنگ آمیزی یالی توسط گراف دو بخش G با بخشهای (X,Y) حل کرد که در آن {TEX()} {X={TEX()} {X_m , … , X_2 , X_1} {TEX}} {TEX} و {TEX()} {Y={TEX()} {Y_n,…,Y_2,Y_1} {TEX}} {TEX} و رأسهای {TEX()} {y_i , x_i} {TEX} به وسیله یالهای {TEX()} {P_{ij}} {TEX} به هم متصل می‌شوند. اکنون در هر دوره ، یک معلم حداکثر می‌تواند در یک کلاس تدریس کنید و تدریس در هر کلاس به وسیله حداکثر یک معلم می‌تواند انجام شود. لذا برنامه ریزی آموزشی برای یک دوره متناظر با جور سازی در گراف است و برعکس هر جورسازی ، متناظر با تخصیص ممکن از معلمان به کلاسها برای یک دوره است. بنابراین مسئله ما یافتن افراز یالهای G به کمترین جور سازیهای ممکن. که آن ، رنگ آمیزی مناسب یالهای G با کمترین رنگ ممکن است. /> />در مطالب فوق به تعدادی از کاربردهای گراف در بخشهای مختلف اشاره شد البته شایان ذکر است که گراف دارای کاربردهای متنوع دیگری نیز هست. زیباترین و جالب ترین کاربرد گراف در ((ژنتیک|علم ژنتیک)) است که توسط گراف به نتایج حیرت آوری می‌رسیم. |
