گراف جهت‌دار کیست؟ توضیح بده.
در ریاضیات و به‌طور خاص در نظریهٔ گراف، گراف جهت‌دار یا گراف سودار گرافی (مجموعه‌ای از گره‌ها که با یال‌ها به هم متصل شده‌اند) است که در آن به هر یال جهتی نسبت داده شده‌است. به زبان ریاضی، یک گراف جهت‌دار زوج مرتبی به صورت formula_1 است (گاهی به صورت formula_2 نیز نمایش داده می‌شود) که در آنگراف جهت دار با گراف معمولی عمده تفاوتشان در تعاریف یال هاست. یعنی زوج مرتب (a,b) با زوج مرتب (b ,a) تفاوتی در گراف معمولی یا بدون جهت ندارد و در حالت کلی تر آن را به شکل ab می نویسیم ولی در گراف جهت دار زوج مرتب های (a,b) با (b,a) تفاوت دارد و نشان دهنده سوی یال است و نشان دهنده ی نحوه ی ارتباط بین این دو راس می باشد.یک گراف جهت‌دار ساده نامیده می‌شود اگر هیچ طوقه و یال چندگانه‌ای نداشته باشد (یال‌های چندگانه یعنی یال‌هایی که ابتدا و انتهای یکسانی دارند). در یک گراف چندگانهٔ جهت‌دار یال‌ها تشکیل یک مجموعهٔ چندگانه (به جای مجموعه) از زوج‌های مرتب رأس‌ها می‌دهند و این گراف‌ها می‌توانند طوقه و یال چندگانه داشته باشند (طوقه یالی است که ابتدا و انتهایش رأس یکسانی است). در برخی متون، گراف جهت‌دار (بدون ذکر ویژگی ساده بودن) می‌تواند طوقه، یال چندگانه یا هر دو را داشته باشد.اصطلاحات پایه‌ای.یال formula_3 دارای جهت از formula_4 به formula_5 در نظر گرفته می‌شود. formula_5 ابتدا و formula_4 انتهای یال نامیده می‌شود. formula_5 را رأس مابعد مستقیم formula_4 و formula_4 را رأس ماقبل مستقیم formula_5 می‌نامند. اگر مسیری متشکل از یک یا چند یال رو به جلو از formula_4 به formula_5 وجود داشته باشد، به formula_5 رأس مابعد formula_4 و به formula_4 رأس ماقبل formula_5 می‌گویند. به یال formula_18 معکوس یال formula_19 می‌گویند.جهت‌دار کردن یک گراف سادهٔ بدون جهت یعنی نسبت دادن جهت به هر یال آن گراف. هر گراف جهت‌داری که به این طریق ساخته شود گراف جهت‌دار شده نامیده می‌شود. یک گراف جهت‌دار، یک گراف سادهٔ جهت‌دار شده‌است اگر و تنها اگر نه طوقه داشته باشد و نه حلقهٔ دوتایی (یال چندگانه). گراف جهت‌دار وزن‌دار گراف جهت‌داری است که به هر یالش وزنی نسبت داده شده‌است، درست مانند گراف بدون جهت وزن‌دار. در نظریهٔ گراف به گراف جهت‌دار با یال‌های وزن‌دار، شبکه می‌گویند.ماتریس مجاورت یک گراف جهت‌دار (با طوقه و یال‌های چندگانه) ماتریسی دارای مقادیر صحیح است که سطرها و ستون‌هایش متناظر با گره‌ها هستند و در آن، مؤلفهٔ غیر قطری formula_20 تعداد یال‌ها از رأس i به رأس j و مؤلفهٔ قطری formula_21 تعداد طوقه‌های رأس i است. ماتریس مجاورت یک گراف جهت‌دار (با یکسان در نظر گرفتن جایگشت‌های سطرها و ستون‌ها) یکتاست. نمایش ماتریسی دیگری برای یک گراف، ماتریس وقوع آن است. درجهٔ ورودی و درجهٔ خروجی.برای هر گره، تعداد رأس‌های ابتدایی مجاور، درجهٔ ورودی و تعداد رأس‌های انتهایی مجاور، درجهٔ خروجی (در درخت‌ها ضریب انشعاب) نامیده می‌شود.درجهٔ ورودی با formula_22 و درجهٔ خروجی با formula_23 نمایش داده می‌شود. رأس با formula_22 صفر منبع نامیده می‌شود (چون مبدأ همهٔ یال‌های متصل به خودش است) و به‌طور مشابه رأس با formula_23 صفر چاه نامیده می‌شود.رابطهٔ مجموع درجات بیان می‌کند که برای یک گراف جهت‌دار:formula_26اگر برای هر گرهٔ ، formula_27 گراف را یک گراف جهت‌دار متعادل می‌نامیم.همبندی گراف جهت‌دار.می‌گوییم یک گراف جهت‌دار ضعیفاً همبند است (یا همبند است ) اگر گراف زمینهٔ آن (که با حذف جهت یال‌ها به دست می‌آید) یک گراف همبند باشد. می‌گوییم یک گراف جهت‌دار قویاً همبند است (یا قوی است) اگر برای هر جفت رأس u و v مسیر جهتداری از u به v و مسیر جهتداری از v به u داشته باشد. مؤلفه‌های قوی ، زیرگراف‌های قویاً همبند ماکزیمال هستند.انواع گراف‌های جهت‌دار.گراف جهت‌دار G متقارن نامیده می‌شود اگر برای هر کمان متعلق به G، معکوس آن کمان نیز متعلق به G باشد. یک گراف جهت‌دار متقارن بدون طوقه معادل یک گراف بدون جهت است که با گذاشتن یک یال به جای هر جفت کمان معکوس هم به دست می‌آید (و بنابراین تعداد یال‌هایش نصف تعداد کمان‌های گراف اولیه است).یک گراف جهت‌دار بی‌دور یا گراف بی‌دور جهت‌دار، گرافی جهت‌دار است که هیچ دور جهت‌داری ندارد. درخت‌های چندگانه (گراف‌هایی که در آن‌ها هیچ دو مسیر جهت‌داری که از یک گره شروع شده‌اند دوباره در یک گرهٔ مشترک تمام نمی‌شوند)، درخت‌های جهت‌دار یا چنددرخت‌ها (گراف‌های جهت‌داری که از جهت‌دار کردن یال‌های یک گراف بدون جهت بی‌دور ساخته می‌شوند) و درخت‌های ریشه‌دار (درخت‌های جهت‌داری که تمام یال‌های درخت بدون جهت زمینهٔ آن به سمت دور شدن از ریشه جهت‌دار شده‌اند) حالت‌هایی خاص از گراف‌های جهت‌دار بی‌دور هستند.یک تورنمنت گرافی جهت‌دار است که از جهت‌دار کردن همهٔ یال‌های یک گراف کامل بدون جهت به دست می‌آید.در نظریهٔ گروه‌های لی، یک quiver، گرافی جهتدار است که دامنهٔ نمایش v (که به عنوان عملگر تعریف شده) می‌باشد (و بنابراین مشخص کنندهٔ شکل V است)؛ به ویژه شیئی از طبقهٔ عملگری FinVctKF(Q) است که (F(Q طبقهٔ آزاد روی Q و تشکیل شده از مسیرهای Q است و FinVctK طبقهٔ فضای برداری با بعد متناهی روی میدان K است. نمایش‌های یک quiver رأس‌های آن را با فضاهای برداری و یال‌هایش (و در نتیجه مسیرهایش) را به‌طور سازگاری با تبدیلات خطّی بین این فضاها و تبدیل از طریق تبدیلات طبیعی برچسب‌گذاری می‌کند.