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

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

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

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

توجه :

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

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

در ادامه به آموزش گراف که از فصول مهم ریاضیات گسستهجامع ترین آموزش درس ریاضی گسستهدرس ریاضیات گسسته به معرفی مباحثی نظیر شمارش و احتمال، استدلال و برهان خلف، نظریه اعداد، منطق ریاضی، روابط بازگشتی، روابط و نظریه‌ گراف می‌پردازد. از آن رو که در عصر کنونی ریاضی گسسته بطور گسترده‌ در رشته کامپیوتر و برنامه نویسی استفاده می‌شود در این صفحه به معرفی و بررسی درس ریاضی گسسته پرداخته شده است، ساختمان دادهآموزش ساختمان داده و الگوریتمهر ساختمان داده یک نوع فرمت ذخیره‌سازی و مدیریت داده‌ها در کامپیوتر است، که امکان دسترسی و اصلاح کارآمد آن داده‌ها را برای یکسری از الگوریتم‌ها و کاربردها فراهم می‌کند، در این صفحه به بررسی و آموزش ساختمان داده و الگوریتم پرداخته شده است و طراحی الگوریتمآموزش طراحی الگوریتم به زبان سادهدرس طراحی الگوریتم‌ یکی از مهم‌ترین و بنیادیترین دروس‌ رشته کامپیوتر است. هدف از این درس، معرفی روش‌های مختلف طراحی الگوریتم‌ها برای حل مسائل گوناگون است، در این صفحه به معرفی و آموزش طراحی الگوریتم پرداخته شده است. بشمار می‌رود می‌پردازیم. در مقاله‌ی نظریه گرافهمه چیز در مورد نظریه گراف (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 مدل گراف داریم که در این مقاله به شرح دو مورد از آن‌ها می‌پردازیم.

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

گراف بدون جهت

در یک گراف بدون جهت هر لبه (یال، ضلع) به صورت $\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 را در یک گراف مجاور (همسایه) گوییم هرگاه لبه مستقیمی بین آن‌ها وجود داشته باشد. به عبارت بهتر:

در گراف بدون جهت : دو گره V , U مجاور (همسایه) هستند هرگاه لبه {U , V} وجود داشته باشد.
در گراف جهت‌دار: هرگاه لبه $\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 رأس
\[\text{تعداد}\mathrm{\ }\text{لبه‌ها}\mathrm{\ =\ n}\left(\mathrm{n}\mathrm{-}\mathrm{1}\right)\]	\[\text{تعداد}\mathrm{\ }\text{لبه‌ها}\mathrm{\ =\ }\frac{\mathrm{n}\left(\mathrm{n}\mathrm{-}\mathrm{1}\right)}{\mathrm{2}}\]

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

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

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

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

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

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

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

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

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

(cycle) 1-3-1

(cycle) 3-1-3

2-3-1

2-1-3

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

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

(cycle) 1-3-2-1

(cycle) 2-1-3-2

(cycle) 3-2-1-3

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

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

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

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

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

path: v, …, v

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

v₁-v₂-v₁
v₁-v₂-v₄-v₁
v₁-v₂-v₃-v₁
v₁-v₂-v₃-v₄-v₁

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

در گراف بدون جهت دو رأس دلخواه ${\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
G₁ یک مؤلفه از گراف G است.
G₁ , G₂ دو مؤلفه از گراف G هستند.
G₁ , G₂ , G₃ سه مؤلفه از گراف 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
G₁ , G₂ , G₃ سه مؤلفه کاملاً متصل (قوی) از گراف G هستند.
G₁ , G₂ دو مؤلفه کاملاً متصل (قوی) از گراف G هستند.
G₁ یک مؤلفه کاملاً متصل (قوی) از گراف 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

گراف منتظم

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

گراف اویلری

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

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

گذر اویلری

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

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

مدار اویلری

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

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

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

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

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

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

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

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

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

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

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

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

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

یادآوری: می‌دانیم که در یک گراف دلخواه با n راس تعداد یال‌های آن بزرگتر مساوی 0 و کوچکتر مساوی $\frac{\mathrm{n}\left(\mathrm{n}\mathrm{-}\mathrm{1}\right)}{\mathrm{2}}$ است که این حالت که یال‌ها ماکزیمم است برای زمانی اتفاق می‌افتد که همه یال‌های گراف رسم شده باشد و در واقع گراف کامل باشد. حال اگر گراف اولیه همبند باشد آنگاه حداکثر تعداد یال با حالت قبلی فرقی نمی‌کند اما حداقل تعداد یال برابر با n-1 است، در واقع یک گراف با n راس باید حداقل n-1 یال داشته باشد تا همبند باشد اگر نه همبند نخواهد بود. برای درک بیشتر شما خوانندگان عزیز این نکات در عکس‌های زیر نیز آورده شده است.

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

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

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

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

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

G یک درخت می‌باشد.
G همبند می‌باشد، اما اگر هر یک از لبه‌ها حذف گردد، گراف حاصل متصل نمی‌باشد. (هر یال، پل است.)
برای هر رأس مجزا مانند $\mathrm{u\ }\mathrm{\in }\mathrm{\ V}\left(\mathrm{G}\right)$ و $\mathrm{v\ }\mathrm{\in }\mathrm{\ V}\left(\mathrm{G}\right)$ تنها یک مسیر ساده از u به v وجود دارد.
G فاقد حلقه بوده و دارای 1- n لبه می‌باشد.
اگر 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 رأس چند یال را کم کنیم تا به درخت پوشا برسیم؟

حل: گزینه 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{!}$ مسیر بین رئوس وجود دارد.

گراف مسطح (Planar)

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

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

ناحیه: به سطوحی از صفحه که توسط یال‌های گراف مسطح از یکدیگر کاملاً جدا شده‌اند. تعداد نواحی را معمولا با r نمایش می‌دهند.
درجه هر ناحیه: برای هر ناحیه درجه تعریف می‌شود و تعداد یال‌های مرزی هر ناحیه را درجه آن ناحیه می‌گویند.

مثال: گراف زیر را در نظر بگیرید. آیا این گراف مسطح است؟ در صورت مسطح بودن این گراف، چه تعداد ناحیه، گره و یال وجود دارد؟

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

این گراف دارای 8 گره، 12 یال و 6 ناحیه به شرح زیر است.

مثال: آیا $K_{5}$ مسطح است؟

n = 5, e = 10 \overset{}{⟶} 10 \leq 3 ⨯ 5 - 6 \overset{}{⟶} 10 \leq 9

در نتیجه $K_{5}$ مسطح نیست.

مثال: آیا $K_{3,3}$ مسطح است؟

n = 6, e = 9 \overset{}{⟶} 9 \leq 3 ⨯ 6 - 6 \overset{}{⟶} 9 \leq 12

با این قضیه نتوانستیم نشان دهیم که $K_{3,3}$ مسطح نیست!

قضیه: در گراف‌های همبند، ساده و مسطح که است و سیکل به طول 3 ندارد آنگاه $e \leq 2n - 4$

وقتی در یک گراف همبند و ساده، سیکل به طول 3 نداریم یعنی $\deg (R_{i}) \geq 4$

در نتیجه:

\deg (R_{i}) \geq 4 \overset{}{⟶} \sum \deg (R_{i}) \geq 4 r \overset{}{⟶} 2 e \geq 4 (e - n + 2)

2 e ≥ 4 e − 4 n + 8 ⟶ 2 e ≤ 4 n − 8 ⟶ e ≤ 2 n − 4

مثال: آیا $K_{3,3}$ مسطح است؟

n = 6, e = 9 \overset{}{⟶} 9 \leq 2 ⨯ 6 - 4 \overset{}{⟶} 9 \leq 8

در نتیجه $K_{3,3}$ مسطح نیست.

نکته: می‌دانستیم که گراف‌های دو بخشی، سیکل به طول فرد ندارند، بنابراین کوچکترین سیکل آن‌ها بزرگتر مساوی 4 است. از این رو می‌توان نتیجه گرفت که در گراف‌های دو بخشی $e \leq 2n - 4$

تقسیم مبنا در گراف

مفهوم تقسیم مبنا در گراف بدین معناست که وسط یک یال در گراف یک راس قرار دهیم. در مثال زیر با قرار دادن گره‌های x1 و x2 (تقسیم مبنا) یک گراف یا تعداد راس 3 را به یک گراف با تعداد راس 5 تبدیل کردیم.

نکته مهم در خصوص تقسیم مبنا این است که عملیات تقسیم مبنا باعث تغییر درجات رئوس نمی‌شود. تنها تعدادی راس درجه 2 به گراف اضافه می‌کند.

در ادامه پس از بیان توضیحاتی در خصوص تقسیم مبنا در گراف، به تعریف 2 مفهوم مهم می‌پردازیم:

ایزومورف یا یکریخت: اگر دو گراف از نظر تمام خواص یکسان باشند می‌گوییم این دو گراف، ایزومورف هستند.
همومورفیک یا همریخت: اگر 2 گراف داشته باشیم و بتوانیم با تقسیم مبنا از یکی از گراف‌ها به دیگری رسید می‌گوییم آن دو گراف، همومورفیک هستند.

حال با بیان مفاهیم فوق قضیه مهمی را در خصوص تشخیص مسطح نبودن یک گراف بیان می‌کنیم:

قضیه‌ی کورتافسکی: گراف G مسطح نیست اگر و تنها اگر دارای زیر گرافی باشد همریخت با $K_{5}$ و $K_{3,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 برابر تعداد یال‌ها (لبه‌ها) می‌باشد.
مجموع عناصر سطری یا ستونی برای هر رأس درجه آن را نشان می‌دهد.

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

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

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

مجموع عناصر ستونی هر رأس = درجه ورودی رأس (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) گرافی است که در آن هیچ سیکلی وجود ندارد.

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

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

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

(i , j) is adj

else

(i , j) is not adj
اغلب الگوریتم‌ها با استفاده از ماتریس مجاورتی با زمان $\mathrm{O}\left({\mathrm{n}}^{\mathrm{2}}\right)=\mathrm{O}\left({\left|\mathrm{V}\right|}^{\mathrm{2}}\right)$ به دست می‌آیند.
برای گراف اسپارس (گراف خلوت) یعنی گرافی که دارای تعداد کمی یال هست زمان لازم 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) با 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)

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

رأس شروع را انتخاب کرده و ملاقات می‌کنیم (پیش‌فرض رأس 0)
برای هر رأس ملاقات‌شده، تمام رئوس مجاور (همسایه) به آن را که تا به حال ملاقات نشده‌اند، ملاقات می‌کنیم.
عملیات 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) در گراف روبه‌رو از چپ به راست کدام است؟

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

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

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

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

A B D C F E
A B C D E F
A C F D E B
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;

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

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

رأس شروع را انتخاب کرده و ملاقات می‌کنیم (پیش‌فرض رأس )
برای هر رأس ملاقات‌شده، اولین رأس مجاور (همسایه) به آن را که تا به حال ملاقات نشده، ملاقات می‌کنیم.
عملیات 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) در گراف روبه‌رو از چپ به راست کدام است؟

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

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

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

A B D C F E
A B C D E F
A C F D E B
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-2-3-4-11-5-6-7-10-8-9
1-2-8-5-3-9-6-4-11-10-7
1-2-5-8-3-9-6-4-10-7-11
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- n لبه استفاده کنیم.
نباید از لبه‌هایی که ایجاد یک حلقه می‌کنند، استفاده کنیم.

الگوریتم راشال (کراسکال = 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 است. تنها اعمالی که می‌خواهیم روی این مجموعه انجام دهیم، عبارتند از:

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

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

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

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

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

حل: گزینه 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 و ... اشاره کرد.