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

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

    

          

مقدمه

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

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

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

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

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

قضیه شور

فرض کنید e8dfa3959844c66c555aa5f0c990fbd0.png افرازی از مجموعه اعداد صحیح fe502bf8051a393b8384f9514eb10c3d.png باشد در این صورت ، برای iیی ، 43193f0a46db7714c275ad5d313247eb.png ، شامل سه عدد صحیح x ، y و z است که در معادله d3e537762c1e931039722d9a0fa69f8d.png صدق می‌کند. برای اثبات این قضیه می‌توان گراف کاملی را در نظر گرفت که مجموعه رأسی آن 41a7a66020cdda0507bf891fe1ceaabc.png است، یالهای این گراف را به رنگهای 1 ، 2 ، ... ، n با این قاعده رنگ کنید که به یال c0c2518724e856003250eb62366ba33f.png رنگ j تخصیص یابد، اگر و تنها اگر u-v| ε Sj| در این صورت یک مثلث تک رنگ وجود دارد، یعنی به رأسی a ، b و c وجود دارند بطوری که ab ، bc و ca دارای یک رنگ ، مثلا i هستند. فرض کنید بدون اینکه به کلیت لطمه‌ای وارد شود، 8331c1034e81d3599d9748b48105837b.png و بنویسید x=a-b ، y=b-c و z=a-c در این صورت x,y,z ε Si و x+y=z. بدین ترتیب توانستیم یکی دیگر از کاربردهای گراف را بیان کنیم.

مسئله جدول زمانی

در یک مدرسه ، m معلم 2ff2d970a7c419d51849df1261a93f26.png و n کلاس 07bc248832670cf4716f2db104a9b893.png وجود دارند. اگر بدانیم از معلم be9e0c82b43d8710bffe88b20b3f0296.png خواسته شده است که در کلاس 4f8e9421c0ded83e8319912266400cba.png برای دوره‌های daf6337e1be7e1bff4134d822ad85ed5.png تدریس کند، جدول زمانی کاملی را با Min تعداد دوره‌های ممکن برنامه ریزی کنید. مسئله فوق به مسئله جدول زمانی مشهور است و می‌توان آن را با استفاده از نظریه رنگ آمیزی یالی توسط گراف دو بخش G با بخشهای (X,Y) حل کرد که در آن 7b9dfa0eeffd662c4d01801e5448d6a9.png} و 77f6790c14c7860b6ed2b55bfc7ebc84.png} و رأسهای 36a99f65a4dfd124ef053fee6996e3ff.png به وسیله یالهای daf6337e1be7e1bff4134d822ad85ed5.png به هم متصل می‌شوند. اکنون در هر دوره ، یک معلم حداکثر می‌تواند در یک کلاس تدریس کنید و تدریس در هر کلاس به وسیله حداکثر یک معلم می‌تواند انجام شود. لذا برنامه ریزی آموزشی برای یک دوره متناظر با جور سازی در گراف است و برعکس هر جورسازی ، متناظر با تخصیص ممکن از معلمان به کلاسها برای یک دوره است. بنابراین مسئله ما یافتن افراز یالهای G به کمترین جور سازیهای ممکن. که آن ، رنگ آمیزی مناسب یالهای G با کمترین رنگ ممکن است.

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

به نقل از :  http://daneshnameh.roshd.ir


مطالب مشابه :


کاربرد گراف

از گراف‌ها برای حل مسایل زیادی در ریاضیات و علوم کامپیوتر استفاده می‌شود. ساختارهای زیادی




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

از گراف‌ها برای حل مسایل زیادی در ریاضیات و علوم کامپیوتر استفاده می‌شود. ساختارهای زیادی




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

این نمودارها دارای کاربردهای بسیار وسیعی در علم کامپیوتر و ترین کاربرد گراف در




گراف

اندک زمانی است که واژه گراف در کامپیوتر است و علت آن نیز به خاطر قابلیت کاربرد آن در




کاربرد های کامپیوتر در مسائل مربوط به زهکشی

کاربرد های کامپیوتر در در روش های محاسبات دستی غالبا از جداول و گراف ها استفاده به عمل




رئوس مطالب مورد آزمون کنکور کارشناسی ارشد کامپیوتر

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




کاربرد فناوری نانو در الکترونیک و کامپیوتر

کاربرد فناوری نانو در الکترونیک و کامپیوتر. اما مهمترين کاربرد ، استفاده در در يک گراف




تاریخچه نظریه گرافها

اندک زمانی است که واژه گراف در کامپیوتر است و علت آن نیز به خاطر قابلیت کاربرد آن در




سرفصل کنکور کارشناسی ارشد مهندسی کامپیوتر

سرفصل کنکور کارشناسی ارشد مهندسی کامپیوتر کاربرد گراف ها در کاربرد Spice در حل




برچسب :