گراف چندگانه

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
شکل (1)
گراف چندگانه

در نظریه گراف، گراف چندگانه یا گراف‌مانند یا شبه‌گراف گرافی است که می‌تواند چندین یال میان یک جفت-گره داشته باشد. این یال‌ها، یال‌های موازی نیز نامیده می‌شود.

می‌توان گراف چندگانه را با جفت مرتب نشان داد:

  • مجموعهٔ گره‌های گراف است.
  • مجموعه‌ای چندگانه از جفت‌های نامرتب است. هر جفت یالی را میان یک جفت گره نشان می‌دهد.

یال‌های چندگانه[ویرایش]

یال‌های چندگانه یال‌هایی‌اند که میان جفت‌گره‌ای یکسان باشند. درایهٔ در ماتریس همسایگی شمار یال‌های میان جفت‌گرهٔ را می‌نمایاند. درایهٔ عددی دُرُست مانند است.

شکل ۲ نشان‌گر نمونه‌ای از گرافی چندگانه و ماتریس همسایگیش است. این ماتریس همسایگی برای گرافی بی‌سو هم‌چنان همامون (متقارن) است.

شکل ۲
ماتریس همسایگی گراف چندگانه

ناسانی شبه‌گراف و گراف چندگانه[ویرایش]

برخی منبع‌ها گرافی را که دارای یالی است که دوسرش یکی باشند، گراف چندگانهٔ دارای حلقه یا شبه‌گراف می‌نامند. به سخنی دیگر، گراف چندگانه حلقه‌ای ندارد، ولی شبه‌گراف یا گراف‌مانند می‌تواند حلقه داشته باشد.

شکل (3)
شبه گراف
شکل (4)
گراف چندگانه

نمونه‌ای از کاربرد گراف چندگانه[ویرایش]

گراف چندگانه را می‌توان در مدلسازی پروازهای هوایی به کار برد. در این مدل‌سازی، گراف چندگانه می‌تواند مانند گراف ساده با جفت‌های یال‌های موازی میان شهرها باشد که پرواز یا پروازهایی به/از شهری را مدل می‌کند. گراف‌های چندگانه هم‌چنین در مدل‌سازی شبکه کاربرد دارند.

شیوهٔ ساختن گراف چندگانه[ویرایش]

گراف با مجموعه گره‌های و مجموعهٔ یالهای

  • گراف را ساختمان داده‌ای است که دربردارندهٔ فهرست گره‌ها است.
  • هر گره ساختمان داده‌ای است که فهرستی ازیالها را دارد که نشان‌گر یالهای آن گره‌اند.
  • هر یال ساختمان داده‌ای است که دربردارندهٔ اشاره‌گری به گرهٔ سر دیگر یال.

در این روش، هر گره تنها می‌داند که یک سر یال‌های خود است. این هر یال است که می‌داند سر دیگرش کدام گره است.

  • ساختمان داده‌هایی چون فهرست پیوندی گراف‌های چندگانه را به سادگی با کمک الگوریتم بالا پیاده‌سازی می‌کنند.
  • هر ساختمان داده، چه یال و چه گره، تنها یک نماینده دارد. یعنی تنها یا گره است یا یال. از همین روی، هر دِگَرِش مانند زُدودن یا افزودن محلی است (تنها یکی از فهرست‌ها می‌دِگَرَد).

بازبُردها[ویرایش]