در ریاضیات و به طور خاص در نظریهٔ گراف، گراف جهت دار یا گراف سودار[ ۱] گرافی ( مجموعه ای از گره ها که با یال ها به هم متصل شده اند ) است که در آن به هر یال جهتی نسبت داده شده است. به زبان ریاضی، یک گراف جهت دار زوج مرتبی به صورت G = ( V , A ) است ( گاهی به صورت G = ( V , E ) نیز نمایش داده می شود ) که در آن[ ۲]
• V مجموعه ایست که اعضایش را رأس یا گره می نامند
• A مجموعه ای از زوج های مرتبی از رأس ها است که کمان، یال جهت دار، فلش یا گاهی یال نامیده می شوند ( که در حالت اخیر مجموعهٔ متناظر را به جای A، با E نمایش می دهند ) .
گراف جهت دار با گراف معمولی عمده تفاوتشان در تعاریف یال هاست. یعنی زوج مرتب ( a, b ) با زوج مرتب ( b , a ) تفاوتی در گراف معمولی یا بدون جهت ندارد و در حالت کلی تر آن را به شکل ab می نویسیم ولی در گراف جهت دار زوج مرتب های ( a, b ) با ( b, a ) تفاوت دارد و نشان دهنده سوی یال است و نشان دهنده ی نحوه ی ارتباط بین این دو راس می باشد.
یک گراف جهت دار ساده نامیده می شود اگر هیچ طوقه و یال چندگانه ای نداشته باشد ( یال های چندگانه یعنی یال هایی که ابتدا و انتهای یکسانی دارند ) . در یک گراف چندگانهٔ جهت دار یال ها تشکیل یک مجموعهٔ چندگانه ( به جای مجموعه ) از زوج های مرتب رأس ها می دهند و این گراف ها می توانند طوقه و یال چندگانه داشته باشند ( طوقه یالی است که ابتدا و انتهایش رأس یکسانی است ) . در برخی متون، گراف جهت دار ( بدون ذکر ویژگی ساده بودن ) می تواند طوقه، یال چندگانه یا هر دو را داشته باشد.
یال e = ( x , y ) دارای جهت از x به y در نظر گرفته می شود. y ابتدا و x انتهای یال نامیده می شود. y را رأس مابعد مستقیم x و x را رأس ماقبل مستقیم y می نامند. اگر مسیری متشکل از یک یا چند یال رو به جلو از x به y وجود داشته باشد، به y رأس مابعد x و به x رأس ماقبل y می گویند. به یال ( y , x ) معکوس یال ( x , y ) می گویند.
جهت دار کردن یک گراف سادهٔ بدون جهت یعنی نسبت دادن جهت به هر یال آن گراف. هر گراف جهت داری که به این طریق ساخته شود گراف جهت دار شده ( به انگلیسی: oriented graph ) نامیده می شود. یک گراف جهت دار، یک گراف سادهٔ جهت دار شده است اگر و تنها اگر نه طوقه داشته باشد و نه حلقهٔ دوتایی ( یال چندگانه ) . [ ۳]
گراف جهت دار وزن دار ( به انگلیسی: weighted digraph ) گراف جهت داری است که به هر یالش وزنی نسبت داده شده است، درست مانند گراف بدون جهت وزن دار. در نظریهٔ گراف به گراف جهت دار با یال های وزن دار، شبکه ( به انگلیسی: network ) می گویند.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلف• V مجموعه ایست که اعضایش را رأس یا گره می نامند
• A مجموعه ای از زوج های مرتبی از رأس ها است که کمان، یال جهت دار، فلش یا گاهی یال نامیده می شوند ( که در حالت اخیر مجموعهٔ متناظر را به جای A، با E نمایش می دهند ) .
گراف جهت دار با گراف معمولی عمده تفاوتشان در تعاریف یال هاست. یعنی زوج مرتب ( a, b ) با زوج مرتب ( b , a ) تفاوتی در گراف معمولی یا بدون جهت ندارد و در حالت کلی تر آن را به شکل ab می نویسیم ولی در گراف جهت دار زوج مرتب های ( a, b ) با ( b, a ) تفاوت دارد و نشان دهنده سوی یال است و نشان دهنده ی نحوه ی ارتباط بین این دو راس می باشد.
یک گراف جهت دار ساده نامیده می شود اگر هیچ طوقه و یال چندگانه ای نداشته باشد ( یال های چندگانه یعنی یال هایی که ابتدا و انتهای یکسانی دارند ) . در یک گراف چندگانهٔ جهت دار یال ها تشکیل یک مجموعهٔ چندگانه ( به جای مجموعه ) از زوج های مرتب رأس ها می دهند و این گراف ها می توانند طوقه و یال چندگانه داشته باشند ( طوقه یالی است که ابتدا و انتهایش رأس یکسانی است ) . در برخی متون، گراف جهت دار ( بدون ذکر ویژگی ساده بودن ) می تواند طوقه، یال چندگانه یا هر دو را داشته باشد.
یال e = ( x , y ) دارای جهت از x به y در نظر گرفته می شود. y ابتدا و x انتهای یال نامیده می شود. y را رأس مابعد مستقیم x و x را رأس ماقبل مستقیم y می نامند. اگر مسیری متشکل از یک یا چند یال رو به جلو از x به y وجود داشته باشد، به y رأس مابعد x و به x رأس ماقبل y می گویند. به یال ( y , x ) معکوس یال ( x , y ) می گویند.
جهت دار کردن یک گراف سادهٔ بدون جهت یعنی نسبت دادن جهت به هر یال آن گراف. هر گراف جهت داری که به این طریق ساخته شود گراف جهت دار شده ( به انگلیسی: oriented graph ) نامیده می شود. یک گراف جهت دار، یک گراف سادهٔ جهت دار شده است اگر و تنها اگر نه طوقه داشته باشد و نه حلقهٔ دوتایی ( یال چندگانه ) . [ ۳]
گراف جهت دار وزن دار ( به انگلیسی: weighted digraph ) گراف جهت داری است که به هر یالش وزنی نسبت داده شده است، درست مانند گراف بدون جهت وزن دار. در نظریهٔ گراف به گراف جهت دار با یال های وزن دار، شبکه ( به انگلیسی: network ) می گویند.
wiki: گراف جهت دار