وبینار رایگان سه ماه مهم تا کنکور ارشد مهندسی کامپیوتر و IT
مشاهده وبینار
کنکور کامپیوتر
گراف چیست،‌ آموزش تمامی مطالب گراف

گراف چیست، آموزش گراف از 0 تا 100 توسط دانشجو ارشد صنعتی شریف

در این مقاله تمامی مطالب مربوط به گراف از 0 تا 100 تدریس شده است. مواردی همچون : گراف چیست؟ انواع گراف، گراف همبند، مکمل گراف،‌ گراف کامل، گراف جهت دار، گراف بدون جهت،‌ گراف ساده و ...

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

در ادامه به آموزش گراف که از فصول مهم ریاضیات گسستهجامع ترین آموزش درس ریاضی گسستهجامع ترین آموزش درس ریاضی گسستهدرس ریاضیات گسسته به معرفی مباحثی نظیر شمارش و احتمال، استدلال و برهان خلف، نظریه اعداد، منطق ریاضی، روابط بازگشتی، روابط و نظریه‌ گراف می‌پردازد. از آن رو که در عصر کنونی ریاضی گسسته بطور گسترده‌ در رشته کامپیوتر و برنامه نویسی استفاده می‌شود در این صفحه به معرفی و بررسی درس ریاضی گسسته پرداخته شده است، ساختمان دادهآموزش ساختمان داده و الگوریتمآموزش ساختمان داده و الگوریتمهر ساختمان داده یک نوع فرمت ذخیره‌سازی و مدیریت داده‌ها در کامپیوتر است، که امکان دسترسی و اصلاح کارآمد آن داده‌ها را برای یکسری از الگوریتم‌ها و کاربردها فراهم می‌کند، در این صفحه به بررسی و آموزش ساختمان داده و الگوریتم پرداخته شده است و طراحی الگوریتمآموزش طراحی الگوریتم به زبان سادهآموزش طراحی الگوریتم به زبان سادهدرس طراحی الگوریتم‌ یکی از مهم‌ترین و بنیادیترین دروس‌ رشته کامپیوتر است. هدف از این درس، معرفی روش‌های مختلف طراحی الگوریتم‌ها برای حل مسائل گوناگون است، در این صفحه به معرفی و آموزش طراحی الگوریتم پرداخته شده است. بشمار می‌رود می‌پردازیم. در مقاله‌ی نظریه گرافهمه چیز در مورد نظریه گراف (Graph Theory)همه چیز در مورد نظریه گراف (Graph Theory)در این مقاله یک مقدمه جامع در رابطه با نظریه گراف ارائه شده است و سعی شده نشان داده شود که دانستن برخی از مبانی نظریه گراف تا چه میزان می­‌تواند مفید و موثر باشد. (Graph Theory) که توسط خانم فدایی، دانشجوی ارشد مهندسی کامپیوتر دانشگاه صنعتی شریف، نوشته شده است، به آشنایی با نظریه گراف، تاریخچه نظریه گراف، انواع گراف، کاربرد گراف و دیگر موارد مهم بطور جامع پرداخته شده است که در صورت علاقه‌مندی توصیه می‌شود که مطالعه این مقاله عالی را از دست ندهید.

گراف چیست؟

گراف بعنوان یک شبکه با مجموعه‌ای از نقاط و خطوط شناخته می‌شود. هر گراف G، شامل دو مجموعه V و E است که:

1) V، مجموعه محدود و غیرتهی از رئوس می‌باشد.

2) E، مجموعه‌ای محدود (تهی یا غیرتهی) از لبه‌ها (یال‌ها) می‌باشد.

V(G) و E(G) مجموعه رئوس و لبه‌های گراف G را نمایش می‌دهند. بنابراین برای نمایش یک گراف از $\mathrm{G\ =\ }\left(\mathrm{V\ ,\ E}\right)$ استفاده می‌کنیم.

نتیجه: هر گراف حداقل یک رأس دارد و نمی‌تواند کاملاً تهی باشد.

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

انواع یال در گراف

یال‌ها در گراف به دو دسته یال جهت دار و یال بی جهت تقسیم می‌شود.

1 یال جهت‌دار این تصویر نمونه ساده از یال جهت دار است. (2,3) زوج مرتب
2 یال غیرجهت‌دار این تصویر نمونه ساده از یال غیر جهت دار است. 12={1, 2}  زوج نامرتب

انواع گراف

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

  1. گراف بدون جهت
  2. گراف جهت‌دار
  3. گراف مختلط یا آمیخته

گراف بدون جهت

در یک گراف بدون جهت هر لبه (یال، ضلع) به صورت $\left\{{\mathrm{v}}_{\circ },\ {\mathrm{v}}_{\mathrm{1}}\right\}$ یا $\left\{{\mathrm{v}}_{\mathrm{1}},\ {\mathrm{v}}_{\mathrm{\circ }}\right\}$ نمایش داده می‌شود که ${\mathrm{v}}_{\circ }$ و ${\mathrm{v}}_{\mathrm{1}}$ دو رأس لبه هستند، ترتیب رئوس در بیان یک لبه مهم نبوده و در حقیقت زوج رئوس، زوج مرتب نیستند. به عبارت بهتر: $\left\{{\mathrm{v}}_{\circ },\ {\mathrm{v}}_{\mathrm{1}}\right\}=\left\{{\mathrm{v}}_{\mathrm{1}},\ {\mathrm{v}}_{\mathrm{\circ }}\right\}$ 

گراف بدون جهت لبه‌ها (Edges) رئوس (Vertex)
این تصویر نمونه ساده از گراف غیر جهت دار است. \[\mathrm{E}\left(\mathrm{G}\right)=\left\{\left\{\mathrm{1}\mathrm{\ ,\ }\mathrm{2}\right\},\left\{\mathrm{1}\mathrm{\ ,\ }\mathrm{4}\right\},\left\{\mathrm{2}\mathrm{\ ,\ }\mathrm{3}\right\},\left\{\mathrm{3}\mathrm{\ ,\ }\mathrm{4}\right\}\right\}\] \[\mathrm{V}\left(\mathrm{G}\right)=\left\{\mathrm{1}\mathrm{\ ,\ }\mathrm{2}\mathrm{\ ,\ }\mathrm{3}\mathrm{\ ,\ }\mathrm{4}\right\}\]

دقت کنید در نمایش بالا برای لبه‌ها E(G) می‌توان: به‌جای $\left\{\mathrm{1}\mathrm{\ ,\ }\mathrm{2}\right\}$ از $\left\{\mathrm{2}\mathrm{\ ,\ }\mathrm{1}\right\}$، به‌جای $\left\{\mathrm{1}\mathrm{\ ,\ }\mathrm{4}\right\}$ از $\left\{\mathrm{4}\mathrm{\ ,\ }\mathrm{1}\right\}$، به‌جای $\left\{\mathrm{2}\mathrm{\ ,\ }\mathrm{3}\right\}$ از $\left\{\mathrm{3}\mathrm{\ ,\ }\mathrm{2}\right\}$ و به‌جای $\left\{\mathrm{3}\mathrm{\ ,\ }\mathrm{4}\right\}$ از $\left\{\mathrm{4}\mathrm{\ ,\ }\mathrm{3}\right\}$ استفاده کرد. 

گراف جهت‌دار (Digraph)

در یک گراف جهت‌دار هر لبه (یال، ضلع) با زوج مرتب $\left({\mathrm{v}}_{\circ },\ {\mathrm{v}}_{\mathrm{1}}\right)$ نمایش داده می‌شود. که ${\mathrm{v}}_{\circ }$ ابتدای لبه و ${\mathrm{v}}_{\mathrm{1}}$ انتها، هستند. بنابراین $\left({\mathrm{v}}_{\mathrm{1}},\ {\mathrm{v}}_{\mathrm{\circ }}\right)$ و $\left({\mathrm{v}}_{\circ },\ {\mathrm{v}}_{\mathrm{1}}\right)$ دو لبه متفاوت را نمایش می‌دهند. به عبارت بهتر: \[\left({\mathrm{v}}_{\circ },\ {\mathrm{v}}_{\mathrm{1}}\right)\ \neq \ \left({\mathrm{v}}_{\mathrm{1}},\ {\mathrm{v}}_{\mathrm{\circ }}\right)\]

گراف جهت‌دار لبه‌ها (Edges) رئوس (Vertex)
این تصویر نمونه ساده از گراف جهت دار است. \[\mathrm{E}\left(\mathrm{G}\right)=\left\{\mathrm{(}\mathrm{1}\mathrm{\ ,\ }\mathrm{2}\mathrm{\ )\ ,\ (}\mathrm{2}\mathrm{\ ,\ }\mathrm{1}\mathrm{\ )}\ ,\ (\mathrm{2}\mathrm{\ ,\ }\mathrm{3}\mathrm{)}\right\}\] \[\mathrm{V}\left(\mathrm{G}\right)=\left\{\mathrm{1}\mathrm{\ ,\ }\mathrm{2}\mathrm{\ ,\ }\mathrm{3}\mathrm{\ }\right\}\]

دقت کنید:

  • از این به بعد، گراف جهت‌دار را "digraph" و گراف بدون جهت را گراف می‌نامیم.
  • برای یک گراف بدون جهت، همواره لبه‌ها یا همان یال ها به صورت خطوط یا منحنی‌ها نمایش داده می‌شوند.
  • برای گراف جهت‌دار لبه‌ها یا همان یال ها به صورت فلش‌هایی هستند که از ابتدا به انتها رسم شده‌اند.

زیر گراف

هر زیر مجموعه از V (رئوس) و E (لبه‌ها) به عنوان زیر گراف‌های G می‌توانند در نظر گرفته شوند.

بعضی از زیرگراف‌های گراف G گراف G
این تصویر یک زیر گراف است این تصویر یک زیر گراف است این تصویر یک زیر گراف است این عکس یک گراف جهت دار را نشان می‌دهد.
این تصویر یک زیر گراف است این تصویر یک زیر گراف است این تصویر یک زیر گراف است این تصویر یک گراف غیر جهت دار را نشان می‌دهد.

همسایگی گراف یا مجاور بودن (Adjacent) در گراف

دو گره V , U را در یک گراف مجاور (همسایه) گوییم هرگاه لبه مستقیمی بین آن‌ها وجود داشته باشد. به عبارت بهتر:

  1. در گراف بدون جهت : دو گره V , U مجاور (همسایه) هستند هرگاه لبه {U , V} وجود داشته باشد.
  2. در گراف جهت‌دار: هرگاه لبه $\mathrm{(\ }\mathrm{U\ ,\ V)}\ $ وجود داشته باشد یعنی یال مستقیمی از U به V وجود دارد، به عبارت بهتر: (U مجاور به رأس V) یا (V مجاور از رأس U) است.
توضیحات گراف G

گره‌های مجاور به 1 عبارتند از: 4 , 2

گره‌های مجاور به 3 عبارتند از: 4 , 2

گره‌های مجاور به 2 عبارتند از: 3 , 1

گره‌های مجاور به 4 عبارتند از: 3 , 1

این تصویر نمونه ساده از گراف غیر جهت دار است.

گره 2 مجاور به رأس 3 , 1 است.

گره 1 مجاور به رأس 2 است.

گره 3 به ‌جایی مجاور نیست.

این تصویر نمونه ساده از گراف جهت دار است.

گراف کامل (Complete Graph)

یک گراف کامل با n رأس، گرافی است که حداکثر تعداد لبه را دارد.

گراف کامل جهت‌دار با n رأس گراف کامل بدون جهت با n رأس
این تصویر یک گراف کامل جهت‌دار با n رأس است.

\[\text{تعداد}\mathrm{\ }\text{لبه‌ها}\mathrm{\ =\ n}\left(\mathrm{n}\mathrm{-}\mathrm{1}\right)\]

این تصویر یک گراف کامل بدون جهت با n رأس است.

\[\text{تعداد}\mathrm{\ }\text{لبه‌ها}\mathrm{\ =\ }\frac{\mathrm{n}\left(\mathrm{n}\mathrm{-}\mathrm{1}\right)}{\mathrm{2}}\]

گراف بدون جهت G با n راس کامل است اگر و فقط اگر یکی از شرایط زیر برقرار باشد:

  1. بین هر دو رأس دلخواه لبه (ضلع) مستقیمی وجود داشته باشد.
  2. هر دو رأس دلخواه مجاور (همسایه) باشند.
  3. درجه هر کدام از رئوس $n-1$ باشد.
  4. تعداد لبه‌ها (اضلاع) $\frac{\mathrm{n}\left(\mathrm{n}\mathrm{-}\mathrm{1}\right)}{\mathrm{2}}$ باشد.

مسیر در گراف (Path Graph)

مسیر: هر مجموعه از لبه‌های پشت سرهم که دو رأس را به هم متصل می‌کنند مسیر نامیده می‌شود.

طول مسیر: تعداد لبه‌های موجود در مسیر را طول مسیر می‌گویند.

مسیر ساده: مسیری است که همه رئوس آن به جز احتمالاً اول و آخر، متفاوت است.

حلقه در گراف (سیکل یا چرخه cycle): مسیر ساده‌ای که اولین و آخرین رأس آن با هم برابر است.

مثال اول: در گراف مقابل چند مسیر ساده به طول 2 قرار دارد؟

  1. 0
  2. 1
  3. 4
  4. 3
این تصویر یک گراف جهت دار است.

حل: گزینه 3 درست است.

(cycle) 1-3-1

(cycle) 3-1-3

2-3-1

2-1-3

مثال دوم: در گراف مقابل چند مسیر ساده به طول 3 قرار دارد؟

  1. 0
  2. 1
  3. 4
  4. 3
این تصویر یک گراف جهت دار است.

حل: گزینه 4 درست است.

(cycle) 1-3-2-1

(cycle) 2-1-3-2

(cycle) 3-2-1-3

مثال سوم: اگر b , a دو گره در یک گراف بدون جهت G باشند و اگر دو مسیر 1P , 2P از a به b وجود داشته باشد، آن‌گاه:

  1. b , a مجاورند.
  2. G نمی‌تواند یک گراف باشد.
  3. G دارای چرخه است.
  4. احتیاج به جهت مسیر داریم.

حل: گزینه 3 درست است.

دو گره b , a زمانی مجاورند هرگاه لبه مستقیمی (مسیری به طول 1) بین آن‌ها وجود داشته باشد. هرگاه بین دو رأس بیش از یک مسیر وجود داشته باشد آن‌گاه حتماً در گراف چرخه وجود دارد.

سیکل (cycle) روی رأس V: به تمام مسیرهای ساده که با رأس v شروع شده و به رأس v ختم شود:

path: v, …, v

مثال: تمام سیکل‌ها روی رأس v1 عبارتند از:


  1. v1-v2-v1
  2. v1-v2-v4-v1
  3. v1-v2-v3-v1
  4. v1-v2-v3-v4-v1
این تصویر یک گراف جهت دار است.

رئوس متصل (همبند) در گراف

در گراف بدون جهت دو رأس دلخواه ${\mathrm{v}}_{\mathrm{j}}\mathrm{\ ,\ }{\mathrm{v}}_{\mathrm{i}}$ را متصل می‌گوییم اگر مسیری از ${\mathrm{v}}_{\mathrm{i}}$ به ${\mathrm{v}}_{\mathrm{j}}$ و یا بالعکس وجود داشته باشد.

گراف همبند (متصل)

گراف بدون جهت را گراف متصل یا گراف همبند گوییم اگر برای هر دو رأس ${\mathrm{v}}_{\mathrm{i}}$ و ${\mathrm{v}}_{\mathrm{j}}$ مسیری از ${\mathrm{v}}_{\mathrm{i}}$ به ${\mathrm{v}}_{\mathrm{j}}$ و یا بالعکس وجود داشته باشد.

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

گراف متصل بدون چرخه (سیکل)

این تصویر یک گراف متصل با چرخه (سیکل) است.

گراف متصل با چرخه (سیکل)

این تصویر یک گراف غیرمتصل است.

گراف غیرمتصل

یادآوری: هر درخت یک گراف همبند (متصل) بدون دور یا حلقه است.

مولفه همبندی

یک مؤلفه اتصال یا به‌طور ساده‌تر یک مؤلفه در گراف بدون جهت بزرگ‌ترین زیرگراف همبند در آن گراف است.

توضیحات گراف بدون جهت G
G1 یک مؤلفه از گراف G است. این تصویر یک گراف غیر جهت دار را نشان می‌دهد.
G1 , G2 دو مؤلفه از گراف G هستند. این تصویر یک گراف غیر جهت دار را نشان می‌دهد.
G1 , G2 , G3 سه مؤلفه از گراف G هستند. این تصویر یک گراف غیر جهت دار را نشان می‌دهد.

گراف همبند قوی (کاملا متصل)

یک گراف جهت‌دار کاملاً متصل نامیده می‌شود هرگاه برای هر زوج رأس ${\mathrm{v}}_{\mathrm{i}}$ و ${\mathrm{v}}_{\mathrm{j}}$ مسیری جهت‌دار از ${\mathrm{v}}_{\mathrm{i}}$ به ${\mathrm{v}}_{\mathrm{j}}$ و همچنین از ${\mathrm{v}}_{\mathrm{j}}$ به ${\mathrm{v}}_{\mathrm{i}}$ وجود داشته باشد.

G1 G2 G3
این تصویر یک گراف کاملا متصل با همبند قوی است. این تصویر یک گراف کاملا متصل است. این تصویر یک گراف با همبندی ضعیف است.

(گراف کاملاً متصل است)

(همبند قوی)
(گراف کاملاً متصل است)

(گراف کاملاً متصل نیست)

(همبند ضعیف)

مولفه های قویا همبند گراف

یک مؤلفه کاملاً متصل (قویا همبند) بزرگ ترین زیر گراف کاملاً متصل در گراف جهت‌دار است.

توضیحات گراف جهت‌دار G
G1 , G2 , G3 سه مؤلفه کاملاً متصل (قوی) از گراف G هستند. این تصویر یک گراف را نشان می‌دهد.
G1 , G2 دو مؤلفه کاملاً متصل (قوی) از گراف G هستند. این تصویر یک گراف را نشان می‌دهد.
G1 یک مؤلفه کاملاً متصل (قوی) از گراف G نیست. این تصویر یک گراف را نشان می‌دهد.

درجه گراف (Graph degree)

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

درجه گراف غیر جهت دار

درجه یک راس از گراف بدون جهت تعداد لبه‌ها یا یال‌های متلاقی با آن رأس است. به عبارت بهتر درجه هر رأس از گراف تعداد گره‌های مجاور به رأس را نشان می‌دهد.

این تصویر یک گراف غیر جهت دار را نشان می‌دهد.

درجه گراف جهت دار

در هر گراف جهتدار درجه یک رأس برابر است با: (درجه وارده + درجه خارجه) که:

  • درجه ورودی (وارده): تعداد یال‌هایی که به رأس وارد می‌شوند.
  • درجه خروجی (خارجه): تعداد یال‌هایی که از رأس خارج می‌شوند.

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

گره‌های چاه و منبع:

  • گره چاه: به گره‌ای که درجه خروجی آن در گراف جهت‌دار باشد.
  • گره منبع: به گره‌ای که درجه ورودی آن در گراف جهت‌دار باشد.

این تصویر یک گراف جهت دار را نشان می‌دهد که گره منبع و چاه در آن مشخص شده است.

درجه گراف:

درجه هر گراف برابر با بزرگ‌ترین درجه گره‌های آن گراف است.

این تصویر دو گراف را نشان می‌دهد که درجه گراف آن ها نیز بدست آمده است.

دقت کنید اگر درجه رأسی فرد باشد آن رأس را راس فرد گویند و اگر زوج باشد آن رأس را راس زوج گویند. تعداد رأس‌های فرد یک گراف غیرجهت‌دار همواره عددی زوج است.

این تصویر یک گراف را نشان می‌دهد.

تعداد یال ها و درجه هر راس گراف

اگر در گراف G (جهت‌دار یا بدون جهت) با n رأس، ${\mathrm{d}}_{\mathrm{i}}$ درجه رأس i و e تعداد لبه‌ها باشد تعداد لبه‌های گراف برابر است با:

\[\mathrm{e\ =\ }\frac{\left(\sum^{\mathrm{n}}_{\mathrm{i\ =\ }\mathrm{1}}{{\mathrm{d}}_{\mathrm{i}}}\right)}{\mathrm{2}}\mathrm{\ \ \ \ \ \ \ \ \ \ \ \ }{{\stackrel{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }{\longrightarrow}}}\ \ \ \ \ \ \ \ \ \ تعداد\mathrm{\ }لبه‌ها\mathrm{\ (}یال‌ها\mathrm{)}\mathrm{\ =\ }\frac{\mathrm{\ \ \ }مجموع\mathrm{\ }درجه\mathrm{\ }رئوس\mathrm{\ \ \ }}{\mathrm{2}}\]

تعداد لبه‌ها (یال‌ها، اضلاع) گراف G
\[\mathrm{e\ =\ }\frac{\sum{{\mathrm{d}}_{\mathrm{i}}}}{\mathrm{2}}=\frac{\mathrm{1}\mathrm{\ +\ }\mathrm{2}\mathrm{\ +\ }\mathrm{2}\mathrm{\ +\ }\mathrm{1}}{\mathrm{2}}=\mathrm{3}\] این تصویر یک گراف غیر جهت دار را نشان می‌دهد.
\[\mathrm{e\ =\ }\frac{\sum{{\mathrm{d}}_{\mathrm{i}}}}{\mathrm{2}}=\frac{\mathrm{3}\mathrm{\ +\ }\mathrm{3}\mathrm{\ +\ }\mathrm{2}\mathrm{\ }}{\mathrm{2}}=\mathrm{4}\] این تصویر یک گراف جهت دار است.

گراف مکمل (Complement Graph)

در صورتی که G یک گراف دلخواه باشد، گراف مکمل G گرافی است که هیچ یال مشترکی با آن نداشته و مجموع دو گراف یک گراف کامل (Complete) را تشکیل می‌دهند به‌طور مثال:

گراف کامل گراف مکمل G گراف G
این تصویر یک گراف کامل است. این تصویر یک گراف کامل G است. این تصویر یک گراف است.

گراف منتظم

گرافی که درجه همه رئوس آن برابر باشد، گراف منتظم نامیده می‌شود. به عنوان مثال گراف‌های زیر نمایشی از گراف دو منتظم با تعداد رئوس متفاوت است.

در این تصویر نمایش‌هایی از گراف منتظم نشان داده شده است.

گراف اویلری

قبل از پرداختن به بحث گراف اویلری و خواص آن، به تعریف چند اصطلاح پرکاربرد در گراف می‌پردازیم:

  • گشت (Walk): به دنباله‌ای از رئوس گراف گشت گفته می‌شود.
  • گذر (Trail): دنباله‌ای از رئوس گراف که یال تکراری ندارد. اگر راس شروع و پایان گذر یکی باشد به آن مدار (Circuit) می‌گویند.
  • مسیر (Path): دنباله‌ای از رئوس گراف که راس تکراری ندارد. اگر راس شروع و پایان یکسان باشد به آن دور یا سیکل (Cycle) می‌گویند.

گذر اویلری

گذری در گراف که همه یال‌ها را طی کند (در گذر یال تکراری نداشتیم) گذر اویلری نام دارد. به شکل زیر توجه کنید.

این تصویر گذر اویلری را نشان می‌دهد.

در این گراف، گذر bcdbad یک گذر اویلری از گراف است. همانطور که مشخص است این گذر از یال تکراری عبور نکرده است.

مدار اویلری

مداری در گراف که همه یال‌ها را طی کند (در مدار یال تکراری نداشتیم) مدار اویلری نام دارد. گرافی که مدار اویلری داشته باشد را گراف اویلری می‌گویند.

قضیه: شرط لازم و کافی برای وجود مدار اویلری در یک گراف غیرجهت‌دار، آن است که اولاً گراف همبندی باشد و ثانیاً  درجه همه رئوس زوج باشد.

اگر گراف غیرجهت دار همبند دارای مدار اویلری باشد چگونه می‌توان گفت که درجه همه رئوس زوج است؟

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

قضیه: شرط لازم و کافی برای وجود گذر اویلری در یک گراف غیرجهت‌دار، آن است که اولاً گراف همبند باشد و ثانیاً یا هیچ راس درجه فردی نداشته باشیم و یا دقیقا دو راس درجه فرد داشته باشیم.

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

با توجه به استدلالات بیان شده برای گذر و مدار اویلری در گراف‌ غیرجهت دار همبند، می‌توان برای گراف جهت دار همبند به صورت زیر استدلال کرد:

قضیه: شرط لازم و کافی برای وجود مدار اویلری در گراف جهت‌دار آن است که گراف همبند باشد و هر راسی، درجه ورودش با درجه خروجش برابر باشد.

قضیه: شرط لازم و کافی برای وجود گذر اویلری در گراف جهت‌دار آن است که گراف همبند باشد و هر راسی، درجه ورودش با درجه خروجش برابر باشد به جز احتمالا دو راس $V_1 $ و $V_2 $ که باید به صورت زیر باشند:

 indeg($V_1$) = outdeg($V_1$) + 1

outdeg($V_2$) = indeg($V_2$) + 1

در این صورت از راسی شروع می‌کنیم که درجه خروجی‌اش یکی بیشتر از درجه ورودی‌ش است و در آخر نیز وارد راسی می‌شویم که درجه ورودش یکی بیشتر از خروجش باشد.

نمایش گراف (ذخیر سازی گراف در کامپیوتر)

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

  1. ماتریس مجاورتی
  2. لیست مجاورتی (همجواری)
  3. لیست مجاورتی معکوس

ماتریس مجاورتی (Adjacent Matrix)

فرض کنید G(V , E) گرافی با n رأس باشد، ماتریس مجاورتی گراف G یک آرایه دو بعدی است به صورت n $\mathrm{\times}$ n که ${\mathrm{n}}^{\mathrm{2}}$ خانه دارد و به صورت زیر پیاده‌سازی می‌شود:

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

در صورتی که لبه یا یالی به صورت $\left\{{\mathrm{v}}_{\mathrm{i}}\mathrm{\ ,\ }{\mathrm{v}}_{\mathrm{j}}\right\}$ وجود داشته باشد $\mathrm{A}\left[\mathrm{i}\right]\left[\mathrm{j}\right]=\mathrm{1}$ است در غیر این صورت $\mathrm{A}\left[\mathrm{i}\right]\left[\mathrm{j}\right]=\mathrm{\circ }$ است.

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

مشخصات ماتریس مجاورتی گراف بدون جهت:

  • ماتریس مجاورتی برای یک گراف بدون جهت همواره نسبت به قطر اصلی گراف متقارن است، بنابراین می‌توانیم تنها مثلث بالایی یا پایینی را ذخیره کنیم.
  • تعداد 1‌های ماتریس همواره 2 برابر تعداد یال‌ها (لبه‌ها) می‌باشد.
  • مجموع عناصر سطری یا ستونی برای هر رأس درجه آن را نشان می‌دهد.

ماتریس مجاورتی گراف جهت دار

در این تصویر ماتریس مجاورتی گراف جهت دار نشان داده شده است.

مشخصات ماتریس مجاورتی گراف جهت‌دار:

  1. ماتریس مجاورتی برای یک گراف جهت‌دار همواره متقارن نیست بنابراین باید تمام خانه‌های ماتریس (n2 خانه) را ذخیره کرد.
  2. تعداد 1های ماتریس برابر با تعداد یال‌ها (لبه‌ها) می‌باشد.
  3. برای هر رأس همواره:

مجموع عناصر ستونی هر رأس = درجه ورودی رأس (indegree)

مجموع عناصر سطری هر رأس = درجه خروجی رأس (outdegree)

دقت کنید اگر ماتریس مجاورتی یک گراف جهت‌دار، ماتریس بالا مثلثی یا پایین مثلثی باشد، (صرف نظر از مقدار درایه‌های قطر اصلی) آن گراف الزاماً گراف بدون دور یا Acyclic است زیرا اگر قرار بود دوری داشته باشد میبایست یک مسیر برگشت به ازای یکی از مسیرهایی واقع در ماتریس بالا مثلثی وجود میداشت، یعنی یک مسیر در پایین ماتریس (زیر مثلث بالایی)، اما در این صورت دیگر آن ماتریس، ماتریس بالا مثلثی نمی‌شد.

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

مثال:

\[ماتریس\mathrm{\ }مجاورتی\mathrm{\ :\ } \begin{array}{c} \mathrm{\ } \\ \mathrm{1} \\ \begin{array}{c} \mathrm{2} \\ \mathrm{3} \end{array} \end{array} \begin{array}{c} \begin{array}{ccc} \mathrm{1} & \mathrm{2} & \mathrm{3} \end{array} \\ \left[ \begin{array}{ccc} \mathrm{\ }\mathrm{\circ } & \mathrm{1} & \mathrm{\circ }\mathrm{\ } \\ \mathrm{\ }\mathrm{\circ } & \mathrm{\circ } & \mathrm{\circ }\mathrm{\ } \\ \mathrm{\ }\mathrm{\circ } & \mathrm{1} & \mathrm{\circ }\mathrm{\ } \end{array} \right] \end{array} \mathrm{\ }\]

این تصویر یک گراف است.

در واقع می‌توان گفت:

  • بالا مثلثی یا پایین مثلثی بودن ماتریس مجاورتی یک گراف شرط کافی برای (Acyclic) بودن آن است؛ اما شرط لازم نیست.
  • (Acyclic) بودن یک گراف شرط لازم برای بالا مثلثی یا پایین مثلثی بودن ماتریس مجاورتی آن است؛ اما شرط کافی نیست.

یادآوری: گراف بدون سیکل (Acyclic) گرافی است که در آن هیچ سیکلی وجود ندارد.

نکات مهم ماتریس مجاورتی

  1. از نقاط قوت ماتریس مجاورتی این است که سرعت عملیات دسترسی به این که آیا دو گره i و j مجاور هم هستند یا نه؟ (لبه مستقیمی از i به j وجود دارد یا خیر) از مرتبه (1)O است.

    if (A[i][j] = 1) then

        (i , j) is adj

    else

        (i , j) is not adj

  2. اغلب الگوریتم‌ها با استفاده از ماتریس مجاورتی با زمان $\mathrm{O}\left({\mathrm{n}}^{\mathrm{2}}\right)=\mathrm{O}\left({\left|\mathrm{V}\right|}^{\mathrm{2}}\right)$ به دست می‌آیند.
  3. برای گراف اسپارس (گراف خلوت) یعنی گرافی که دارای تعداد کمی یال هست زمان لازم O(n + e) است. البته به شرطی که $\mathrm{e\ <}\frac{{\mathrm{n}}^{\mathrm{2}}}{\mathrm{2}}$ باشد.

گراف اسپارس (گراف خلوت)

به گراف‌هایی که تعداد یال کمی داشته $\left(\mathrm{e\ \lt\lt}{\mathrm{n}}^{\mathrm{2}}/\mathrm{2}\right)$ و در نتیجه اکثر عناصر در ماتریس مجاورتی آنها صفر می‌باشد، گراف اسپارس با گراف خلوت گفته می‌شود. در این وضعیت می‌توانیم زمان لازم برای تست موقعیت‌ها در ماتریس مجاورتی را از زمان $\mathrm{O}\left({\mathrm{n}}^{\mathrm{2}}\right)=\mathrm{O}\left({\left|\mathrm{V}\right|}^{\mathrm{2}}\right)$ به کمک نمایش لیست مجاورتی (ترتیبی یا پیوندی) به زمان $\mathrm{O}\left(\mathrm{n\ +\ e}\right)=\mathrm{O}\left(\left|\mathrm{V}\right|+\left|\mathrm{E}\right|\right)$ کاهش دهیم.

توان k ام از ماتریس مجاورتی

در صورتی که A ماتریس مجاورتی گراف G باشد، آنگاه خانه [i , j] در ماتریس ${\mathrm{A}}^{\mathrm{k}}$، تعداد مسیرها به طول k از رأس i به رأس j را نشان می‌دهد.

لیست مجاورتی (Adjacent List)

با این نمایش، n سطر ماتریس مجاورتی در n لیست پیوندی قرار می‌گیرند. برای هر رأس مانند v از گراف G به عنوان Head، یک لیست وجود دارد و هر لیست، حاوی رئوس مجاور از آن رأس می‌باشد.

لیست مجاورتی گراف بدون جهت

در این وضعیت برای یک گراف با n رأس و e لبه (یال) برای نمایش لیست مجاورتی به n گره Head و 2e گره لیست احتیاج داریم.

گراف بدون جهت G لیست مجاورتی
این تصویر یک گراف غیر جهت دار را نشان می‌دهد. این تصویر لیست مجاورتی گراف بدون جهت را نشان می‌دهد.

دقت کنید که درجه هر گره (تعداد گره مجاور) در لیست مجاورتی گراف بدون جهت همان تعداد گره‌های لیست آن رأس می‌باشد.

اگر تعداد رئوس گراف G برابر با n باشد، تعداد کل لبه‌ها، در زمان $\mathrm{O}\left(\mathrm{n\ +\ e}\right)=\mathrm{O}\left(\left|\mathrm{V}\right|+\left|\mathrm{E}\right|\right)$ تعیین می‌شود.

لیست مجاورتی گراف جهت دار

در این وضعیت برای گراف جهت‌دار با n رأس و e لبه (یال) لیست مجاورتی احتیاج به n گره Head و e گره لیست دارد.

گراف جهت‌دار G لیست مجاورتی
این تصویر یک گراف جهت دار را نشان می‌دهد. این تصویر لیست مجاورتی گراف جهت را نشان می‌دهد.

دقت کنید که برای یک گراف جهت‌دار، درجه خروجی هر رأس با شمارش تعداد گره‌ها در لیست مجاورتی آن گره به دست می‌آید این بدین معناست که می‌توانیم تعداد کل خطوط یک گراف جهت‌دار را در زمان $\mathrm{O}\left(\mathrm{n\ +\ e}\right)=\mathrm{O}\left(\left|\mathrm{V}\right|+\left|\mathrm{E}\right|\right)$ تعیین کنیم.

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

در لیست مجاورتی به راحتی می‌توانیم درجه خروجی هر رأس را به دست آوریم که همان تعداد گره‌های لیست هر گره‌ی Head می‌باشد. برای پیدا کردن درجه‌ی ورودی به راحتی نمی‌توانیم عمل کنیم. چون باید تمام گره‌های Head را جستجو کنیم به غیر از گره‌ای که می‌خواهیم درجه‌ی ورودی آن را به دست آوریم. برای آن که به راحتی بتوانیم این کار را انجام دهیم می‌توانیم از لیست مجاورتی معکوس استفاده کنیم که در این وضعیت باز هم n گره Head داریم.

گراف جهت‌دار G لیست مجاورتی معکوس
این تصویر یک گراف جهت دار را نشان می‌دهد. این تصویر لیست مجاورتی معکوس گراف جهت دار را نشان می‌دهد.

دقت کنید که در هر لیست مجاورتی معکوس، تعداد گره‌های لیست درجه‌ی ورودی آن گره را نشان می‌دهند.

درخت پوشا (Spanning Tree)

یادآوری:

\[≤\frac{\mathrm{n}\left(\mathrm{n}\mathrm{-}\mathrm{1}\right)}{\mathrm{2}}\] تعداد یال‌ها (لبه‌های) گراف دلخواه با n رأس

\[\mathrm{\circ }\mathrm{\le }\]

این تصویر یک گراف کامل است.

گراف کامل

این تصویر یک گراف بدون لبه است.

گراف بدون لبه

\[≤\frac{\mathrm{n}\left(\mathrm{n}\mathrm{-}\mathrm{1}\right)}{\mathrm{2}}\] تعداد یال‌ها (لبه‌های) گراف متصل (همبند) با n رأس

\[\mathrm{n}\mathrm{-}\mathrm{1}\mathrm{\le }\]

این تصویر یک گراف کامل است.

گراف کامل

این تصویر یک درخت پوشا است.

درخت پوشا

هر گراف همبند (متصل) با حداقل لبه‌ی (1- n) را درخت پوشا (Spanning Tree) نامیده می‌شود. به عبارت بهتر:

  1. در صورتی که G یک گراف همبند با n رأس باشد، حداقل 1- n لبه دارد.
  2. درخت پوشا در گراف همبند، درختی است که n رأس گراف را داشته و دقیقاً 1- n لبه (یال) را اختیار می‌کند.

قضیه: برای گراف بدون جهت G با n رأس، موارد زیر یکسان و معادل هستند:

  1. G یک درخت می‌باشد.
  2. G همبند می‌باشد، اما اگر هر یک از لبه‌ها حذف گردد، گراف حاصل متصل نمی‌باشد. (هر یال، پل است.)
  3. برای هر رأس مجزا مانند $\mathrm{u\ }\mathrm{\in }\mathrm{\ V}\left(\mathrm{G}\right)$ و $\mathrm{v\ }\mathrm{\in }\mathrm{\ V}\left(\mathrm{G}\right)$ تنها یک مسیر ساده از u به v وجود دارد.
  4. G فاقد حلقه بوده و دارای 1- n لبه می‌باشد.
  5. اگر T یک درخت پوشا برای G باشد، آن‌گاه اضافه کردن یک لبه موجب ایجاد یک حلقه منحصر به فرد می‌گردد.

قضیه: در گراف کامل با n رأس، تعداد درختان پوشا برابر با ${\mathrm{n}}^{\mathrm{n}\mathrm{-}\mathrm{2}}$ است.

به‌طور مثال در گراف کامل با 3=n رأس تعداد ${\mathrm{n}}^{\mathrm{n}\mathrm{-}\mathrm{2}}\mathrm{=}{\mathrm{3}}^{\mathrm{3}\mathrm{-}\mathrm{2}}=\mathrm{3}$ درخت پوشا با 2 = 1- n لبه به صورت زیر وجود دارد:

گراف کامل با 3 = n درختان پوشا با 2 = 1- n لبه
این تصویر یک گراف کامل است. این تصویر درخت های پوشا که دارای ۲ لبه هستند را نشان می دهد.

مثال: در یک گراف کامل با 10 رأس چند یال را کم کنیم تا به درخت پوشا برسیم؟

  1. 45
  2. 36
  3. 9   
  4. 10

حل: گزینه 2 درست است.

تعداد یال‌های یک گراف کامل با n رأس (پیش‌فرض بدون جهت):

\[تعداد\mathrm{\ }یالها\mathrm{\ =\ }\frac{\mathrm{n}\left(\mathrm{n}\mathrm{-}\mathrm{1}\right)}{\mathrm{2}}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ تعداد\mathrm{\ }یالها\mathrm{\ =\ }\frac{\mathrm{10}\mathrm{\ \times \ }\mathrm{9}}{\mathrm{2}}=\mathrm{45}\]

10 = n

در یک درخت پوشا از یک گراف با n رأس 1- n یال وجود دارد، در نتیجه در گراف با 10 رأس درخت پوشا 9 یال دارد. بنابراین 36 = 9 - 45 یال باید کم شود.

قضیه: در یک گراف کامل با n رأس تعداد مسیرهای بین دو رأس مشخص برابر است با:

\[\sum^{\mathrm{n}\mathrm{-}\mathrm{2}}_{\mathrm{i\ =\ }\mathrm{\circ }}{\mathrm{i!}\left( \begin{array}{c} \mathrm{n}\mathrm{-}\mathrm{2} \\ \mathrm{i} \end{array} \right)}\]

یا به عبارت دیگر:

\[\sum^{\mathrm{n}\mathrm{-}\mathrm{2}}_{\mathrm{i\ =\ }\mathrm{\circ }}{{\mathrm{P}}^{\mathrm{n}\mathrm{-}\mathrm{i}\mathrm{-}\mathrm{1}}_{\mathrm{n}\mathrm{-}\mathrm{2}}}\]

قضیه: در گراف کامل با n رأس، تعداد مسیرها به طول r برابر است با:

\[\frac{\left(\mathrm{n}\mathrm{-}\mathrm{2}\right)!}{\left(\mathrm{n}\mathrm{-}\left(\mathrm{r\ +\ }\mathrm{1}\right)\right)\mathrm{!}}\mathrm{=}{\mathrm{P}}^{\mathrm{n}\mathrm{-}\left(\mathrm{r\ +\ }\mathrm{1}\right)}_{\mathrm{n}\mathrm{-}\mathrm{2}}\]

قضیه: در گراف کامل با n رأس، حداکثر تعداد مسیرهای بین رئوس برابر $\mathrm{O}\left(\left(\mathrm{n}\mathrm{-}\mathrm{1}\right)!\right)$

به‌طور مثال در گراف کامل روبه‌رو مسیرهای بین دو رأس 1 و 2 عبارتست از: path2: 2-3-1, path1: 1-2

این تصویر یک گراف کامل است.

 یعنی برای 3 = n رأس از این گراف کامل حداکثر $\mathrm{2}\mathrm{\ =}\left(\mathrm{3}\mathrm{-}\mathrm{1}\right)\mathrm{!}$ مسیر بین رئوس وجود دارد.

پیمایش گراف

پیمایش به این معناست که همه رئوس گراف را یکبار ملاقات کنیم. به‌طور کلی پیمایش گراف‌های همبند (متصل) منجر به تولید درخت پوشا (Spanning Tree) با n رأس و 1- n لبه می‌شود.

انواع پیمایش:

  • پیمایش سطحی (BFS) به کمک ساختار صف
  • پیمایش عمقی (DFS) به کمک ساختار پشته

مرتبه اجرایی پیمایش گراف

اگر گراف G توسط ماتریس مجاورتی ارائه شود، آنگاه زمان لازم برای پیمایش DFS یا BFS برابر با $\mathrm{O}\left({\mathrm{n}}^{\mathrm{2}}\right)=\mathrm{O}\left({\left|\mathrm{V}\right|}^{\mathrm{2}}\right)$ است.

 اگر گراف G توسط لیست مجاورتی ارائه شود، آنگاه زمان لازم برای پیمایش DFS یا BFS برابر با $\mathrm{O}\left(\mathrm{e}\right)=\mathrm{O}\left(\left|\mathrm{E}\right|\right)$ است.

دقت کنید از آنجایی که در هر گراف همبند، $\mathrm{n}\mathrm{-}\mathrm{1}\mathrm{\ }\mathrm{\le }\mathrm{\ e\ }\mathrm{\le }\mathrm{\ n}\left(\mathrm{n}\mathrm{-}\mathrm{1}\right)/\mathrm{2}$ است بنابراین تقریباً $\mathrm{e\ >\ n}$ بوده و میتوان O(e) = O(n + e) و $\mathrm{O}\left(\left|\mathrm{E}\right|\right)=\mathrm{O}\left(\left|\mathrm{E}\right|+\left|\mathrm{V}\right|\right)$ در نظر گرفت.

پیمایش سطح اول یا اول سطح (Breath First Search = BFS)

قاعده این نوع پیمایش گراف به صورت زیر است:

  1. رأس شروع را انتخاب کرده و ملاقات می‌کنیم (پیش‌فرض رأس 0)
  2. برای هر رأس ملاقات‌شده، تمام رئوس مجاور (همسایه) به آن را که تا به حال ملاقات نشده‌اند، ملاقات می‌کنیم.
  3. عملیات 2 را تا زمانی که همه رئوس یک‌بار ملاقات شوند ادامه می‌دهیم.

دقت کنید هرگاه برای یک رأس ملاقات‌شده هیچ همسایه‌ی ملاقات ‌نشده‌ای وجود نداشت، سراغ رأس ملاقات‌شده‌ی بعدی (در صف) رفته و عملیات 2 را برای آن انجام می‌دهیم.

درخت پوشای حاصل از پیمایش پیمایش $\mathrm{BFS}\left(\circ \right)$ گراف G
این تصویر درخت پوشای حاصل از پیمایش است. \[\mathrm{\circ }\mathrm{,\ }\mathrm{1}\mathrm{,\ }\mathrm{2}\mathrm{,\ }\mathrm{3}\mathrm{,\ }\mathrm{4}\mathrm{,\ }\mathrm{5}\mathrm{,\ }\mathrm{6}\mathrm{,\ }\mathrm{7}\] این تصویر یک گراف است.

مرتبه اجرایی BFS

اگر گراف G توسط ماتریس مجاورتی ارائه شود، آنگاه زمان لازم برای پیمایش BFS برابر با $\mathrm{O}\left({\mathrm{n}}^{\mathrm{2}}\right)=\mathrm{O}\left({\left|\mathrm{V}\right|}^{\mathrm{2}}\right)$ است.

اگر گراف G توسط لیست مجاورتی ارائه شود، آنگاه زمان لازم برای پیمایش BFS برابر با $\mathrm{O}\left(\mathrm{e}\right)=\mathrm{O}\left(\left|\mathrm{E}\right|\right)$ است. 

دقت کنید از آنجایی که در هر گراف متصل $\mathrm{n}\mathrm{-}\mathrm{1}\mathrm{\ }\mathrm{\le }\mathrm{\ e\ }\mathrm{\le }\mathrm{\ n}\left(\mathrm{n}\mathrm{-}\mathrm{1}\right)/\mathrm{2}$ است بنابراین تقریباً $\mathrm{e\ >\ n}$ بوده و می‌توان O(e) = O(n + e) و $\mathrm{O}\left(\left|\mathrm{E}\right|\right)=\mathrm{O}\left(\left|\mathrm{E}\right|+\left|\mathrm{V}\right|\right)$ در نظر گرفت.

مثال: ترتیب ملاقات گره‌ها در پیمایش ردیفی (BFS) در گراف روبه‌رو از چپ به راست کدام است؟

  1. 0-1-3-2-4-5-6-7-8-9
  2. 0-1-3-2-4-5-7-6-8-9
  3. 0-1-2-3-4-5-6-7-8-9
  4. 0-1-3-2-4-5-7-6-9-8

این تصویر یک گراف است.

حل: گزینه 3 درست است.

مثال: لیست مجاورتی مربوط به گراف G به صورت زیر است. پیمایش سطحی این گراف کدام است؟

  1. A B D C F E
  2. A B C D E F
  3. A C F D E B
  4. A D C B E F
Adjacent list
A : B,C,D
B : A,D,E
C : A,D,F
D : A,B,C
E : B,F
F : C,E

حل: گزینه 2 درست است.

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

procedure  BFS (v)

begin

        visit   v;

1. AddQueue (Queue , v)

         while   queue is not empty   do

          begin

2. DeleteQueue (Queue , v)

             for all vertices w adjacent   to   v   do

                  if   w is not visited   then

                  begin

3. AddQueue (Queue , v)

                         visit   w

                    end;

        end;

end;

پیمایش عمق اول یا اول عمق (Depth First Search = DFS)

قاعده این نوع پیمایش گراف به صورت زیر است:

  1. رأس شروع را انتخاب کرده و ملاقات می‌کنیم (پیش‌فرض رأس )
  2. برای هر رأس ملاقات‌شده، اولین رأس مجاور (همسایه) به آن را که تا به حال ملاقات نشده، ملاقات می‌کنیم.
  3. عملیات 2 را تا زمانی که همه رئوس یک‌بار ملاقات شوند ادامه می‌دهیم.

دقت کنید هرگاه برای یک رأس ملاقات‌شده هیچ همسایه‌ی ملاقات نشده‌ای وجود نداشت، سراغ رأس ملاقات شده‌ی قبلی (در پشته) رفته و عملیات 2 را برای آن انجام می‌دهیم.

درخت پوشای حاصل از پیمایش پیمایش $\mathrm{DFS}\left(\circ \right)$ گراف G
این تصویر درخت پوشای حاصل از پیمایش است. \[\mathrm{\circ },\mathrm{1}\mathrm{,\ }\mathrm{3}\mathrm{,\ }\mathrm{7}\mathrm{,\ }\mathrm{4}\mathrm{,\ }\mathrm{5}\mathrm{,\ }\mathrm{2},\mathrm{6}\] این تصویر یک گراف است.

مرتبه اجرایی DFS

اگر گراف G توسط ماتریس مجاورتی ارائه شود، آنگاه زمان لازم برای پیمایش DFS برابر با $\mathrm{O}\left({\mathrm{n}}^{\mathrm{2}}\right)=\mathrm{O}\left({\left|\mathrm{V}\right|}^{\mathrm{2}}\right)$ است.

اگر گراف G توسط لیست مجاورتی ارائه شود، آنگاه زمان لازم برای پیمایش DFS برابر با $\mathrm{O}\left(\mathrm{e}\right)=\mathrm{O}\left(\left|\mathrm{E}\right|\right)$ است.

دقت کنید از آنجایی که در هر گراف متصل $\mathrm{n}\mathrm{-}\mathrm{1}\mathrm{\ }\mathrm{\le }\mathrm{\ e\ }\mathrm{\le }\mathrm{\ n}\left(\mathrm{n}\mathrm{-}\mathrm{1}\right)/\mathrm{2}$ است بنابراین تقریباً $\mathrm{e\ >\ n}$ بوده و می‌توان O(e) = O(n + e) و $\mathrm{O}\left(\left|\mathrm{E}\right|\right)=\mathrm{O}\left(\left|\mathrm{E}\right|+\left|\mathrm{V}\right|\right)$ در نظر گرفت.

مثال: ترتیب ملاقات گره‌ها در پیمایش عمقی (DFS) در گراف روبه‌رو از چپ به راست کدام است؟

  1. 0-1-2-3-4-5-6-7-8-9
  2. 0-1-2-4-3-5-6-7-8-9
  3. 0-1-2-3-4-5-6-7-9-8
  4. 0-1-3-2-4-5-7-6-8-9

این تصویر یک گراف است.

مثال: لیست مجاورتی مربوط به گراف G به صورت زیر است. پیمایش عمقی (DFS) این گراف کدام است؟

  1. A B D C F E
  2. A B C D E F
  3. A C F D E B
  4. A D C B E F
Adjacent list
A : B,C,D
B : A,D,E
C : A,D,F
D : A,B,C
E : B,F
F : C,E

حل: گزینه 1 درست است.

مثال: در جستجوی عمق اول (DFS) گراف جهت‌دار زیر فرض کنید که گره 1، گره شروع باشد و گره‌های مجاور یک گره به ترتیب مقدار عددی‌شان ملاقات می‌شوند. کدام گزینه ترتیب گره‌های ملاقات‌شده را نشان می‌دهد؟ (از چپ به راست)

  1. 1-2-3-4-11-5-6-7-10-8-9
  2. 1-2-8-5-3-9-6-4-11-10-7
  3. 1-2-5-8-3-9-6-4-10-7-11
  4. 1-2-3-4-5-6-7-8-9-10-11

این تصویر یک گراف جهت دار است.

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

غیربازگشتی:

1.initialize all nodes to the ready state (status = 1)

2. push the starting node A onto STACK and change its status to the waiting state (STATUS = 2)

3. Repeat steps 4 and 5 until STACK is empty

4. Pop the top node N of STACK. Process its status to the processed state (STATUS = 3)

5. Push on to STACK all the neighbors of N that are still in the ready state (STATUS = 1), and change their status to the waiting state (STATUS = 2).

[ End of step 3 Loop ]

6. Exit

بازگشتی:

procedure dfs (v : vertex);

w : vertex;

begin

       mark v as "visited";

       for all vertices w adjacent to v do

            if   w is not "visited"   then   dfs (w);

end;

گراف همبند و پیمایش‌ BFS و DFS 

اگر گراف G توسط ماتریس مجاورتی ارائه شود، آنگاه زمان لازم برای تعیین گراف‌های متصل با استفاده از پیمایش‌های عمقی و سطحی برابر با $\mathrm{O}\left({\mathrm{n}}^{\mathrm{2}}\right)=\mathrm{O}\left({\left|\mathrm{V}\right|}^{\mathrm{2}}\right)$ است.

اگر گراف G توسط لیست مجاورتی ارائه شود، آنگاه زمان لازم برای تعیین گراف‌های متصل با استفاده از پیمایش‌های عمقی و سطحی برابر با $\mathrm{O}\left(\mathrm{n\ +\ e}\right)=\mathrm{O}\left(\left|\mathrm{V}\right|+\left|\mathrm{E}\right|\right)$ می‌باشد.

گراف برچسب دار (Labeled Graph)

گراف G برچسب‌دار یا گراف وزن دار یا گراف شماره دار می‌گویند اگر اطلاعاتی به یال‌های آن نسبت داده شود. اگر اطلاع نسبت داده شده به یال‌ها یک عدد غیرمنفی باشد به آن وزن یال یا هزینه یال می‌گویند.

در این تصویر یک گراف برچسب دار نشان داده شده است.

درخت پوشای کمینه (MST: Minimum Spanning Tree)

اساساً گرافی که در آن یال‌ها وزن داشته باشند گراف وزن دار نامیده می‌شود.

این تصویر یک درخت پوشای کمینه  است.

پیمایش‌های هر گراف وزندار منجر به تولید درختان پوشا با 1- n لبه و با هزینه‌های متفاوت می‌شود. برای به دست آوردن درخت پوشایی که مجموع هزینه یال‌ها (اضلاع) آن مینیمم باشد بایستی از الگوریتم‌های خاصی استفاده کنیم.

در تمام الگوریتم‌ها برای درخت‌های پوشا، از ملاک یا معیار کم‌ترین هزینه استفاده می‌کنیم، روش ما باید دارای شرایط زیر باشد:

  1. باید فقط از لبه‌های داخل گراف استفاده کنیم.
  2. باید دقیقاً از 1- n لبه استفاده کنیم.
  3. نباید از لبه‌هایی که ایجاد یک حلقه می‌کنند، استفاده کنیم.

الگوریتم راشال (کراسکال = Kruskal)

در این روش، درخت پوشای مینیمم (T)، لبه به لبه ساخته می‌شود تا دقیقاً 1- n یال برای انتخاب شود. در هر مرحله یالی را انتخاب می‌کنیم که اولاً کم‌ترین هزینه را داشته باشد ثانیاً با لبه‌های انتخاب شده در مراحل قبل حلقه ایجاد نکند، (به عبارت بهتر لبه‌های مورد استفاده در T، به ترتیب صعودی وزن‌ها می‌باشد و یک لبه در T خواهد بود، اگر با لبه‌های قبل که در T بوده‌اند، تشکیل یک حلقه ندهد)

دقت کنید:

1. در هر مرحله از الگوریتم کراسکال ممکن است یک جنگل داشته باشیم.

2. در پایان کار یک درخت پوشا با هزینه مینیمم وجود دارد.

3. اگر G یک گراف همبند بدون جهت باشد، الگوریتم راشال یک درخت پوشای حداقل را ایجاد می‌کند.

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

مراحل الگوریتم کراسکال را برای گراف زیر جلو می‌بریم.

 این تصویر یک گراف غیر جهت دار را نشان می‌دهد.

 

(1) (2) (3)

مرحله اول الگوریتم کراسکال در این تصویر نشان داده شده است.

مرحله دوم الگوریتم کراسکال در این تصویر نشان داده شده است.

مرحله سوم الگوریتم کراسکال در این تصویر نشان داده شده است.

(4) (5) (6)

مرحله چهارم الگوریتم کراسکال در این تصویر نشان داده شده است.

مرحله پنجم الگوریتم کراسکال در این تصویر نشان داده شده است.

مرحله ششم الگوریتم کراسکال در این تصویر نشان داده شده است.

شبه کد الگوریتم کراسکال

T = {};

While (T contains less than n-1 edges & & E is not empty) {

       choose a least cost edge (v , w) from E;

       delete (v , w) from E;

        if ((v , w) does not create a cycle in T)

              add (v , w) to T;

       else

               discard (v , w);

}

if (T contains fewer n-1 edges)

      printf  ("No spanning tree \ n");

در آغاز، E مجموعه‌ای از تمام لبه‌ها در G است. تنها اعمالی که می‌خواهیم روی این مجموعه انجام دهیم، عبارتند از:

  1. تعیین یک لبه با کم‌ترین هزینه
  2. حذف آن لبه

هر دو مورد را می‌توان به شرطی که خطوط موجود در E به عنوان یک لیست ترتیبی مرتب شده باشد، انجام داد. لبه‌های موجود در E در زمان O(e log e) مرتب می‌شوند. مسلماً، همه‌ی لبه‌ها در E الزاماً نباید مرتب شوند و ما قادر هستیم لبه بعدی با حداقل هزینه را به سادگی تعیین کنیم. به نظر می‌رسد که مرتب‌سازی heap روش مناسبی برای مرتب کردن باشد که در این صورت لبه بعدی در زمان O(log e) تعیین و حذف می‌گردد. انجام عمل مرتب‌سازی heap به تنهایی به زمانی برابر با O(e) نیاز دارد.

مرتبه اجرایی: الگوریتم راشال را در زمانی برابر با O(e log e) پیاده‌سازی می‌کنیم به نحوی که e تعداد لبه‌ها در G می‌باشد.

مثال: هزینه درخت پوشا با کم‌ترین هزینه در گراف زیر کدام است؟

  1. 12
  2. 15
  3. 16
  4. 22

در این تصویر یک گراف برچسب دار نشان داده شده است.

حل: گزینه 2 درست است.

\[\mathrm{cost\ of\ min\ spanning\ tree\ =\ }\mathrm{1}\mathrm{\ +\ }\mathrm{2}\mathrm{\ +\ }\mathrm{3}\mathrm{\ +\ }\mathrm{3}\mathrm{\ +\ }\mathrm{6}\mathrm{\ =\ }\mathrm{15}\]

این تصویر یک گراف است.

الگوریتم پریم (Prim)

الگوریتم پریم با یک درخت مانند T، که تنها شامل یک رأس است، شروع می‌کند. این رأس می‌تواند هر یک از رئوس در گراف اصلی باشد. سپس، یک لبه با کم‌ترین هزینه به گونه‌ای انتخاب می‌شود که اولاً یکی از رئوسش در درخت T باشد ثانیاً هزینه آن مینیمم باشد این عمل را تا زمانی که T شامل 1- n لبه باشد، ادامه می‌دهیم.

برای اطمینان از این که لبه‌های اضافه شده تشکیل یک حلقه یا سیکل نمی‌دهند، در هر مرحله لبه‌ای مانند (u , v) با هزینه مینیمم را به گونه‌ای انتخاب می‌کنیم که دقیقاً یکی از رئوس u یا v در T وجود داشته باشد. دقت کنید در هر مرحله از الگوریتم پریم حتماً یک درخت وجود دارد.

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

در شروع کار درخت T با رأس $\mathrm{\circ }$ شروع میشود.

این تصویر یک گراف غیر جهت دار را نشان می‌دهد.

(1) (2) (3)

مرحله اول الگوریتم پریم در این تصویر نشان داده شده است.

مرحله دوم الگوریتم پریم در این تصویر نشان داده شده است.

مرحله سوم الگوریتم پریم در این تصویر نشان داده شده است.

(4) (5) (6)

مرحله چهارم الگوریتم پریم در این تصویر نشان داده شده است.

مرحله پنجم الگوریتم پریم در این تصویر نشان داده شده است.

مرحله ششم الگوریتم پریم در این تصویر نشان داده شده است.

مرحله 1: لبه $\left(\mathrm{5}\mathrm{\ ,\ }\mathrm{\circ }\right)$ بهگونهای انتخاب شده که اولاً یک رأس آن $\left(\mathrm{\circ }\right)$ در T بوده و ثانیاً هزینه آن مینیمم است.

مرحله 2: ...

شبیه کد الگوریتم پریم

T = {};

TV = {0}; /*start with vertex 0 and no edges*/

While (T contains fewer than n-1 edges){

     let (u , v) be a least cost edge such that u   TV  and

      v   TV;

     if (there is no such edge)

               break;

     add  v  to TV;

     add (u , v) to T;

}

if (T contains fewer n-1 edges)

printf ("No spanning tree \ n");

الگوریتم پرایم را در زمانی برابر با $\mathrm{O}\left({\mathrm{n}}^{\mathrm{2}}\right)$ پیاده‌سازی می‌کنیم به نحوی که n تعداد رئوس در G میباشد.

الگوریتم سالین (Sollin)

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

مراحل الگوریتم سالین

این تصویر یک گراف غیر جهت دار را نشان می‌دهد.

(1) (2)

مرحله اول الگوریتم سالین در این تصویر نشان داده شده است.

مرحله دوم الگوریتم سالین در این تصویر نشان داده شده است.

همواره هزینه مینیمم درخت پوشا به دست آمده در تمام الگوریتم‌ها یکسان است. اما درخت پوشای به دست آمده از همه روش‌ها یکسان نیست مگر آن که:

1- یال با لبه تکراری نداشته باشیم       یا        2- گراف در ابتدا یک درخت پوشا 1- n لبه باشد.

گراف در کامپیوتر چیست؟

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

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

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

همچنین هر گونه سوالی در مورد کلاس‌های آنلاین کنکور کامپیوتر و یا تهیه فیلم‌ها و یا رزرو مشاوره تک جلسه‌ای تلفنی با استاد رضوی دارید می‌توانید به طرق زیر از تیم پشتیبانی بپرسید:

آی دی تلگرام تیم پشتیبانی:     konkurcomputer_admin@

تماس با پشتیبانی:   09378555200

امتیازدهی5 1 1 1 1 1 1 1 1 1 15.00 امتیاز (6 رای)
بارگذاری نظرات