مرتبه و اندازه گراف ساده

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

تعریف مرتبه و اندازه گراف ساده

در هر گراف ساده G=(V,E):

تعداد اعضای VG را مرتبه G می‌نامیم و با p  نمایش می‌دهیم، یعنی:

p=V(G)

تعداد اعضای EG را اندازه G می‌نامیم و با q نمایش می‌دهیم، یعنی:

q=E(G)

تمرین

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

مرتبه و اندازه G را بنویسید. 

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


E(G)=ab,ac,ae,ad,bc,edq=E(G)=6

تمرین

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

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

p=7q=6

تمرین

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

V=a,b,c,dE=ab,ac,ad,bc,dc

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

p=4q=5

دریافت مثال

نکته

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

2- اگر گراف ساده‌ای q یال داشته باشد، حداقل تعداد راس‌های آن برابر است با:

p1+8q2

تمرین

آیا جمله زیر جمله درستی است؟

حداكثر مرتبه برای گرافی با 6 يال برابر 7 است.

خیر.


برای گراف ساده با q يال حداكثر مرتبه p را نمی‌توان تعيين كرد زيرا به هر تعداد می‌توانيم راس از درجه صفر داشته باشيم.

دریافت مثال

قضایای مرتبه و اندازه گراف ساده

قضیه

هر گراف ساده که p راس دارد، حداکثر تعداد یال‌هایش p2 و حداقل تعداد یال‌هایش صفر است: 

0qp20qpp12

اثبات

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

چون هر یال متناظر با یک زیر مجموعه دو عضوی از راس‌ها است، پس در مورد یک مجموعه p عضوی، حداکثر تعداد یال‌ها برابر است با تعداد زیرمجموعه‌های 2 عضوی مجموعه VG که p عضو دارد.

این تعداد برابر است با تعداد انتخاب‌های 2 شی از میان p یعنی p2

یادآوری می‌کنیم که:

nr=n!r!nr!p2=p!r!p2!p2=pp1p2!2!p2!

p2=pp12!p2=pp12

نکته

نتایج قضیه فوق به‌شرح زیر است:

max(q)=p2=pp12    ;    min(q)=0

0qp20qp(p1)202qp(p1)

تمرین

گراف ساده را با مشخصات زیر در نظر بگیرید:

G=V,EV=a,b,c,d,e

این گراف حداقل و حداكثر چند يال دارد؟

minq=0maxq=p(p1)2=5(4)2=10

تمرین

حداكثر اندازه يک گراف ساده مرتبه 8 چند است؟

p=8maxq=pp12=872=28

در ميان گراف هايی كه 66 يال دارند، گرافی كه تعداد راس های آن كم‌ترين است، داراي چند راس است؟

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

02qpp1


02×66pp1    ;    q=66


p2p1320p12p+110p12p11


چون مقدار منفی برای يال و راس معنی ندارد پس p11 قابل قبول نيست و فقط p12 قبول است، بنابراين حداقل رئوس چنين گرافی p=12 است.

تمرین

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

V=a,b,c,d

چند گراف ساده G وجود دارد كه q=2 و يكی از يال های آن ab باشد؟

تعداد گراف های مورد نظر برابر است با:


421=61=5


دریافت مثال

قضیه

تعداد گراف‌های ساده با p راس برابر است با: 

2p2=2p(p1)2

اثبات

فرض کنید مجموعه زیر ، مجموعه راس‌های گراف G باشد:

V(G)=V1,V2,...,Vp

اگر همه عضوهای VG به‌هم متصل شده باشند، آن‌گاه p2 یال خواهیم داشت. 

چون در گراف‌های مختلف ممکن است، هیچ یا یک یا دو یا ... یا p2 یال داشته باشیم، بنابراین تعداد گراف‌های مختلف برابر است با تعداد زیر‌مجموعه‌های یک مجموعه p2 عضوی، یعنی:  

2p2=2p(p1)2

تمرین

گراف های ساده با 4 راس زیر را در نظر بگیرید. 9

u,v,w,t

اگر دو يال كه يكی از آنها u,v باشد، تمام گراف های آن را رسم کنید.

در مجموع، تعداد زير مجموعه از اين نوع گراف داريم كه عبارتند از:


42=6


w,t,v,t,v,w,u,t,u,w,u,v


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


بنابراين هريک از 5 زير مجموعه باقيمانده را می‌توان برای يال دوم انتخاب كرد.


تمرین

چند گراف ساده G وجود دارد كه مجموعه راس های آن 4 عضو داشته باشد؟ 

p=4


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


2p2=2pp12=24×32=26=64

دریافت مثال

خرید پاسخ‌ها

مرتبه و اندازه گراف ساده

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

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