گراف (ریاضی): تفاوت میان نسخه‌ها

در واقع گراف مدلی ریاضی برای یک مجموعه گسسته است که اعضای آن به طریقی به هم مرتبط هستند. اعضای این مجموعه می‌توانند انسان باشند و ارتباط آن‌ها با هم دست دادن باشد. اعضا می‌توانند اتم‌ها در یک مولکول باشند و ارتباط آن‌ها اتصال‌های شیمیایی باشد یا اعضا می‌توانند قسمت‌های مختلف زمین و ارتباط بین آن‌ها پل‌هایی باشد که آن‌ها را به هم مرتبط می‌کند (همانند [[مسئله پل‌های کونیگسبرگ|مسئله کونیگسبرگ]]).<ref name="ReferenceA">{{پک|بابلیان|۱۳۸۶|ف=مباحثی از نظریه گراف|ک=مباحثی در ریاضیات گسسته|ص=۱۵۱}}</ref>

 

==تعریف==

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