مرجع دانلود پاورپوینت های درسی

حجم فایل : 226.4 KB
نوع فایل : پاور پوینت
تعداد اسلاید ها : 43
بنام خدا نظريه گراف گراف ساده : تست : با توجه به تعريف مرتبه و اندازه کدام درست است ؟
1- P عضو N و qعضو N
2- P عضو Zو qعضو N
3-P عضو N و qعضو Z
4-P عضو N و qعضو ٌٌٌٌW


 deg (vi)=2q
i=1 p تعداد راس های فرد در هر گراف ساده عددی است زوج : تعداد يالها در گراف کامل : p(p-1)/2 درجه هر راس در گراف کامل : q=p-1 در گراف r منتظم از مرتبه p مجموع درجات برابر است با : p*r=2q نکته: K1=k1 تست: تست : در گراف 8 منتظم از مرتبه 11 چند يال وجود دارد ؟
1-36
2-42
3-44
4-43 تست: تست :در گرافی منتظم از مرتبه 10 ، 35 يال وجود دارد . درجه هر راس چند است ؟
1-7
2-8
3-9
4-10 تمرین: تمرين : چند گراف 5 منتظم از مرتبه 9 وجود دارد ؟ هر گراف کامل kp گرافی است p-1 منتظم . بنابراین داريم : ==p-1 رابطه بین مرتبه و اندازه و بیشترین درجه و کمترین درجه : <=2q/p<= میانگین درجات راس ها : 2q/p تعداد مسیرهای موجود بین دو راس a و b از گراف کامل kp : (p-2)!((1/0!)+(1/1!) +…+(1/(p-2)!) تعداد مسیرهای موجود بین دو راس a و b از گراف کامل kp : [(p-2)!*e] e=2/71 تعداد مسیرهای غیر صفر موجود در گراف کامل kp : [(p-2)!*e]*p(p-1)/2 e=2/71 تعداد مسیرهای به طول r بین دو راس a و b موجود در گراف کامل kp : (p-2)!/(p-r-1)! e=2/71 1<=r<=p-1 تعداد دور های به طول r موجود در گراف کامل kp : ( )*(r-1)!/2 3<=r<=p P r تعداد دور های موجود در گراف کامل kp : 3<=r<=p P r  ( )*(r-1)!/2 r=3 p دنباله درجات : اگر درجه راسهای گراف را به صورت دنباله ای نزولی بنويسم گويند . S:=d1,d2,d3,…,dp برای پیدا کردن اندازه یا q می توان نوشت : q=(d1,d2,d3,…,dp)/2 در دنباله درجات نظیر گراف از مرتبه p : d1<=p-1 دنباله درجات : در دنباله درجات اگر حداکثر درجه يا d1 برابر p-1 باشد آنگاه در اين دنباله راس با درجه صفر نداريم . اگر در دنباله درجات n تا صفر داشته باشيم : انگاه حداکثر درجه در دنباله درجات p-1-r است . درخت : اگر و فقط اگر همبند و بدون دور باشد . تمرين : تعداد درختهای از مرتبه 6 چند تا است ؟ ج : متاسفانه راهی جز رسم نداريم. 6 عدد . ويژگی های درخت : 1- در هر درخت با بيش از يک راس حداقل دو راس از درجه يک وجود دارد .
2- در هر درخت بين دو راس حداقل يک مسير وجود دارد . تعداد مسيرهای با طول غير صفر : ( ) P 2 تعداد مسيرهای با طول صفر و غير صفر : ( ) P+1 2 رابطه بین تعداد راسها و یالها : P=q+1  deg (vi)=2q=2p-2
i=1 p مجموع درجات راسها در هر درخت : تست: بين هر دو راس از گراف G دقيقاً يک مسير وجود دارد . اگر اين گراف شامل 7 راس باشد از درجه 1 و پنچ راس از درجه 2 و K راس از درجه 3 باشد ، K کدام است ؟
1- 4
2-5
3-3
4-6 نکته: اگر در درخت max درجه برابر k باشد ، انگاه اين درخت حداقل k راس از درجه 1 دارد . نکته...