شروعی برای «گراف»

« گراف »

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

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

تعریف

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

در نظریه گراف‌ها، درجه یک راس به تعداد یال‌های متصل به آن راس گفته می‌شود. به عبارت دیگر، درجه یک راس تعداد همسایگی (مجاورت)‌های مستقیم یک راس را بیان می‌کند. از آنجا که هر یال در گراف دو راس را به هم وصل می‌کند، مجموع درجه راس‌های یک گراف با دو برابر تعداد یال‌های ان گراف برابر است.

مسطح و نامسطح

* در یک گراف ممکن است رأس ها یکدیگر را در نقاطی غیر از رأس ها قطع کنند ؛ اگر در یک گراف یال ها تنها در محل رأس ها متقاطع باشند به آن گراف مسطح و در غیر این صورت نا مسطح می گویند.

رئوس مجاور

* دو رأسی که بر روی یال مشترکی واقعند مجاور نامیده می شوند.

انواع یال ها

* یک یال با دو سر یکسان یال طوقه و یک یال با دوسر متمایز را یال پیوندی می نامند.

گراف های همسان و یکریختی گراف

* دو گراف را در نظر بگیرید که تعداد رأس ها و یال هایشان برابر بوده و علاوه بر آن تابع وقوع آن ها نیز یکسان می باشد.
در این صورت گراف های مزبور را همسان می نامند.
* اکنون دو گراف را در نظر بگیرید که تنها برچسب رأس ها و یا یال های آن ها با هم تفاوت دارند.
در این صورت گراف های مزبور را یکریخت می نامند.

گراف تهی

* گرافی که هیچ یالی نداشته باشد.

گراف دوبخشی

* گرافی که می توان مجموعه ی رأس های آن را به دو مجموعه ی X و Y چنان افراز کرد که یک سر تمام رأس ها درX
وسر دیگر رأس ها درY باشد.

درجه ی یک رأس

* درجه ی یک رأس برابر تعداد یال های واقع برآن رأس می باشد.


نوشته های فوق مطالبی بسیار ساده و ابتدایی از مبحث گسترده ی گراف بودند.
در این آموزش سعی شد تا تنها برخی از اصطلاحات گراف  بررسی و ذکر شود.
انشاءا... در آموزش های آینده مطالب بیشتر و به مراتب عمیق تر و صد البته سنگین تر برای استفاده شما عزیزان مطرح خواهد شد.
و همچنین در مطالب آینده بیشتر به بررسی سوالات گراف خواهیم پرداخت.

در پناه حق موفق و پیروز باشید.