Hozirgi kunga kelib diskret matematikaning qo`llanish sohasi kengayib


Download 0.83 Mb.
Pdf ko'rish
bet25/29
Sana05.01.2022
Hajmi0.83 Mb.
#224188
1   ...   21   22   23   24   25   26   27   28   29
Bog'liq
graflar nazariyasi va mundarija

Yechimi:  Har  bir  ishchini  G  grafning  uchi  qilib  olamiz.  Bu  masalada  hamma 

uchlarning darajasi bir hil ekanligini isbotlash kerak.  



u va v o`zaro uchlari tutashgan graf bo`lsin. Masala shartiga binoanu

1

u



2

,…,u



n

 

uchlari u uch bilan o`zaro tutash va v uch bilan tutash bo`la olmaydi. Tutashmagan 



u

1

 va v uchlarni ko`rib chiqamiz. Ular tutashgan u uchdan boshqa yana bir nuqtada 



uchrashishlari  kerak, masalan  v

1

 da, shunda  bu uch  u uch  bilan  tutash bo`lmaydi. 



(1-rasm) 


38

 

 



 

15.3- rasm 

Shu tariqa har bir i (2≤ip) ga shunday v

i

 uch toplidaki, u u

i

 va v uchlar bilan 

tutash lekin u bilan tutash bo`lmaydi. Shu sababli d(v)≥d(u). Shu kabi d(v)≤d(u) ni 

isbotlasak bo`ladi. Demak, d(v)=d(u). (2-rasm) 

 

15.4-rasm 



5. Biron bir korxonada ma’lumki, istalgan ishchi shu korxonadagi oltita ishchi 

bilan  tanish.  Oltita  kishidan  iborat  guruhda  bir  ishchi  qolgan  barchasini  taniydi. 

Korxonada nechta ishchi ishaydi. 


Download 0.83 Mb.

Do'stlaringiz bilan baham:
1   ...   21   22   23   24   25   26   27   28   29




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling