4. Laboratoriya mashg’uloti Mavzu: Kommivoyajer haqidagi masala Ishning maqsadi

Mustaqil yechish uchun masalalar

1. 
   Grafdagi cho'qqilar to'plami, agar bu to'plamning ikkita uchi bir chekka bilan bog'lanmagan bo'lsa, mustaqil deyiladi. Boshqacha qilib aytadigan bo'lsak, ushbu to'plam tomonidan induktsiya qilingan pastki grafik izolyatsiya qilingan tepalardan iborat. Shuningdek, ba'zida grafning har bir chekkasi mustaqil to'plamning ko'pi bilan bitta cho'qqisiga to'g'ri keladi, deb ham aytiladi. Tanib olish muammosi (hal qilish muammosi) quyidagicha ko'rinadi: berilgan G grafi k o'lchamdagi mustaqil to'plamga egami?
   
2. 
   Sayohatchi sotuvchi muammosi (yoki ingliz tilidagi Sayohatchi sotuvchi muammosidan TSP) eng mashhur kombinatoriy optimallashtirish muammolaridan biri bo'lib, u belgilangan shaharlardan kamida bir marta o'tib, keyin asl shaharga qaytib keladigan eng foydali marshrutni topishdan iborat.
   
3. 
   Ochko'z algoritm yordamida sig'imi W=17 bo'lgan ryukzak masalasini yeching.
   

   k	1	2	3	4	5
   C	4	5	1	3	2
   P	5	7	6	8	4

4. 
   Ismingizni shifrlash va shifrini ochish uchun Huffman kodini kompilyatsiya qiling.