درس هشتم: يالها و گرافهای وزن دار و جهت دار

به طور معمول در گرافها يالها هيچ تفاوتی (مگر احتمالاً در دو سرشان) با هم ندارند. اما فرض کنيد بخواهيم گرافی را برای بررسی جاده های ميان شهرهای يک کشور به کار ببريم. در اين حالت مواردی همچون مسافت جاده ها و يک طرفه يا دو طرفه بودن جاده سبب ايجاد تمايز می گردد. برای حل اين گونه مشکلات از مفاهيمی با عنوان يالهای وزن دار و يالهای جهت دار استفاده می گردد.

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

وزن در يک گراف تابعی از مجموعه يالهای آن گراف به مجموعه اعداد حقيقی است و به چنين يالهايي، يالهای وزن دار گفته می شود. در نمايش يک يال وزن دار در صفحه معمولاً عدد تابع يال را روی آن می نويسند.