تماس درباره   صفحه اصلی
  ساختمان داده > گراف  
 
 

گراف


گراف يک ساختمان داده غير خطی است که کاربردهای وسيعی دارد. در اين بخش برخی از اصطلاحات نظريه گراف ، روش های نمايش و عمليات روی گراف آورده شده است.

تعاریف گراف
نمایش گراف
پیمایش گراف
درخت پوشای حداقل
کاربردهای گراف


تعاریف گراف

يک گراف شامل دو مجموعه است؛ مجموعه غير تهی از گره ها يا رئوس (vertex) و مجموعه ای از يال ها (edge) که راس ها را به هم متصل می کنند.

مثال. می توان شهر های يک کشور را رئوس و جاده های بين آن ها را يال های يک گراف تصور کرد.

به هر راس يا هر يال گراف نامی اختصاص داده می شود.

يک گراف تهی (null graph) گرافی است که تنها شامل راس است و مجموعه يال های آن تهی است يعنی يالی ندارد.

جهت

يک گراف می تواند به دو شکل جهتدار(directed) يا غيرجهتدار (undirected) باشد.

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

Directed and Undirected Graph

وزن

يال های گراف می توانند وزن دار(weighted) يا بدون وزن (unweighted) باشند. گرافی که يال های آن وزن باشد گراف وزن‌دار ناميده می شود. وزن می تواند نشان دهنده هزينه، مسافت، زمان يا هر مشخصه ديگری از يال باشد.

مجاورت

هر یال بوسیله یک جفت راس مشخص می شود. دو راسی که توسط يک يال به هم متصل می شوند را رئوس مجاور (adjacent) و يال را يک لبه تلاقی (incident) دو آن رو راس می نامند.

حلقه

يک حلقه (loop) يالی است که يک راس را به خودش متصل می کند. به عبارت ديگر راس ابتدا و انتهایش یكسان باشد.

مثال. در شکل زير يال e7 يک حلقه روی راس D است

Multiple Graph

يال های موازی

يال های موازی (parallel edges) يا چندگانه یال‌هایی هستند كه رئوس یكسان را بهم مرتبط می‌كنند.

گرافی که دارای يال های موازی باشد را گراف چندگانه (multigraph) می نامند.

مثال. در گراف چندگانه شکل قبل يال های e5 و e6 که رئوس C و D را به هم متصل می کنند موازی هستند

گراف ساده

گراف بدون یال موازی و حلقه را گراف ساده (simple graph) می‌نامند. گراف جهتدار را وقتی ساده می گویند که یال موازی نداشته باشد.

حداكثر تعداد یال‌ها در یك گراف جهتدار با n‌ راس برابر است با n×(n-1).

حداكثر تعداد یال‌ها در یك گراف غيرجهتدار با n راس برابر است با n×(n-1)/2.

گراف کامل

يک گراف کامل (complete graph) گراف ساده ای است که هر جفت راس آن مجاور باشند يعنی هر از راس به کليه راس های ديگر يالی وجود داشته باشد.

Complete Graph

درجه

درجه (degree) هر راس توسط تعداد يال های متلاقی با راس مشخص می شود.

در گراف جهتدار درجه ورودی (indegree) يک راس تعداد يال هائی است که به آن راس وارد شده اند و درجه خروجی (outdegree) يک راس تعداد يآل هائی است که از آن راس خارج شده اند.

راس منبع راسی است كه درجه خروجی آن مثبت و درجه ورودی آن صفر باشد.

راس چاه راسی كه كه درجه ورودی آن مثبت و درجه خروجی آن صفر باشد.

مثال. در گراف زير درجه خروجی راس A دو و درجه ورودی آن يک است.. راس D منبع و راس B چاه است.

Degree

درجه گراف برابر درجه ماکزيمم رئوس گراف است.

گرافی که کلیه راس های آن از یک درجه باشد گراف منتظم (regular graph) ناميده می شود. گراف مکعب گراف منتظم درجه 3 است.

دریك گراف مجموع درجات كلیه رئوس همواره عددی زوج است

مسير

يک مسير(path) در گراف يک گذر از راس های متوالی در امتداد يک سری از يال ها است. راس انتهای يک يال راس ابتدای يال بعدی در توالی محسوب می شود.

طول مسير تعداد يال های مسير است که در طول مسير طی می شود. یك مسیر با طول n دارای n+1 راس و n یال است. در یگ گراف وزن دار طول مسیر برابر مجموع وزن‌های یال‌های مسیر است.

دوراس را متصل (reachable) می‌گویند اگر مسیری بین آنها وجود داشته باشد.

یك مسیر (simple path) ساده مسیری است كه همه رئوس آن بجز احتمالا راس شروع و پايان تکراری نباشد.

مثال. در شکل زير يک مسير نشان داده شده است که از راس C آغاز و به راس D ختم می شود.

Path and Cycle

دور

يک دور (cycle) مسير ساده ای است که راس شروع و پايانی آن يکی باشد.

گراف ساده جهتداری که دارای دور نيست را غير مدور (acyclic) می نامند.

يک دور در گراف ساده بدون جهت حداقل شامل سه يال متفاوت است که هيچ راسی در آن تکراری نيست بجز راس شروع و پايان.

اتصال

يک گراف غيرجهتدار متصل يا همبند (connected) گفته می شود اگر مسيری بين هر جفت راس آن وجود داشته باشد. يعنی هر دو راس آن متصل باشند.

در گراف جهتدار چون جهت بايد درنظر گرفته شود اتصال پيچيده تر است. ممکن است راس a به b متصل باشد ولی مسيری از راس b به a وجود نداشته باشد.

در گراف جهتدار ساده سه حالت برای اتصال وجود دارد:

• متصل ضعيف (weakly connected). يک گراف متصل ضعيف گرافی است که اگر جهت گراف نديده گرفته شود متصل است.
• متصل يکطرفه (unilaterally connected). يک گراف متصل يکطرفه گرافی است که حداقل يک راس آن به هر راس ديگری متصل باشد.
• متصل قوی (strongly connected). يک گراف متصل قوی گرافی است که هر جفت راس متصل باشد.

Connectness

يک گراف ساده متصل بدون دور را درخت (tree) می‌نامند. درخت گرافی است كه فقط یك مسیر بین هر دو راس آن وجود دارد.

يک درخت با ‌یك n راس است دارای n-1 یال باشد.


نمایش گراف

راه های متعددی برای نمايش گراف در کامپيوتر وجود دارد دو ساختمان داده پايه ای که برای نمايش گراف استفاده می شوند ماتريس مجاورت و ليست مجاورتی هستند.

ماتریس مجاورت

ماتريس مجاورت (adjacency matrix) گراف G با n راس (که رئوس آن به ترتيب از v1 تا vn نامگذاری شده است) يک ماتريس بيتی n×n با نام A است که در آن:

درايه aij برابر با 1 است اگر يالی از vi به vj وجود داشته باشد
درايه aij برابر با 0 است اگر يالی از vi به vj وجود نداشته باشد

مثال. گراف جهتدار زير را با پنج راس درنظر بگيريد. ماتريس مجاورت آن در سمت راست نشان داد شده است.

Adjacancy matrix example

همانطور که در شکل ديده می شود اگر يعنی دو راس مجاور باشند در موقعيت متناظر در ماتريس بايد 1 باشد. برای مثال از رئوس مجاور با v1 راس های v4، v2 و v5 هستند بنابراين در سطر اول در ستون های دوم، چهارم و پنجم بايد 1 قرار بگيرد.

ماتریس مجاورت برای یك گراف بدون جهت متقارن است.

در يک گراف غير جهتدار درجه راس ‌vi برابر با مجموع عناصر سطرi ام در ماتريس مجاورت است. و در یك گراف جهتدار درجه خروجی راس‌ vi برابر مجموع عناصر سطر i ام و درجه ورودی آن برابر مجموع عناصر ستون i ام در ماتريس مجاورت است.

فضای مورد نیاز در روش مانریس مجاورت برای نمایش یك گراف با مجموعه رئوسV برابر O(|V|2) است. اگر تعداد یال‌های گراف كم باشد می‌توان آنرا به صورت ماتریس اسپارس نمایش داد.

قضيه. اگر A‌ ماتریس مجاورتی گراف G‌ باشد، درایه aij در ماتریس Ak تعداد مسیرهای با طول k از راس vi‌ به vj را نشان می دهد.

مثال. با ضرب ماتريس مجاورت مثال قبل در خودش ماتريس A2 به صورت زير بدست می آيد. عدد 1 در سطر i و ستون j ماتريس نشان دهنده وجود مسيری با طول 2 از راس vi به vj در گراف است.

Adjacancy matrix example

با توجه به ماتريس فوق می توان گفت که از راس v1 با دو حرکت می توانيم به راس v2 برويم. اگر گراف را بررسی کنيم می شويم که از v1 به v5 و سپس به v2 می توانيم برويم. يعنی مسيری با طول 2 از راس v1 به v2 وجود دارد.

مزيت اصلی نمايش ماتريس در اين است که محاسبه مسير ها و دورها بسادگی توسط عمليات ماتريسی قابل انجام است. مجاورت بین دو راس با پيچيدگی زمان O(1) تعيين می شود و اجازه رسم حلقه در گراف را می دهد. اشکال آن اين است که از جنبه ظاهری گراف دور است و خواصی که بسادگی در شکل گراف نمايان است توسط ماتريس به سختی قابل رويت است. علاوه بر اين ماتریس همجواری یال‌های موازی را نشان نمی‌دهد.

لیست مجاورت

ليست مجاورتی (adjacency list) فرم ديگر نمايش گراف در کامپيوتر است. اين ساختمان داده شامل ليستی از کليه رئوس گراف است. برای هر راس یك لیست پیوندی وجود دارد که گره های آن رئوس مجاور راس را دربر می گيرند. به عبارت ديگر لیست i‌ حاوی رئوسی است كه مجاور راس vi است.

مثال. گراف غيرجهتدار زير را درنظر بگيريد. ليست مجاورتی آن در سمت راست آمده است:

Adjacancy list example

مثال. گراف جهتدار زير را درنظر بگيريد. ليست مجاورتی آن در سمت راست آمده است:

Adjacancy list example

درجه هر راس در یك گراف غیر جهتدار با شمارش تعداد گره‌های ليست پيوندی مربوط به راس درلیست مجاورتی تعیین می‌شود. در یك گراف جهتدار درجه خروجی هر راس با شمارش تعداد گره‌های ليست پيوندی مربوط به آن بدست می آيد.

اگر تعداد یال‌ها در گراف كم باشد این روش بهتر از ماتریس مجاورتی است. فضای مورد نیاز برای نمایش یك گراف با مجموعه رئوس V و مجموعه يال های E به روش لیست مجاورت برابر O(|E|+|V|) می‌باشد.

ليست مجاورتی به روشنی طبيعت مجاورتی رئوس گراف را نشان می دهد و اغلب زمانی استفاده می شود که گراف دارای تعداد يال های نسبتا متعادلی باشد.

لیست مجاورتی معكوس

ليست مجاورتی معکوس مشابه لیست مجاورتی ساخته می شود با این تفاوت كه در لیست پيوندی i رئوسی اضافه می شود که از آنها به راس vi یالی وارد شده باشد. تعداد گره های ليست پيوندی i ام درجه ورودی راس vi را نشان می دهد.

برای گراف غیرجهتدار لیست مجاورتی و لیست مجاورتی معكوس مشابه می شود.


پیمایش گراف

هدف از پیمایش اين است که کلیه رئوسی که از طریق یک راس قابل دسترس هستند را بدست آوریم. دو روش معروف برای پيمايش وجود دارد؛ جستجوی اول عمق (Deep First Search) و جستجوی اول سطح (Breadth First Search) .

جستجوی اول عمق

در جستجوی اول عمق پيمايش از يک راس آغاز می شود. هر راس که پردازش يا اصطلاحا ملاقات می شود يکی از رئوس مجاور آن که قبلا ملاقات نشده است انتخاب می شود و پيمايش با ملاقات راس مجاور ادامه پیدا می‌كند. اگر راس مجاوری وجود نداشت که قبلا ملاقات نشده باشد یك سطح به عقب برمی گردد.

الگوريتم بازگشتی جستجوی اول عمق به صورت زير است. آرايه يک بعدی Visited تعيين می کند آيا راسی قبلا ملاقات شده است يا خير. اگر راس vi ملاقات شود Visited[i] برابر با يک می شود.

DFS (int v)
{
  int w
  Visited[v]:=1
  For (each vertex w adjacent to v)
    If (not visited[w]) then
      DFS(w)
    End if
  End For
}

ترتیب ملاقات رئوس را DFN می‌نامند.

برای گراف G با n راس و m يال ، مرتبه اجرائی الگوريتم وقتی گراف توسط ماتریس مجاورتی نمايش داده شده باشد O(n2) و اگر از لیست مجاورتی استفاده شود O(m)‌ است.

مثال. مراحل اجرای DFS(v1) برای يک گراف در شکل زير نشان داده شده است.

DFS example

جستجوی اول سطح

در جستجوی اول سطح پيمايش از يک راس آغاز می شود. آن راس و کليه رئوس مجاورش ملاقات می شود سپس پيمايش از راس مجاور ادامه پيدا می کند.

الگوريتم جستجوی اول سطح به صورت زير است. آرايه Visited برای تعيين رئوس ملاقات شده بکار می رود. از يک صف برای نگهداشتن رئوس مجاور استفاده می شود. هر بار که راسی ملاقات می شود کليه رئوس مجاور آن در صف اضافه می شود. پيمايش از راسی که از صف برداشته می شود ادامه پيدا می کند.

BFS (int v)
{   int w
  Queue q

  Visited[v]:=1
  CreateQueue(q)
  AddQueue(q, v)
  While (not EmptyQueue(q))
    DeleteQueue(q,v)
    For (all vertex w adjacent to v)
      If (not visited[w]) then
        AddQueue(q,w)
        Visited[w]:=1
      End if
    End For
  End while
}

برای گراف G با n راس و m يال ، مرتبه اجرائی الگوريتم وقتی گراف توسط ماتریس مجاورتی نمايش داده شده باشد O(n2) و اگر از لیست مجاورتی استفاده شود O(m)‌ است.

مثال. مراحل اجرای BFS(v1) برای يک گراف در شکل زير نشان داده شده است.

BFS example

درخت پوشای حداقل

همانطور که قبلا تعريف شد درخت يک گراف متصل بدون است. يک درخت پوشا (spanning tree) زيرگرافی از گراف G است که شامل کليه رئوس گراف G باشد و يک درخت باشد. بنابراين اگر گراف G دارای n گره باشد درخت پوشای آن دارای n-1 یال است.

پیمایش‌های DFS و BFS هر کدام يک درخت پوشا تولید می‌كنند.

تعداد درخت‌های پوشای یك گراف كامل با n گره برابر 2n-1-1 است.

مثال. دو درخت های پوشا که از پيمايش های DFS و BFS گراف G بدست آمده در شکل زير نشان داده شده اند.

Spanning Tree example

درخت پوشای حداقل (Minimum Spanning Tree) گراف وزن دار G، درخت پوشائی است که مجموع وزن های آن حداقل باشد.

برای بدست آوردن درخت پوشای حداقل دو الگوريتم الگوريتم کروسکال (Kruskal) و الگوريتم پريم (Prim) را بررسی می کنيم.

الگوریتم کروسکال

گراف G با n راس را در نظر بگيريد. الگوريتم کروسکال به صورت زير عمل می کند:

1. تمام یال ها را به طور صعودی بر حسب وزن مرتب کنید.
2. درخت T را متشکل از گره های G بدون یال را ايجاد کنيد.
3. عملیات زیر را n-1 بارتکرار کنید:
4. یک یال با حداقل وزن را به درخت T اضافه کنید به طوریکه حلقه ایجاد نشود.

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

پيچيدگی زمانی الگوريتم O(mn) می شود. که m تعداد يال ها و n تعداد رئوس گراف G است.

الگوریتم پریم

گراف G با n راس را در نظر بگيريد. الگوريتم پريم به صورت زير عمل می کند:

1. درخت تهی T را ايجاد کنيد.
2. راس v از گراف را انتخاب کرده و به درخت اضافه کنيد.
3. عمليات زير را تکرار کنيد تا کليه راس های گراف به درخت T اضافه شوند:
3. يالی که با حداقل وزن به رئوس T متصل است را پيدا کنيد. يال و راس متصل به آن را به درخت T اضافه کنيد به طوريکه حلقه ايجاد نشود.

پيچيدگی زمانی الگوريتم O(mn) می شود. که m تعداد يال ها و n تعداد رئوس گراف G است.

مثال

Minimum Spanning Tree example

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

گراف کاربردهای متعددی در مسائل مختلف دارد از جمله می توان کاربردهای زير را نام برد:

• پیداکردن کوتاهترین مسیر بین دو نقطه
• شبکه AOV برای کنترل پروژه و فعالیت ها و ارتباط بین آنها
• مسیربحرانی


 


 


صفحه اصلی| PDF| درباره| تماس