گراف وزن‌دار

گراف وزن‌دار (نام علمی: weighted graph)، گرافی است که به هر یال آن عددی نسبت داده شده‌است[1] که وزن آن یال می‌باشد. یا به راس آن عددی نسبت داده شده. وزن یال می‌تواند نشان دهنده هزینه، مسافت، زمان یا هر مشخصه دیگری از یال باشد. بعضی از نویسنده‌ها به آن گراف شبکه‌ای می‌گویند.[2] از گراف وزن‌دار برای حل مسائلی چون فروشنده دوره گرد استفاده می‌شود. درگراف وزن‌دار، وزن‌ها را در ماتریس مجاورت ذخیره می‌کنند.

انواع گراف وزن‌دار
  • گرافی که راس‌های آن دارای وزن می‌باشند.
  • گرافی که یال‌های آن دارای وزن می‌باشند.
  • گرافی که هم راس و هم یال‌های آن دارای وزن می‌باشند.[3]

وزن یال‌ها

وزن هر یال یک گراف موزون می‌تواند نشان دهنده یکی از موارد زیر باشد:

  • هزینه یا مسافت: میزان هزینه یا مقدار مسافت برای جابه جایی از یک راس (مکان) به راس دیگر.
  • ظرفیت: حد اکثر میزان چیزی که می‌تواند از یک راس (مکان) به راس دیگر منتقل شود.

پیاده‌سازی گراف وزن‌دار

کلاس مربوط به پیاده‌سازی یال‌ها:

public class Edge

  {
     int  NodeID;     // The neighbor node
     double Weight;   // وزن یال
     Node next;       // Link variable
  }

کلاس مربوط به پیاده‌سازی گراف

public class Graph

  {
      public Edge[] graph;    // Array of Edges
  }

نمایش گراف با استفاده از ماتریس مجاورت
  • اگر بین دو راس i و j هیچ یالی نباشد، مقدار a[i][j] را برابر بینهایت قرار می‌دهیم.
  • اگر بین دو راس i و j یالی باشد، مقدار a[i][j] را برابر ارزش آن یال قرار می‌دهیم.

کلاس مربوط به پیاده‌سازی گراف وزن‌دار با استفاده از ماتریس مجاورت

public class Graph

  {
     double[][] M;      // M[i][j] = weight of edge (i,j)
     ...
  }

منابع
  1. Fletcher, Peter; Hoyle, Hughes; Patty, C. Wayne (1991). Foundations of Discrete Mathematics (International student ed.). Boston: PWS-KENT Pub. Co. p. 463. ISBN 0-534-92373-9. A weighted graph is a graph in which a number w(e), called its weight, is assigned to each edge e.
  2. Strang, Gilbert (2005), Linear Algebra and Its Applications (4th ed.), Brooks Cole, ISBN 0-03-010567-6
  3. Weisstein, Eric W. "Weighted Graph." From MathWorld--A
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.