درجه گراف ساده

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

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

مجموعه راس‌های گراف ساده G به‌صورت زیر را در نظر بگیرید:

V(G)=v1,v2,..,vk,...vp

درجه هر راس از گراف ساده G برابر تعداد یال‌هایی از G است که از راس vk می‌گذرند و این عدد را با degvk نمایش می‌دهند.

  • اگر degvk یک عدد فرد باشد، vk را یک راس فرد گویند.     
  • اگر degvk یک عدد زوج باشد، vk را یک راس زوج گویند. 
  • بزرگ‌ترین عدد در بین درجه‌های راس‌های گراف G را ماکزیمم درجه G می‌نامند و با  نشان می‌دهند.
  • کوچک‌ترین عدد در بین درجه‌های راس‌های گراف G را مینیموم درجه G می‌نامند و با δ نشان می‌دهند.  

تمرین

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

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

درجه راس‌های این گراف را بنویسید.

dega=3degc=4degb=3degd=2dege=2degf=0


دو راس از درجه فرد است و چهار راس از درجه زوج است، راس f را که درجه‌اش صفر است، راس تنها گویند.

تمرین

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

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

max و min درجه این گراف را بنویسید. 

Δ=5δ=2

دریافت مثال

قضایای درجه گراف ساده

قضیه

مجموع درجات تمام راس‌ها در گراف ساده G دوبرابر اندازه G یعنی q تعداد یال‌های G می‌باشد:  

i=1pdegVi=2q

اثبات

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

قضیه فوق در یک گراف غیرساده هم صادق است (گراف‌های چندگانه).با توجه به فرمول فوق، درجه کل یک گراف، زوج است.

دریافت مثال

قضیه

نامساوی زیر همواره برقرار است:

δ2qpΔ

اثبات

مجموعه راس‌های گراف ساده G به‌صورت زیر را در نظر بگیرید:

V(G)=v1,v2,..,vk,...vp


(1ip)

δdegViΔi=1pδi=1pdegVii=1pΔ  δ+δ+...+δi=1pdegViΔ+Δ+...+Δpδ2qpΔpδp2qppΔp   δ2qpΔ

دریافت مثال

قضیه

در هر گراف ساده تعداد راس‌هایی که درجه آنها فرد است، عددی زوج است.

اثبات

فرض کنید G یک گراف ساده و دارای n راس از درجه فرد و m راس از درجه زوج باشد که در آن n و m اعداد صحیح نامنفی است. 

باید ثابت کنیم که n عددی زوج است.

اگر n برابر صفر باشد، چون صفر زوج است آن‌گاه G دارای تعداد زوج، راس از درجه فرد است، از این رو فرض می‌کنیم n1 باشد. 

فرض کنید E مجموع درجه‌های همه راس‌های از درجه زوج و O مجموع درجه‌های همه راس‌های از درجه فرد و T درجه کل گراف G باشد. 

اگر u1,u2,...,um راس‌های از درجه زوج و V1,V2,...,Vn راس‌های از درجه فرد گراف G باشد، آن‌گاه: 

E=deg(u1)+deg(u2)+...+deg(um)O=deg(V1)+deg(V2)+...+deg(Vn)T=deg(u1)+...+deg(um)+deg(V1)+...+deg(Vn)=E+O

T یعنی درجه کل گراف G که یک عدد صحیح زوج است و هم‌چنین E زوج است زیرا یا E برابر صفر است که زوج است یا E مجموع اعداد deg(ui) هاست که هر یک از اینها زوج هستند، اما:   

T=E+O     O=TE

تفاضل دو عدد صحیح، زوج است در نتیجه O زوج است.

بنابر فرض به‌ازای همه مقادیر، درجه زیر فرد است:

deg(Vi)    ;    i=1,2,...,n

بنابراین O یعنی یک عدد صحیح زوج ، برابر مجموع n عدد صحیح فرد است: 

deg(Vn),...,deg(V2),deg(V1)

جمع n عدد صحیح فرد، زوج می‌باشد، بنابراین n زوج است.

به‌عنوان نمونه:

  • در یک مهمانی تعداد افرادی که با تعدادی فرد، از مهمان‌ها دست نداده‌اند، زوج است که جمله‌ای درست است.
  • تعداد تمام افرادی که به‌دفعات فرد ازدواج کرده‌اند زوج است که جمله‌ای درست است.
  • در یک دوره مسابقه فوتبال تعداد تیم‌هایی که با تعدادی فرد از تیم‌ها مسابقه داده‌اند فرد است که جمله‌ای غلط است.

نکته

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

2- اگر یک یال از گراف به‌صورت حلقه (طوقه) باشد، درجه آن راس دوبار شمارش می‌شود که در گراف‌های چندگانه مطرح است.

یادآوری می‌کنیم که طوقه، یالی است که ابتدا و انتهایش یک راس است.

به‌عنوان نمونه:

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

درجه راس v1 در گراف فوق 5 است.


3- برای محاسبه درجه یک راس باید تعداد یال‌هایی را شمرد که آن راس بر آنها واقع است.

4- با یک تعداد راس مشخص، درصورتی تعداد یال‌ها بیش‌تر می‌شود که درجه راس‌ها تا جای ممکنه بیش‌تر شود.

5- در یک نگاه ساده با q یال مشخص، هر چه درجه راس‌ها کم‌تر باشد، تعداد راس‌ها بیش‌تر است.

6- حداقل دو راس از گراف G دارای یک درجه هستند.

7- اگر p مرتبه گراف G باشد، آن‌گاه: 

0degVkp1

برحسب آن‌که degVk زوج یا فرد باشد، راس Vk زوج یا فرد است.

دریافت مثال

دنباله‌های درجات راس‌ها

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

dp,...d2,d1

 به‌طوری‌که didi+1i=1,...,p1، در این‌صورت:

d1d2...dp

آن‌گاه دنباله زیر را دنباله درجات راسهای گراف ساده G می‌نامیم:

S:d1,d2,...,dp

نکته

با توجه به تعریف گراف و مفاهیمی که از دنباله‌ها می‌دانیم، داریم:

1- وقتی که گراف ساده‌ای دارای p راس باشد، بزرگ‌ترین درجه، حداکثر p-1 است، به‌عبارت دیگر در دنباله، درجات راس‌ها همواره: 

d1p1

2- در هر گراف ساده تعداد راس‌هایی که درجه آنها فرد است، عددی زوج است پس در یک دنباله، تعداد اعداد فرد بایستی زوج باشد.

3- در یک دنباله، مجموع درجات راس‌ها باید عددی زوج باشد، زیرا:

i=1pdeg(Vi)=2q

4- دنباله S دنباله‌ای نزولی از اعداد صحیح نامنفی است.

5- حداقل در یک دنباله، دو راس متمایز وجود دارد که دارای یک درجه هستند و توجه کنید که این مطلب فقط در مورد گراف ساده برقرار است.

6- دنباله زیر از گراف G مفروض است:

d=(d1,d2,.....,dn)    ;    d1d2....dn

به‌ازای 1kn می‌توان درستی نامساوی زیر را ثابت کرد:

i=1kdikk1+i=k+1nmink,di

دریافت مثال

قضیه

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

اثبات

فرض کنیم دنباله درجات راس‌های گراف G دنباله نزولی از اعداد صحیح و نامنفی به‌صورت زیر برقرار باشد:

S:d1,d2,...,dp

در این‌صورت مطابق قضیه، درجات راس‌های یک گراف i=1pdi عددی زوج است. 

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

تذکر

اگر گراف ساده G دارای p راس باشد و p>1 ، حداقل دو راس دارای درجه یکسان می‌باشند و علت آن است که اگر درجه تمام راس‌ها متفاوت باشد، اجبارا دنباله درجات راس‌های گراف باید به‌صورت زیر باشند:

S:(p1),(p2),...,2,1,0

اما این موضوع امکان پذیر نیست، زیرا وقتی درجه یکی از راس‌ها برابر صفر باشد، یعنی p-1 راس داریم که حداکثر درجه می‌تواند به‌صورت زیر باشد: 

p11=p2

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

با توجه به موضوع فوق اگر گفته شود درجه راس‌های یک گراف تشکیل دنباله حسابی یا هندسی می‌دهند، نتیجه می‌گیریم درجه همه راس‌ها برابر است که در این حالت:

در شرایطی که دنباله درجات راس‌های یک گراف ساده، دنباله حسابی باشد، قدرنسبتش برابر صفر است.

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

دریافت مثال

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

درجه گراف ساده

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

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