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

تاریخ انتشار: 15 آذر 1399
آخرین ویرایش: 14 تیر 1400
دسته‌بندی: گراف
امتیاز:
بازدید: 28 مرتبه

تعریف- گراف ساده G را با زوج مرتب G=(V,E) نمایش می‌دهند و عبارت است از:

V=v1,v2,...,vp

مجموعه فوق مجموعه‌ای ناتهی و متناهی است که عناصر آن را  گره یا رأس می‌نامیم و مجموعه راس‌های گراف G را با VG نمایش می‌دهند.

E=e1,e2,...,eq

مجموعه فوق زیرمجموعه‌های دوعضوی V است که آنها را یال‌های G می‌نامیم و مجموعه یال‌های گراف G را با EG نمایش می‌دهند.   

در این‌صورت برای هر راس vi و vj که (ij) توسط یال ek به‌هم متصل شده باشند، داریم:

ek=vivj=vivj    ;    (ij)

نکته

از تعریف گراف ساده درمی‌یابیم:

1- مجموعه یال‌ها یعنی EG می‌تواند تهی باشد یعنی هیچ یالی به راس‌ها وجود نداشته باشد. 

2- مجموعه راس یعنی VG نمی‌تواند تهی باشد. 

3- دو مجموعه V و E از هم جدا هستند. 

4- مجموعه یال‌ها یعنی EG شامل زیرمجموعه‌های دو عضوی از عناصر متمایز مجموعه راس VG می‌باشد.   

5- در یک گراف ساده هر دو راس حداکثر با یک یال به یک‌دیگر متصل می‌گردند. اتصال یا پیوند، یالی است که دو انتهایش از هم مجزا است.

6- راس منفرد راسی است که با هیچ راسی مجاور نباشد.

دو راس مجاور یا دو راس همسایه

دو راس vi و vj از یک گراف که به‌وسیله یک یال vivj به‌هم متصل شده باشد را دو راس مجاور (یا همسایه) می‌گویند.

به‌عنوان نمونه، گراف زیر در نظر بگیرید:

گراف ساده - پیمان گردلو

راس v1 با رئوس v2 و v5 همسایه است.

راس v2 با رئوس v1 و v3 و v4 همسایه است.  

همسایگی باز راسv

به مجموعه راس‌هایی از گراف G که به راس v متصل هستند، همسایگی باز راس v می‌گوییم و با NGv نمایش می‌دهیم.

همسایگی بسته راسv

اضافه کردنِ خودِ راسِ v به NGv را همسایگی بسته راس v می‌گوییم و با NGv نمایش می‌دهیم.   

تمرین

شکل زیر را در نظر بگیرید:

گراف ساده - پیمان گردلو

همسایگی باز راس‌های a,c,f را نمایش دهید.  

NGa=bNGc=b,d,gNGf=

همسایگی بسته راس‌های a,c,f را نمایش دهید.  

NGa=a,bNGc=c,b,d,gNGf=f

دو یال مجاور

دو یال را مجاور گوییم هرگاه راسی وجود داشته باشد که هردوی آنها به آن راس متصل باشند.

به‌عنوان نمونه، گراف زیر در نظر بگیرید:

گراف ساده - پیمان گردلو

یال‌های bc و cd مجاورند.

نمودار گراف ساده

این شاخه از علم ریاضیات را گراف می‌گویند زیر می‌توان آن‌را به‌صورت تصویری معرفی نمود.

این نمایش تصویری بسیاری از خواص و ویژگی‌های گراف‌ها را به‌طور مشهودی به ما معرفی می‌کند.

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

ضمنا چگونگی رسم یال‌ها فعلا چندان اهمیتی ندارد چرا که هیچ راه منحصر به‌فردی برای رسم نمودار یک گراف موجود نمی‌باشد.

به‌عبارت دیگر برای رسم نمودار یک گراف، روش یکتایی مد نظر نیست و آن‌چه مهم است این است که باید مشخص باشد که گراف مورد نظر چند راس و چند یال دارد و کدام یال به‌کدام رئوس متصل است.

شکل‌های زیر هر دو یک گراف را نمایش می‌دهند:

گراف ساده - پیمان گردلو  

تذکر

1- در نظر گرفتن بیش از یک یال بین دو راس مجاز نیست، یعنی یال‌های چندگانه نداریم.

2- در یک گراف ساده، طوقه Loop وجود ندارد.

طوقه یالی است که ابتدا و انتهای آن یک راس است مانند راس a در گراف زیر:

گراف ساده - پیمان گردلو

3- در زمان رسم نمودار یک گراف توجه کنید که هیچ یالی خودش را قطع نکند و هیچ یالی نباید از روی راسی که مربوط به دو سر آن یال نیست، عبور نماید.

دریافت مثال

مثال‌ها و جواب‌ها

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

خرید فایل PDF مثال ها و جواب ها

برای ارسال نظر وارد سایت شوید