گراف (ریاضیات گسسته)

گراف در ریاضیات گسسته

در ریاضیات گسسته، و به ویژه در نظریه گراف، یک گراف ساختاری است که شامل مجموعه‌ای از اشیاء است که برخی از جفت‌های آن‌ها به نوعی به هم مرتبط هستند. این اشیاء رأس (یا گره یا نقطه) نامیده می‌شوند و هر جفت مرتبط، یال (یا لینک یا خط) نام دارد.

گراف‌ها می‌توانند جهت‌دار یا بدون جهت باشند. به عنوان مثال، اگر رأس‌ها نمایانگر افراد در یک مهمانی باشند و یال بین دو نفر نشان‌دهنده دست دادن آن‌ها باشد، این گراف بدون جهت است. اما اگر یال از شخص A به شخص B نشان‌دهنده بدهی A به B باشد، گراف جهت‌دار است.

انواع گراف

• گراف جهت‌دار: گراف‌هایی که یال‌ها جهت دارند.
• گراف بدون جهت: گراف‌هایی که یال‌ها جهت ندارند.
• گراف وزندار: گراف‌هایی که به هر یال یک وزن (عدد) نسبت داده می‌شود.
• گراف دو بخشی: گراف‌هایی که رأس‌ها به دو مجموعه جداگانه تقسیم می‌شوند و یال‌ها فقط بین این دو مجموعه وجود دارند.

کاربردها

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