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

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

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

در هر گراف ساده 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)=5E(G)=ab,ac,ae,ad,bc,edq=E(G)=6

دریافت مثال

نکته

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

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

p1+8q2

دریافت مثال

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

قضیه

هر گراف ساده که 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)=00qp20qp(p1)202qp(p1)

دریافت مثال

قضیه

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

2p2=2p(p1)2

اثبات

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

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

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

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

2p2=2p(p1)2

تمرین

در گراف ساده G=(V,E) که مجموعه راس‌های آن V=a,b,c می‌باشد، تعداد گراف آنها را رسم کنید.

p=3


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

2p2=2pp12=23×22=23=8


 با سه راس a,b,c جمعا 8 گراف می‌توان ساخت:


 مرتبه و اندازه گراف ساده - پیمان گردلو

دریافت مثال

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

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

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

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