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

آخرین ویرایش: 09 اسفند 1402
دسته‌بندی: گراف
امتیاز:

تعریف

گراف ساده 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- در زمان رسم نمودار یک گراف توجه کنید که هیچ یالی خودش را قطع نکند و هیچ یالی نباید از روی راسی که مربوط به دو سر آن یال نیست، عبور نماید.

تمرین

گراف های زیر را در نظر بگیرید:

كدام‌يک از شكل های فوق مشخص كننده يک گراف ساده است؟

گرافی مشخص كننده يک گراف ساده است كه:


اولا) طوقه نداشته باشد.


ثانيا) بين هر دو راس آن حداكثر يک يال داشته باشيم.


شکل 2 گراف ساده است.

تمرین

گراف های زیر را در نظر بگیرید:

كدام شکل می‌تواند معرف گراف با مشخصات زير باشد.

G=V,EV=a,b,c,dE=ac,ad,bd

شکل 2 گراف ساده است.

تمرین

اگر داشته باشیم:

V=a,b,c,dE=ab,ac,bd,bc

آن‌گاه نمودار گراف G=V,E را رسم كنيد.

تمرین

شش تيم فوتبال f,e,d,c,b,a با يک‌ديگر مسابقه می‌دهند، بازی های زير انجام شده است:

a با c,d,f بازی كرده است.

d با a,e,f  بازی كرده است.

b با c,e,f بازی كرده است.      

e با b,d,f  بازی كرده است.

c با a,b بازی كرده است.   

f با a,b,d,e بازی كرده است. 

گراف مربوط به اين مسابقه را رسم كنيد.

G=V,E


V=a,b,c,d,e,f


E=ac,ad,af,bc,be,bf,de,df,ef


تمرین

فرض كنيد:

V=a,b,c,d,eE=ab,ad,ae,bc,bd,ce,de

اگر داشته باشیم:

نمودار گراف G=V,E كدام یک از شکل های فوق است؟

تمرین

يک مثال در (زندگی واقعی) از يک گراف G ارائه دهيد كه هم به راس و هم به يال های آن داده هايی نسبت داده شده باشد.

راس های گراف G را نمايش شهرها با جمعيت‌شان و يال های G را نمايش فاصله بين شهر‌ها در نظر بگيريد.

تمرین

گراف G با اطلاعات زیر را در نظر بگیرید:

V=v1,v2,v3,v4E=v1v2,v1v3,v2v3,v3v4

در اين گراف راس های مجاور با راس v2 را بيابيد.

چون v1v2 يک يال دراين گراف است، پس v1 با v2 مجاور است.


از طرفی v2v3 نيز یک يال دراين گراف  می‌باشد، پس v3 با v2 مجاور است، بنابراين فقط راس های v1 و v3 با راس v2 مجاورند.

تمرین

اگر داشته باشیم:

V=v1,v2,v3,v4E=v1v2,v1v3,v3v4,v2v4,v1v4

گراف ساده G=V,E را رسم کنید. 

تمرین

نمودار گراف G در زیر رسم شده است.

مجموعه های V و E را مشخص كنيد.

V=v1,v2,v3,v4,v5


E=v1v2,v1v3,v1v4,v2v4,v2v5,v3v4,v4v5

تمرین

كدام‌يک از وضعيت‌های زير بیان‌گر گراف ساده نیست؟

وضعيت ژنتيک افراد يک خانواده 

گراف مربوط به این حالت يک گراف ساده است.


 زيرا هيچ فردی از خودش به وجود نمی‌آيد (عدم وجود طوقه) 


هيچ فردی دو بار زائيده نمی‌شود.

نقشه جاده‌های كشور

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


زيرا بين دو  شهر در يک كشور ممكن است بيش از يک جاده وجود داشته باشد، لذا اين امر يال چندگانه را امكان پذير می‌سازد.

دوستی ما بين يک گروه از انسان‌ها

گراف مربوط به این حالت يک گراف ساده است.


در این حالت دوست بودن یک فرد با خودش معنی ندارد. (عدم وجود طوقه)


در يک گراف، وقتی دو نفر با يک‌ديگر دوست می‌باشند را فقط با يک يال به‌هم متصل می‌كنند. 

مسابقات ورزشی يک حذفی

گراف مربوط به این حالت يک گراف ساده است.


در این حالت می‌توان گفت د‌ر مسابقات ورزشی يک حذفی، هر تيم با تيم ديگر بيش از يک بار مسابقه نمی‌دهد. (يال چندگانه ندارد) 


ضمنا هيچ تيمی با خودش مسابقه نمی‌دهد. ( عدم وجود طوقه)

تمرین

گراف های زیر را در نظر بگیرید:

در كدام‌يک از گراف های فوق، خاصيت زیر برقرار است؟

acEbcE  ,  abE

تمرین

گراف های زیر را در نظر بگیرید:

در كدام يک از گراف های فوق، مجموعه راسی را می‌توان به دو مجموعه X و Y افراز كرد به‌طوری كه هر يال گراف مورد نظر، دارای يک انتها در X و  يک انتها در Y باشد؟

اگر قرار دهيم:


X=b,eY=a,b,c


در اين صورت هر يال در اين گراف دارای يک انتها در X و يک انتها در Y است.



پس گراف زیر، گراف مورد نظر است:


دریافت مثال

خرید پاسخ‌ها

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

4,000تومان
خرید فایل PDF مثال ها و جواب ها

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