Hozirgi kunga kelib diskret matematikaning qo`llanish sohasi kengayib

Yechimi: G grafni yasab olamiz. Har bir uchining darajasi 6 ga teng bo`lsin. G 

grafning  6  ta  uchini  ko`rib  chiqamiz:  u

1

,  u

2

,…,u

p

.  Shart  bo`yicha  shunday  u

0

  uch 

borki, bu uch qolganlari bilan o`zaro ulangan (15.4-rasm). 

  Endi 6 ta u

1

, u

2

, u

3

, u

4

, u

5

, u

0

 uchlarini olamiz. Shartga asosan shu uchlarni 

bitta  nuqtada  yig`ilgan  uchi  mavjud.  Bu  yig`ib  turuvchi  uch  sifatida  faqat  u

6

  ni 

olish mumkin, chunki u

0

 ni olsak, uchlarining darajasi 6 dan oshib ketadi. Shu kabi 

har  bir  juft  uchlarning  o`zaro  tutash  ekanligi  isbotlanadi.  Shu  sababli  G  graf  K

7

 

grafi bo`ladi va korxonada 7 ta ishchi borligini bildiradi. 

---

39

 

 

 

15.5-rasm 

6. Lagerda 50 ta dam oluvchi o`quvchilar bor. Ma’lumki, istalgan to`rttasining 

ichidan  kamida  bittasi  qolgan  uchtasini  taniydi.  Shu  lagerda  bir  bola  qolgan 

hammasini tanishini isbotlang.