کاربرد گراف در کامپیوتر

• • کاربرد گراف

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

    ساختارهای زیادی را می‌توان به کمک گراف‌ ها به نمایش در آورد. برای مثال برای نمایش چگونگی رابطه وب سایت‌ها به یکدیگر می‌توان از گراف جهت دار استفاده کرد.

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

  • گراف و درخت

  • درخت و ماتریس درخت در رشته‌های مختلفی مانند شیمی مهندسی برق و علم محاسبه کاربرد دارد . کیرشهف در سال ۱۸۴۷ میلادی هنگام حل دستگاههای معادلات خطی مربوط به شبکه‌های الکتریکی. درختها را کشف و نظریه درختها را بارور کرد.
  • کیلی در سال ۱۸۵۷ میلادی درختها را در ارتباط با شمارش ایزومرهای مختلف هیدروکربنها کشف کرد .
  • وقتی مثلا میگوییم در ایزومر مختلف c4h۱۰ وجود دارد منظورمان این است که دو درخت متفاوت با ۱۴ راس وجود دارند که درجه ۴ راس از این ۱۴ راس جهار و درجه هر یک از ۱۰ راس باقیمانده یک است.
  • اگر هزینه کشیدن مثلا راه آهن بین هر دو شهر ازp شهر مفروض مشخص باشد ارزانترین شبکه ای که این p شهر را به هم وصل می‌کند با مفهوم یک درخت از مرتبه p ارتباط نزدیک دارد.
  • به جای مساله مربوط به راه آهن میتوان وضعیت مربوط به شبکه‌های برق رسانی و لوله کشی نفت و لوکشی گاز و ایجاد کانالهای آبرسانی را در نظر گرفت . برای تعیین یک شبکه با نازلترین هزینه از قاعده ای به نام الگوریتم صرفه جویی استفاده می‌شود که کاربردهای فراوان دارد. از گرافها می توان به عنوان کدهای کمکی نام برد که به DVB Player‌ها در بالا بردن قابلیت‌های آنها کمک میکنند. گراف‌ها …