نمایش ماتریسی گراف ساده

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

تعریف ماتریس مجاورت گراف ساده

ماتریس مجاورت گراف ساده G=(V,E) از مرتبه p که با نماد AG نمایش داده می‌شود، عبارت است از A(G)=aijp×p به‌طوری‌که:

aij=1    ;    ViVjE(G)0    ;    ViVjE(G)

تمرین

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

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

ماتریس مجاورت گراف ساده فوق را بنویسید.

A(G)=0      1      0       1        01      0      0       1        10     0      0       1         11      1       1       0        10     1       1        1       0


همان‌طور که مشاهده می‌شود، تمام درایه‌های این ماتریس 0 و 1 است.


درایه aij از ماتریس را برابر 1 می‌گیریم اگر Vi و Vj را یالی به‌هم وصل کرده باشد، یعنی ViVjE(G) در غیر این‌صورت درایه aij عدد 0 است.  


در گراف فوق چون V4 و V5 به‌وسیله یالی به‌هم متصل شده‌اند a45=1 است. (سطر چهارم و ستون پنجم)  

تمرین

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

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

ماتریس مجاورت گراف ساده فوق را بنویسید.

A(G)=0110101111010110

دریافت مثال

نکته

ویژگی‌های ماتریس مجاورت یک گراف ساده

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

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

ماتریس مجاورت این گراف ساده به شکل زیر است:

A(G)=01011010010110104×4

1- ماتریس A مربعی است. 

2- درایه‌های روی قطر اصلی A همگی صفرند، زیرا هیچ راسی با خودش مجاور نیست یعنی در گراف ساده طوقه نداریم.

اگر در ماتریس مجاورت یک گراف تعداد عناصرغیر صفر فرد باشد، گراف ساده نیست، یعنی طوقه دارد یا جهت‌دار است.

3- هر درایه ماتریس A برابر صفر یا یک است.

4-ماتریس A متقارن است یعنی aij=aji

5- تعداد یک‌های ماتریس، برابر با تعداد درجه‌های راس‌های این گراف است و برابر 2q می‌باشد.

6- تعداد یک‌های یک سطر (یا یک ستون) برابر با درجه راس مربوط به آن سطر (یا ستون) است.

7- مرتبه ماتریس مجاورت، با مرتبه گراف یعنی p برابر است.

8- نصف تعداد یک‌ها برابر است با تعداد یال‌های q.

9- تعداد درایه‌های 1 در ماتریس مجاورت یک گراف ساده از مرتبه p و اندازه q را برابر 2q و لذا تعداد درایه‌های صفر برابر p2-2q است.    

دریافت مثال

قضایای ماتریس مجاورت

قضیه

تعداد یک‌های یک سطر (یا یک ستون) برابر با درجه راس مربوط به آن سطر (یا ستون) است.

اثبات

اگر A ماتریس مجاورت گراف ساده G=(V,E) باشد، هر عدد یک که در سطر iام (یا ستون iام) A ظاهر شود که 1ip نشان‌گر آن است که از راس Vi (راس متناظر همان سطر یا ستون) یک یال عبور کرده، بنابراین تعداد 1 های سطر iام (یا ستون iام) برابر تعداد یال‌هایی است که از راس Vi عبور می کند، بنابراین این تعداد این 1 ها درجه راس Vi می‌باشد.    

دریافت مثال

قضیه

اگر A ماتریس مجاورت گراف ساده G=(V,E) از مرتبه p باشد، هر درایه واقع بر قطر اصلی ماتریس A2 برابر است با درجه راس متناظر سطر (یا ستون) درایه مزبور 

به‌عبارت دیگر، اگر ViV(G) باشد، آن‌گاه در درایه سطر iام و ستون iام ماتریس: 

deg(Vi)=A2

اثبات

چون A متقارن است، بنابراین aij=aji.

درایه سطر iام و ستون iام از A2 مطابق زیر به‌دست می‌آید:

ai1a1i+ai2a2i+...+aipapi=ai1.ai1++ai2ai2+...+aipaip=a2i1+a2i2+...+a2ip

می‌دانیم تعداد یک‌های موجود در سطر iام A برابر درجه راس Vi می‌باشد، چون i2=1 بنابراین حاصل فوق همان درجه راس Vi است.  

نکته

اگر A ماتریس مجاورت گراف ساده G از مرتبه p و اندازه q باشد، آن‌گاه: 

مجموع درایه‌های قطر اصلی A2:

q(G)=12

دریافت مثال

قضیه

فرض کنید A ماتریس مجاورت گراف G با p راس باشد که در آن p>1 است، در این‌صورت درایه ijام ماتریس An تعداد مسیرهای به‌طول n از راس Vi به راس Vj است. 

ماتریس وقوع گراف ساده

 فرض کنید M=mijp×q یک ماتریس p×q باشد که به‌صورت زیر تعریف شده است:

mij=1  0 

 1 وقتی در نظر گرفته می‌شود که راس vi روی یال ej واقع شده باشد.

در غیر این صورت 0 را در نظر می‌گیریم. 

آن‌گاه M را ماتریس وقوع G نامیده می‌شود.

از آنجا که گراف G دارای p راس و q یال است، از این رو ماتریس وقوع M یک ماتریس p×q است.

دریافت مثال

ساختار مجاورت (پیوندی) گراف ساده

سوال) فرض کنید G یک گراف با p راس باشد، دو عیب اساسی ذخیره در حافظه کامپیوتر را به‌صورت ماتریس مجاورت توضیح دهید؟  

عیب اول) اگر خواسته باشیم مجموعه راس‌ها و یا مجموعه یال‌ها را تغییر دهیم، ممکن است انجام تغییرات مورد نظر روی AG مشکل باشد. 

عیب دوم) ممکن است ماتریس A یک ماتریس خلوت باشد (که حاوی تعداد بسیار زیادی صفر است) از این رو، وقتی A در حافظه کامپیوتر ذخیره می شود، مقدار زیادی از حافظه بدون معرف رها می‌شود.

بنابراین، معمولا ماتریس AG به‌صورت نمایش ساختار مجاورت یا پیوندی در حافظه کامپیوتر ذخیره می‌شود که به بحث آن می‌پردازیم. 

تعریف- گراف زیر را در نظر بگیرید:

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

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

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

پس از هر راس Vi از گراف G در نمایش ساختار مجاورت گراف G مجموعه راس‌های مجاور آن نوشته می‌شود، چنین نمایشی ممکن است مانند جدول فوق به‌صورت فشرده زیر نشان داده شود:

G =A:B,P ; B:A,C,P,Q ; C:B ; P: A,B ; Q :B

ملاحظه می‌کنید که کالن : یک راس را از لیست راس‌های مجاور آن جدا می‌کند و سمی‌کالن ; لیست‌های مختلف را از هم جدا می‌کند.

به این نمایش گاهی اوقات نمایش پیوندی گراف G می‌گویند زیرا غالباً لیست‌های راس‌های مجاورت در حافظه کامپیوتر به‌صورت لیست‌های پیوندی نمایش داده می‌شود.

دریافت مثال

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

نمایش ماتریسی گراف ساده

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

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