Hozirgi kunga kelib diskret matematikaning qo`llanish sohasi kengayib
Download 141.24 Kb.
|
Hozirgi kunga kelib diskret matematikaning qo`llanish sohasi ken-fayllar.org
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
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
3 , u 4
5 , u 0
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. Yechimi: Har biri uchi dam oluvchilarga teng bo`lgan G grafni yasab olamiz. Bu masaladi bir darajasi 49 ga teng bo`lgan uch borligini isbotlashimiz kerak. Biron-bir u uchni eng yuqori p darajali deb qabul qilamiz. u uch bilan tutash uchlarni Ґ(u) ={ u 1 , u 2 ,…,u p } bilan belgilaymiz. v uch u uch bilan tutash bo`lsin. Agar Ґ(u) da ikkita istalgan u 1 , u 2 uchlar tutash bo`lmasa, unda to`rta uchlar u,v, u 1 , u 2 masalaning shartini qanoatlantirmaydi.(15.6-rasm) 15.6-rasm Shu sababli Ґ(u) ning uchlari juft-juft bo`lib tutash. Endi u, v, u 1 , u 2 ko`rib chiqamiz. Masala sharti bo`yicha shu uchlarning bittasi qolgan uchlar bilan tutash bo`kishi kerak. u va v tutash uchlar bo`lmaganligi sababli bizda u 1 va v 1
Aniqlash uchun u 1 uch qolgan v, u, u 2 uchlar bilan tutash bo`lsin. u 1 uch qolgan v, u va Ґ(u) ning uchlari bilan tutash bo`lganligi sababli uning darajasi u ga nisbatan ko`proq bo`ladi. Demak, G grafda darajasi 49 ga teng bo`lgan uch mavjud va lagerda bitta o`quvchi qolgan barcha o`quvchilarni taniydi. 40
7. Uch o`lchamli fazoda shunday 8 ta nuqta tanlanganki, ularning hech qaysi
Download 141.24 Kb. Do'stlaringiz bilan baham: |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling