گراف کامل

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

تعریف گراف کامل

گراف ساده G=(V,E) را کامل گویند، اگر هر راس آن با تمام راس‌های دیگر متصل باشد، در واقع هر دو راس این گراف با یک یال به هم متصل می‌باشد.

گراف کامل با p راس را به‌صورت kp نمایش می‌دهند.

گراف‌های زیر همگی گراف‌های کاملی هستند:

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

دریافت مثال

قضایای گراف کامل

قضیه

تعداد یال‌های گراف کامل kp برابر است: 

q=p2=p(p-1)2    ;    pN

اثبات

با توجه به این‌که درجه هر راس یک گراف کامل kp ، برابر p-1 می‌باشد، پس مجموع درجه‌های راس‌های گراف kp برابر است با pp-1 یعنی:  

(p-1)+(p-1)+...+(p-1)=p(p-1)

پرانتزهای p-1 به تعداد p بار تکرار شده است.  

چون در یک گراف کامل kp درجه هر راس p-1 است، داریم:  

i=1pdeg(vi)=2q(p-1)+(p-1)+...+(p-1)=2q⇒p(p-1)=2qq=p(p-1)2q=p2

دریافت مثال

قضیه

در گراف ساده G از مرتبه p همواره داریم:

qG=p2-q(G)

اثبات

تعداد یال‌های=kpتعداد یال‌هایG+تعداد یال‌هایG

qG+qG=p2qG=p2-qG

قضیه

در یک گراف کامل kp تعداد مسیرهای متفاوت از یک راس u به راس w از دو فرمول زیر به‌دست می‌آید:  

k=0p-2p-2(k)p2!×e

p تعداد راس‌ها

e عدد نپز معادل 2/71

اثبات

به‌عنوان مقدمه برای اثبات قضیه فوق به تمرین زیر توجه کنید:

در گراف کامل kp با شرط 2p4 تعداد مسیرهای متفاوت از یک راس u به راس v که (uv) را پیدا می‌کنیم:   

اگر p=2 باشد ، پس نمودار kp چنین است: 

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

که تنها یک مسیر در آن دیده می‌شود.


اگر p=3 باشد ، پس نمودار kp چنین است: 

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

از راس u به راس v دو مسیر متفاوت وجود دارد:

p1=uvp2=uwv


اگر p=4 باشد ، پس نمودار kp چنین است: 

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

از راس u به راس v پنج مسیر متفاوت وجود دارد:

p1=uvp2=uwvp3=uxvp4=uxwvp5=uwxv


حال به اثبات فرمول اول می‌پردازیم:

یادآوری می‌کنیم که تعداد جایگشت‌های (تبدیل‌های) r تایی n شی:

nr=n!(n-r)!


تعداد مسیرهای به طول 1 بین دو راس w و u. (k=0 تعداد راس‌های بین w و u

k=0;(p2)(0)=(p2)!(p2)0!=(p2)!(p2)!=1


تعداد مسیرهای به طول 2 بین دو راس w و u. (k=1 تعداد راس‌های بین w و u

k=1;(p2)(1)=(p2)!(p2)1!=(p2)!(p3)!=(p2)(p3)!(p3)!=(p2)

زیرا مسیرهای به طول 2 بین w و u عبارتند از uxw که در آن به‌جای x به تعداد p-2 راس دیگر را می‌توان قرار داد.


تعداد مسیرهای به طول 3 بین دو راس w و u. (k=2 تعداد راس‌های بین w و u

k=2;(p-2)(2)=(p-2)!(p-2)-2!=(p-2)!(p-4)!=(p-2)(p-3)(p-4)!(p-4)!=(p-2)(p-3)

زیرا مسیرهای به طول 3 بین w و u عبارتند از uxyw که در آن به‌جای x و y به تعداد p-2 راس دیگر را می‌توان قرار داد.


تعداد مسیرهای به طول n بین دو راس w و u دنباله‌هایی به‌صورت ua1a2...ap-2w هستند:  

k=p2;(p2)(p2)=(p2)!(p2)(p2)!=(p2)!0!=(p2)!1=(p2)!

بنابراین:

(p-2)(0)+(p-2)(1)+...+(p-2)(p-2)=k=0p-2(p-2)(k)

دریافت مثال

نکته

نتیجه اول از قضیه فوق آن‌است که:

تعداد کل مسیرهای متفاوت به طول r در گراف کامل kp  برابر است با:

12(p)r+1=12p!(p-r-1)!

دریافت مثال

نکته

نتیجه دوم از قضیه فوق آن‌است که:

تعداد مسیرهای متفاوت به طول r در گراف کامل kp  برابر است با: 

(p2)!(pr1)!

دریافت مثال

قضیه

تعداد دورهای به طول r در گراف کامل kp برابر است با:   

pr×(r1)!2

اثبات

a...a(r1)(r2)1pr×  (r1)×(r2)×...×12=pr×(r1)!2

دریافت مثال

تذکر

اگر بیان شود که گراف کامل kp چند دور مختلف دارد، بایستی دورهای به طول p=3,4,.... را یافته و با هم جمع کنیم.  

دریافت مثال

قضیه

در یک گراف کامل kp که p3 است، تعداد دورهای به طول p برابر است: 

(p-1)!2

اثبات

این قضیه را در یک حالت خاص مثلا در مورد گراف کامل k4 ثابت می‌کنیم.

می‌دانیم که هر دور به طول 4 در گراف کامل k4 حتما از هم‌راس‌ها عبور می‌کند، بنابراین می‌توانیم در موقع نامگذاری دورهای به طول 4 همه آنها را از a شروع می‌کنیم. 

بنابراین a را ثابت می‌گیریم و جعبه‌هایی به‌شکل زیر در نظر می‌گیریم:

راس‌های d,c,b باقی می‌مانند.

می‌دانیم این راس به 3! طریق می‌تواند در سه محل باقی‌مانده قرار گیرند، تمام این 3! طریق در زیر نوشته شده است: 

abcdaabdca          adcbaadbca             acdbaacbda

اگر دقت کنید ملاحظه می‌شود که دورهای abcda و adcba یکسانند زیرا اگر دور abcda را برعکس بخوانیم adcba به‌دست می‌آید.  

abcdaadcbaabdcaacdbaacbdaadbca

بنابراین هر دور از این 6 دور نوشته شده با یکی از این دورها مساوی است، در نتیجه تعداد واقعی دورها برابر است با:

3!2=41!2

تذکر

به‌ازای p3 گراف کامل kp دور دارد و اگر n عددی طبیعی بوده و 3np باشد، آن‌گاه گراف kp دوری به طول n دارد.

قضیه

اگر A ماتریس مجاورت گراف کامل kp باشد، هر درایه واقع بر قطر اصلی ماتریس A2 برابر با p-1 است و هر درایه غیر واقع بر قطر اصلی A2 برابر p-2 است.  

اثبات

می‌دانیم که تعداد یال‌های گراف کامل kp برابر است با:   

p2=p(p-1)2

از طرفی می‌دانیم که مجموع درایه‌های قطر اصلی ماتریس A2 برابر است با دو برابر تعداد یال‌ها:

q(G)=p2q(G)=p(p-1)22q(G)=p(p-1)

چون گراف kp دارای p راس می‌باشد، پس ماتریس مجاورت آن یعنی A و درنتیجه A2 دارای p سطر (یا ستون) است، لذا هر درایه واقع بر قطر اصلی باید برابر p-1 باشد تا حاصل جمع همه آنها (یعنی p درایه) برابر pp-1 گردد.      

A=0     1     1          11     0     1          11     1     0          1                         1     1     1         0p×p        A2=p1       p2      p2            p2p2       p1      p2            p2p2       p2     p1              p2                                                                        p2       p2      p2               p1

تمرین

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

A=0     1     11     0     11     1     0

ماتریس A2 را بنویسید.

A×A=0     1     11     0     11     1     0×0     1     11     0     11     1     0A2=2     1     11     2     11     1     2


همان‌طور که مشاهده می‌کنید، هر درایه واقع بر قطر اصلی ماتریس A2 برابر است:

p-1=3-1=2


هر درایه غیر واقع بر قطر اصلی A2 برابر است:

p-2=3-2=1

قضیه

اگر A ماتریس مجاورت گراف کامل kp باشد، مجموع درایه‌های ماتریس A2 برابر است:

p(p-1)2

اثبات

ماتریس مجاورت kp به‌صورت زیر است:

A=0     1     1          11     0     1          11     1     0          1                         1     1     1         0p×p        A2=p1       p2      p2            p2p2       p1      p2            p2p2       p2     p1              p2                                                                        p2       p2      p2               p1

p2-p تا از درایه‌های ماتریس A2 عدد p-2 است و p تا از درایه‌های ماتریس A2 عدد p-1 است:      

مجموع درایه‌های ماتریس A2:

(p2-p)  (p-2)+pp-1=p(p-1)  (p-2)+pp-1=p(p-1)(p-2)+1=p(p-1)(p-1)=(p-1)2p

دریافت مثال

نکته

1- گراف کامل kp همان گراف (p-1 - منتظماز مرتبه p است.  

در گراف کامل kp درجه هر راس p-1 است، بنابراین گراف (p-1 - منتظم) از مرتبه p یک گراف کامل است.      

تمرین

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

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

شکل 1 چه نوعی گراف است؟ 

شکل 1 گراف کامل k1 می‌باشد که همان گراف (0 - منتظم) از مرتبه یک است.   

شکل 2 چه نوعی گراف است؟ 

شکل 2 گراف کامل k2 می‌باشد که همان گراف (1 - منتظم) از مرتبه دو است.   

شکل 3 چه نوعی گراف است؟ 

شکل 3 گراف کامل k4 می‌باشد که همان گراف (3 - منتظم) از مرتبه چهار است.   

شکل 4 چه نوعی گراف است؟ 

شکل 4 گراف کامل k5 می‌باشد که همان گراف (4 - منتظم) از مرتبه پنج است.   

دریافت مثال

نکته

2- گراف kp یک گراف تهی از مرتبه p است. 

تمرین

تعداد یال‌های گراف k10 را به‌دست ‌آورید. 

گراف k10 مکمل گراف کامل k10 است، بنابراین k10 یک گراف تهی از مرتبه 10 می‌باشد، چون در گراف کامل k10 بین هردو راس یک یال وجود دارد.   

نکته

3- از ترکیب یک گراف ساده G و گراف ممکن آن یعنی یک گراف کامل به‌دست می‌آید.

4- تمام راس‌های گراف کامل kp از درجه p-1 است و داریم:

Δ=δ=p-1

ضمنا گراف کامل kp عبارت 1+8q مربع کامل است و δ+Δ ماکزیمم است.  

دریافت مثال

نکته

5- اگر از تعداد راس‌های یک گراف کامل kp یک راس حذف کنیم به تعداد p-1 یال از تعداد یال‌های آن کم می‌شود و اندازه 2p-1 از مجموع درجات راس‌ها کم می‌شود.      

دریافت مثال

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

گراف کامل

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

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