منو
 صفحه های تصادفی
آشنایی با شیمی صنعتی
آزمونهای هوش
ابو محمد قاضی عبیدالله بن صاعد
زرد آلو «داروئی»
دیدار امام علی علیه السلام برای دوست و دشمن هنگام مرگ
مدیریت دانش
لامپ مهتابی
مصاحبت با جبرئیل و میکائیل
جمال‌الدین اسدآبادی
حاج میرزا آقاسی
 کاربر Online
328 کاربر online
تاریخچه ی: کاربردهای گراف

تفاوت با نگارش: 2

Lines: 1-17Lines: 1-24
-@#14: +V{maketoc}
^
@#14:
 !مقدمه !مقدمه
 بسیاری از وضعیتهای دنیای واقعی را می‌توان به راحتی به وسیله نموداری متشکل از مجموعه‌ای از نقاط و خطوطی که زوجهای معینی از این نقاط را به هم وصل می‌کنند، توصیف کرد. مثلا نقاط می‌توانند معرف افراد باشند و خطوط واصل بین زوجها می‌توانند معرف دستها باشند یا هر چیز دیگر که در اطراف خود می‌بینیم. مثل اینکه نقاط معرف اهداف ما و خطوط واصل می‌تواند راههای رسیدن به اهداف باشند. توجه کنید در چنین نمودارهایی آنچه بیشتر مورد توجه ما قرار می‌گیرد این است که آیا بین دو نقطه مفروض یک خط وصل شده است یا خیر. شیوه وصل مهم نیست. تجرید ریاضی وضعیتهایی از این نوع به پیدایش گراف منجر شده است. این نمودارها دارای کاربردهای بسیار وسیعی در علم کامپیوتر و انواع مهندسی ، ((رسم نمودارها در فیزیک|علوم پایه)) به خصوص ((ژنتیک)) می‌باشند. در واقع اهمیت و قابل لمس بودن این بخش از ریاضیات غیر قابل انکار است. بسیاری از وضعیتهای دنیای واقعی را می‌توان به راحتی به وسیله نموداری متشکل از مجموعه‌ای از نقاط و خطوطی که زوجهای معینی از این نقاط را به هم وصل می‌کنند، توصیف کرد. مثلا نقاط می‌توانند معرف افراد باشند و خطوط واصل بین زوجها می‌توانند معرف دستها باشند یا هر چیز دیگر که در اطراف خود می‌بینیم. مثل اینکه نقاط معرف اهداف ما و خطوط واصل می‌تواند راههای رسیدن به اهداف باشند. توجه کنید در چنین نمودارهایی آنچه بیشتر مورد توجه ما قرار می‌گیرد این است که آیا بین دو نقطه مفروض یک خط وصل شده است یا خیر. شیوه وصل مهم نیست. تجرید ریاضی وضعیتهایی از این نوع به پیدایش گراف منجر شده است. این نمودارها دارای کاربردهای بسیار وسیعی در علم کامپیوتر و انواع مهندسی ، ((رسم نمودارها در فیزیک|علوم پایه)) به خصوص ((ژنتیک)) می‌باشند. در واقع اهمیت و قابل لمس بودن این بخش از ریاضیات غیر قابل انکار است.
 !مسئله کوتاهترین مسیر !مسئله کوتاهترین مسیر
 فرض کنید به هر یال 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|\inS_j} {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 با کمترین رنگ ممکن است. /> />در مطالب فوق به تعدادی از کاربردهای گراف در بخشهای مختلف اشاره شد البته شایان ذکر است که گراف دارای کاربردهای متنوع دیگری نیز هست. زیباترین و جالب ترین کاربرد گراف در ((ژنتیک|علم ژنتیک)) است که توسط گراف به نتایج حیرت آوری می‌رسیم.
 !مباحث مرتبط با عنوان !مباحث مرتبط با عنوان
 *((انواع تابع)) *((انواع تابع))
 *((تابع)) *((تابع))
 *((رسم توابع)) *((رسم توابع))
 *((روش رسم نمودارها در فیزیک)) *((روش رسم نمودارها در فیزیک))
-*((مقاطع مخروطی))#@ +*((مقاطع مخروطی))#@^

تاریخ شماره نسخه کاربر توضیح اقدام
 یکشنبه 20 خرداد 1386 [14:10 ]   3   حسین خادم      جاری 
 یکشنبه 20 خرداد 1386 [13:55 ]   2   حسین خادم      v  c  d  s 
 چهارشنبه 23 اسفند 1385 [08:23 ]   1   آیدا سلیم نژاد      v  c  d  s 


ارسال توضیح جدید
الزامی
big grin confused جالب cry eek evil فریاد اخم خبر lol عصبانی mr green خنثی سوال razz redface rolleyes غمگین smile surprised twisted چشمک arrow



از پیوند [http://www.foo.com] یا [http://www.foo.com|شرح] برای پیوندها.
برچسب های HTML در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..