تعاریف¶

تعریف 3.1.1 (گراف جهت دار)¶

فرض کنید تعدادی شهر داریم که توسط جاده هایی به هم متصل هستند و شما در شهر D هستید و می‌خواهید به شهر A بروید(شکل ۱). برای رسیدن به شهر A باید از تعدادی جاده عبور کنیم ولی از آنجا که جاده‌ها می‌توانند یک‌طرفه باشند، به گرافی نیاز داریم که جهت هر جاده را به ما نشان دهد که به آن گراف جهت دار گوییم(شکل ۲).

به بیان دقیق تر، گراف جهت دار \(G\) یک زوج مرتب \((V, E)\) است که \(V\) مجموعه راس های گراف است. همچنین \(E\) یک مجموعه شامل زوج مرتب هایی به فرم \((u, v)\) است به این معنا که یک یال جهت دار از \(u\) به \(v\) در گراف وجود دارد.

به گراف جهت دار \(G\) ساده می‌گوییم اگر شامل یال های جهت دار چند گانه و طوقه نباشد. البته توجه داشته باشید که ممکن است \(G\) ساده باشد و \(E\) شامل \((u, v)\) و \((v, u)\) باشد، ولی نمی‌تواند ۲ تا از زوج مرتب \((u, v)\) را داشته باشد.

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

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

در یک گراف جهت دار، هر راس یک درجه ورودی و یک درجه خروجی دارد. برای مثال در شکل۲، درجه ورودی راس D برابر با ۳ و درجه خروجی آن برابر با ۱ است!

درجه ورودی راس \(v\) را با نماد \(d^{−}(v)\) یا \(deg^{−}(v)\) و درجه خروجی را با \(d^{+}(v)\) یا \(deg^{+}(v)\) نمایش می‌دهیم.

منظور از \(\delta^{+}, \delta^{-}\) به ترتیب مینیمم درجه ورودی و مینیمم درجه خروجی است.

به طور مشابه منظور از \(\Delta^{+}, \Delta^{-}\) به ترتیب ماکسیمم درجه ورودی و ماکسیمم درجه خروجی است.

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

مشابه گراف های ساده، در گراف های جهت دار هم تعاریفی مانند گشت، گشت بسته، گذر، دور و مسیر داریم. برای مثال در شکل۲، یک مسیر جهت دار می‌تواند مسیری به شکل (D -> C -> B -> A) باشد که راس شروع همان مبدا سفر(D) و راس پایان همان مقصد سفر(A) می‌باشد. دقت کنید در طی کردن یال ها، باید جهت یال رعایت شود. برای مثال هنگامی که در راس D هستیم، نمی‌توانیم به راس A به صورت مستقیم برویم!

همچنین یک دور در شکل۲ می‌تواند به صورت (D -> C -> B -> D) باشد. بدیهتا در هنگام طی کردن دور، باید جهت یال ها رعایت شود.

به طور مشابه، طول هر کدام از تعاریف بالا، برابر با تعداد یال های آن است.

به بیان دقیق تر :

گشت : دنباله \(v_{1}, v_{2}, ..., v_{l}\) یک گشت در گراف جهت دار \(G\) است، اگر به ازای هر \(1 \leq i < l\) یال \((v_{i}, v_{i+1})\) در \(G\) باشد(به عبارتی یال فوق متعلق به مجموعه \(E\) باشد) .

گشت بسته : اگر در دنباله ای که تعریف کردیم، \(v_{1} = v_{l}\) باشد، به این گشت یک گشت بسته گوییم.

گذر : اگر در دنباله ای که تعریف کردیم، هیچ یال تکراری نباشد، به این گشت یک گذر گوییم.

مسیر : اگر در دنباله ای که تعریف کردیم، هیچ راس تکراری نباشد(و در نتیجه یال تکراری هم نباشد)، گشت حاصل یک مسیر است.

دور : در آخر اگر در یک مسیر، راس شروع و پایان یکسان باشند( \(v_{1} = v_{l}\) ) به گشت حاصل یه دور گوییم.

دقت کنید که تعاریف بالا دقیقا مانند تعاریف در گراف ساده هستند با این تفاوت که در گراف جهت دار باید جهت یال ها درست طی شوند!

قضایا و لم های مورد استفاده در این بخش¶

چند تعریف دیگر¶

گراف زمینه : اگر یال های یک گراف جهت دار را بی جهت کنیم، آنگاه به گراف به دست آمده گراف زمینه گوییم. برای مثال شکل۱ یک گراف زمینه برای شکل۲ است.