گراف (ریاضی)

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

نظریه گراف یکی از موضوع‌های مهم در ریاضیات گسسته است که به مطالعهٔ گراف‌ها و مدلبندی مسائل به وسیلهٔ آن‌ها می‌پردازد. اویلر در سال ۱۷۳۶ با حل مسئله پل‌های کونیگسبرگ نظریهٔ گراف‌ها را بنیان گذاشت. اما جیمز جوزف سیلوستر نخستین کسی بود که در سال ۱۸۷۸ از واژهٔ گراف برای نامیدن این مدل‌های ریاضی استفاده کرد.

تعریف

یک گراف از مجموعه‌ای غیر خالی از اشیاء به نام رأس تشکیل شده، که آن را با $V$ نشان می‌دهیم، و مجموعه‌ای شامل یال‌ها، که رأس‌ها را به هم وصل می‌کنند و با $E$ نمایش می‌دهیم. یک چنین گرافی را با $G = (V,E)$ نشان می‌دهیم. اگر یال $y$ دو رأس $v_1$ و $v_2$ را به هم وصل کند می‌نویسیم $y = \lbrace v_1,v_2 \rbrace$.

جستارهای وابسته

نظریه گراف

منابع

• بابلیان، اسماعیل. مباحثی در ریاضیات گسسته. چاپ ششم. تهران: مبتکران، ۱۳۸۶. شابک ‎۹۷۸-۹۶۴-۵۹۹۳-۳۲-۸. 
• بهزاد، مهدی، علی رجالی، علی عمیدی و عبادالله محمودیان. ریاضیات گسسته. چاپ دوازدهم. تهران: شرکت چاپ و نشر کتاب‌های درسی ایران، ۱۳۸۵. شابک ‎۹۶۴-۰۵-۰۱۰۳-۴.