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

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

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

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

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

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

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

تمرین

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

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

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


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

تمرین

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

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

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

Δ=5δ=2

تمرین

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

گراف شكل فوق چند راس فرد وجود دارد؟

راس فرد به راسی گفته می‌شود كه درجه اش فرد باشد.


پس گراف فوق دو راس فرد دارد.

تمرین

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

ماكزيمم درجه و مينيمم درجه در بين درجه های راس های گراف داده شده در شكل فوق را بنویسید.

δ=1  ,  Δ=5

تمرین

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

V=a,b,c,d,e

چند گراف G وجود دارد كه داشته باشيم:

dega=degb=2degc=degd=dege=4

چون درجه هر يک از راس های e,d,c برابر 4 است، پس هر كدام از اين راس ها به چهار راس ديگر متصل است.


بنابراين راس a به  سه راس e,d,c متصل است.


در نتيجه داریم:


dega3


كه خلاف فرض است، پس چنين گرافی وجود ندارد.

تمرین

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

V=a,b,c,d

آيا گرافی وجود دارد كه داشته باشیم:

dega=degb=1degc=degd=3

چون درجه c عدد 3 است پس سه یال از c به a,b,d وجود دارد.


به‌همين دليل سه يال از d به a,b,c وجود دارد.


بنابراين گراف G بايد به‌صورت زير باشد:



بنابراين داریم:


dega2degb2


كه خلاف فرض است، بنابراين گرافی با مشخصات فوق وجود ندارد.

تمرین

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

V=v1,...,v4

E=(v1,v2),(v1,v3),(v4,v1),(v3,v4),(v2,v3),(v4,v3)

در اين‌صورت درجه راس v3 را به‌دست آورید.

چون راس v3 در سه زوج مرتب، مولفه دوم قرار گرفته است، لذا سه يال به آن وارد شده است:


deg(v3)=3

تمرین

در گراف از مرتبه 8 و اندازه 25 حداقل چند راس از درجه  وجود دارد؟

دراين گراف بايد =7 باشد.


اگر <7 باشد، آن‌گاه تعداد يال ها كمتر از 25 می‌شود.


اگر همه راس ها از درجه 7 باشد، مجموع درجات برابر است با:


7×8=56


در صورتی كه در اين گراف مجموع درجات برابر است با:


2×25=50


حال بايد اين اختلاف 6 واحد را بين حداكثر تعداد راس ها توزيع كرد تا حداقل تعداد راس ها با درجه  به‌دست آيد.


يعنی دنباله گرافی چنين گرافی به‌صورت زیر است.


v,v,y,y,y,y,y,y


كه دارای 2 راس از درجه =7 است.

دریافت مثال

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

قضیه

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

i=1pdegVi=2q

اثبات

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

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

تمرین

گراف ساده G از مرتبه شش، سه راس از درجه چهار و سه راس از درجه دو دارد، اندازه آن را به‌دست آورید.

i=16deg(Vi)=2q

(4+4+4)+(2+2+2)=2q

18=2qq=9

گراف ساده G دارای 24 یال می‌باشد، اين گراف 3 راس از درجه دو 3 راس از درجه شش و بقيه راس ها از درجه سه هستند، اين گراف چند راس دارد.

deg(Vi)=2q3×2+3×6+3k=2(24)k=8


تعداد راس ها برابر است با:

3+3+8=14

اگر اندازه گراف ساده G (تعداد یال های گراف) هشت باشد، مجموعه درجات تمام راس های G را به‌دست آورید.

i=1pdegVi=2q   ;   q=8i=1pdegVi=2×8i=1pdegVi=16

تمرین

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

در گراف فوق تعداد راس ها، يال ها و درجه هر راس را مشخص كنيد و نشان دهيد كه مجموع درجات رئوس دو برابر تعداد يال ها است.

V(G)=a,b,c,d,ep=V(G)=5


E(G)=a,b,a,c,a,d,b,c,b,e,c,d,c,eq=E(G)=7


5 راس و 7 يال به در گراف فوق موجود است.


degVi=3+3+4+2+2=14=2(7)

تمرین

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

در گراف فوق، تعداد يال ها را با مجموع درجه های راس ها مقايسه نمائيد.

ابتدا درجه همه راس ها را می‌يابيم:


deg(a)=deg(c)=4deg(b)=deg(d)=3deg(e)=5deg(f)=1


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


deg(a)+deg(c)+deg(b)+deg(d)+deg(e)+deg(f)=4+4+3+3+5+1=20


كه اين مقدار دو برابر تعداد يال ها است.


q=10

تمرین

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

V(G)=A,B,C,D

m ،درجه راس های G را در حالات زیر به‌دست آورید.

E(G)=A,B,A,C,A,D,B,D

مجموع راس های گراف G دو برابر تعداد يال های آن است: 


i=1pdeg(vi)=2q


اين گراف 4 يال دارد در نتيجه:


m=2(4)=8

E(G)=A,B,A,C,A,D,B,A,B,BC,B,C,D

اين گراف 7 يال دارد در نتيجه:


m=2(7)=14

تمرین

در گرافی با 9 يال، درجه تمامی راس ها برابر 3 می‌باشد.

تعداد راس ها چند است؟

degVi=2q3n=2×9n=6

تمرین

فرض كنيد G يک گراف ساده است.

در این گراف V، 12 عضو دارد و درجه هر راس آن برابر با 4 است.

در اين‌صورت G چند يال دارد؟

مجموع درجه های راس های يک گراف دو برابر تعداد يال هاست.


پس اگر q تعداد يال های گراف مورد نظر باشد، آن‌گاه:


degVi=2q12×4=2qq=24

تمرین

درجه كليه رئوس يک گراف از مرتبه 6 برابر 3 است.

اين گراف چند يال دارد؟

i=1pdegVi=2qi=163=2q


3×6=2qq=9

تمرین

گرافی دارای 4 راس از درجه 5 بوده و مرتبه و اندازه‌اش به‌ترتيب 6,14 است.

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

degvi=2q


4×5+x=2×14    ;    p=6q=14


x=8

تمرین

گراف G دارای 10  يال و دو راس از درجه 4 و بقيه راس ها از درجه 3 می‌باشند.

تعداد راس های آن را به‌دست آورید.

deg(vi)=2q2×4+k×3=2×10


k×3=12k=4


تعداد راس ها:


2+k=2+4=6

تمرین

گراف ساده G دارای 10 يال و 2 راس از درجه 4 و بقيه راس ها از درجه 3 می‌باشد.

مرتبه اين گراف را به‌دست آورید.

فرض می‌كنيم تعداد راس های با درجه 3 برابر n است:


deg(Vi)=2q2×4+3×n=20


8+3n=20n=4


پس تعداد راس های با درجه 3 برابر 4 است و 2 راس از درجه 4 نيز وجود دارد، بنابراين تعداد كل راس ها برابر 6 می‌باشد.

تمرین

يک گراف از مرتبه 12 و اندازه 16 فقط دارای راس های درجه 2 و درجه 3 است.

اين گراف چند راس از درجه 2 دارد؟

p=x+y=12degVi=2q2x+3y=2×16


x+y=122x+3y=32


x=4y=8


اين گراف 4 راس درجه 2 دارد.

تمرین

آيا ممكن است در يک گروه 9 نفری، هر شخص به تنهايی با 5 نفر ديگر دوست باشد؟

خير. اگر هر نفر نماينده يک راس باشد و با 5 نفر دوست باشد يعنی درجه اين نقطه 5 است.


degVi=5+5+5+...+59=45


در تساوی فوق، مجموع درجات 45 است که عددی فرد است.


می‌دانيم مجموع كل درجه يک گراف همواره زوج است.

تمرین

در گرافی با 31 راس كه درجه هر راس حداكثر 3 می‌باشد.

بيشترين تعداد يال را به‌دست آورید؟

هر 31 راس نمی‌تواند از درجه فرد باشد چون تعداد رئوس ازدرجه فردشظ بايد زوج باشد.


پس حداكثر تعداد يال وقتی ايجاد می‌شود كه 30 راس از درجه 3 و 1 راس از درجه 2 داشته باشد:


degVi=2q303+12=2q


92=2qq=46

تمرین

گرافی 20 يال دارد كه درجه هر راس آن حداقل 4 است.

بيشترين تعداد راس را بیابید.

degVi=2q4x=40x=10


چون حداقل درجه هر راس 4 است، پس حداكثر تعداد راس ها برابر 10 است.

تمرین

فرض كنيد G گرافی است كه درجه هر راس آن 6 يا 7 است.

ثابت كنيد تعداد راس های درجه 6  اين گراف برابر است با:

7p2q

فرض كنيم x تعداد راس های با درجه 6 در این گراف است.


y تعداد راس های با درجه 7 در اين گراف است.


پس اين گراف x+y راس دارد، بنابراين:


p=x+yy=px


i=1pdegVi=2q


6+6+...+6+7+7+...+7=2q


6x+7y=2q    ;    y=px6x+7px=2q


6x+7p7x=2qx=2q7px=7p2q

تمرین

گرافی با 23 راس و =5 را در نظر بگیرید.

اين گراف حداكثر چند يال می‌تواند داشته باشد؟

حداكثر تعداد يال ها در اين گراف وقتی است كه همه راس ها حداكثر درجه يعنی درجه 5 را داشته باشند.


اما چون اين گراف 23 راس دارد، بنابراين هر 23 راس نمی‌تواند از درجه 5 باشند.


در نتيجه بايد 22 راس از درجه 5 و يک راس ديگر از درجه 4  باشد.


در اين‌صورت حداكثر تعداد يال ها برابر است با:


i=1pdegVi=2q22(5)+1(4)=2qq=57

تمرین

17 نفر به سفر می‌روند و قبل از سفر قرار می‌گذارند هركس به پنج نفر ديگر نامه بفرستد.

آيا امكان دارد هر كس به آن 5 نفری نامه بفرستد كه از آنها نامه دريافت می‌كند؟

خیر.


اگر گرافی رسم كنيم كه راس های آن 17 نفر مذكور و يال های آن معرف فرستادن و دريافت نامه باشد، در اين‌صورت (اگر هركس به همان 5 نفری نامه بفرستد كه از آنها دريافت كرده) مجموع درجه های راس ها برابر است با:


17×5=85


زيرا هر راس از درجه 5 می‌باشد.


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


پس اين مجموع نمی‌تواند عدد 85 باشد، لذا چنين گرافی وجود ندارد.

تمرین

كدام‌يک از وضعيت‌های زير می‌تواند وجود داشته باشد؟

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

17×1=17


مجموع درجه های راس های آن عددی فرد است. 


برای این وضعیت گرافی قابل رسم نیست.

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

15×3=45


مجموع درجه های راس های آن عددی فرد است. 


برای این وضعیت گرافی قابل رسم نیست.

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

27×4=108


تنها برای اين وضعيت می‌توان گرافی رسم كرد كه مجموع درجه های راس های آن عددی زوج است.

دریافت مثال

قضیه

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

δ2qpΔ

اثبات

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

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


(1ip)

δdegViΔi=1pδi=1pdegVii=1pΔ

δ+δ+...+δi=1pdegViΔ+Δ+...+Δ

pδ2qpΔpδp2qppΔpδ2qpΔ

تمرین

در گرافی با 35 راس كه ماكزيمم درجه آن سه است، بيش‌ترين تعداد يال را تعيين كنيد. 

δ2qpΔ2qpΔ2q35×3

q35×32q52.5q=52

تمرین

گرافی از مرتبه 11 و داریم:

Δ=6δ=4

اندازه اين گراف در چه بازه‌ای قرار دارد؟

δ2qpΔ42q11622<q<33

تمرین

در گراف G حداقل درجه راس ها و حداكثر درجه راس ها دو عدد متوالی هستند.

اگر اين گراف دارای 7 راس و 18 يال باشد:

حداقل درجه راس ها را به‌دست آورید؟

Δ=δ+1δ2qpΔ


δ2qpδ+1    ;    p=7q=18


δ2×187δ+1δ367δ+1


53676δ=5

تمرین

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

اگر اين گراف 2n راس داشته باشد و تعداد يال هايش 11 باشد:

حدود n را به‌دست آورید.

δ2qpΔ12×112n3132n221


13n111113n11


چون n مقادير طبيعی را اختيار می‌كند، پس:


3n11

تمرین

در يک گراف ساده، بزرگ ترين و كوچک ترين درجه در بين درجه های راس ها به‌ترتيب 2,5 می‌باشد.

اگر اندازه اين گراف عدد 11 باشد:

بيش ترين و كم ترين عدد در مورد مرتبه اين گراف را به‌دست آورید.

δ2qpΔ22×15p5


15p30126p15

تمرین

در يک گراف ساده داریم:

δ=Δ=2

اگر مرتبه گراف 5 باشد، آن‌گاه اندازه گراف را به‌دست آورید.

δ2qpΔ22q52


2q5=22q=10q=5

تمرین

فرض كنيد G گراف ساده ای با 17 يال باشد.

اگر در اين گراف داشته باشيم δ=3 :

اين گراف حداكثر چند راس دارد؟

δ2qpΔ2qpδ


2qpδ217p3


p343p11maxp=11

دریافت مثال

قضیه

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

اثبات

فرض کنید 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 زوج یا فرد است.

تمرین

بيش ترين تعداد يال برای گراف مرتبه 7 كه درجه هر راس آن حداكثر 3 باشد را به‌دست آورید.

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


در اين تمرین بهتر است تعداد راس های درجه 3 ماکزیمم باشد.


با توجه به اين‌كه هر 7 راس نمی‌توانند درجه 3 باشند (مجموع درجات نبايد فرد باشد) می‌توان 6 راس را از درجه 3 و يک راس را از درجه 2 در نظر گرفت.


degVi=6×3+1×2=2qq=10

تمرین

در يک گراف با اندازه 10، درجه هر راس حداقل 2 می‌باشد.

ماکزیمم تعداد راس ها را به‌دست آورید.

در يک گراف ساده با q يال مشخص، هر چه درجه راس ها كم تر باشد تعداد راس ها بيش تر خواهد بود.


degVi=2qdegVi=2×10degVi=20


اگر مجموع درجات راس های این گراف 20 باشد و درجه هر راس حداقل 2 باشد، می‌توانيم ماکزیمم 10 راس درجه 2 داشته باشيم.

دریافت مثال

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

اگر گراف ساده 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

تمرین

گرافی رسم كنيد كه دنباله درجات راس های آن به‌صورت زیر باشد.

3,3,2,2


dega=degc=3degb=degd=2

تمرین

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

دنباله درجات راس های گراف شكل فوق را بنويسيد.

ابتدا درجه هر راس را می‌نویسیم:


dega=degd=degg=3degb=4  ,   degc=1dege=degf=2


بنابراين دنباله درجات راس های اين گراف عبارت است از:


4,3,3,3,2,2,1

تمرین

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

دنباله درجات راس های گراف شكل فوق را بنويسيد.

3,2,2,1,1,1

تمرین

تعداد يال های گرافی با دنباله درجات راس های زیر را به‌دست آورید.

5,3,2,2,1,1,0

می‌دانيم كه مجموع جملات دنباله درجات راس های يک گراف دو برابر تعداد يال هاست.

i=1pdi=2q

5+3+2+2+1+1+0=2q

q=7

دریافت مثال

قضیه

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

اثبات

فرض کنیم دنباله درجات راس‌های گراف 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 مثال ها و جواب ها

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