Mavzu: Bog‘langan graflarga marshrutlar, ularni narxi bo‘yicha baholash. “Xasis” algoritmlar. Eng qisqa marshrutni aniqlash algoritmi. Uni variantlar soni bo`yicha hajmini baholash. Maqsad

Amaliy topshirig‘i sharti. Quyida tasvirlangan graf uchun minimal narxli daraxt skeletini qurish usullaridan Primo usuli yordamida yechilsin va dasturini tuzilsin.

Prim algoritmini amalga oshirish bosqichlari quyidagicha:

1. 
   Minimal uzunlikdagi daraxtni tasodifiy tanlangan tugun bilan boshlang.
   
2. 
   Daraxtni yangi tugunlar bilan bog'laydigan barcha qirralarni toping, minimalini toping va daraxtga qo'shing
   
3. 
   Minimal daraxt daraxti olinmaguncha, 2-bosqichni takrorlang
   

tasvir	U tanlangan tugunlar to’plami	(u,v)yoylar	v\u tanlanmagan tugunlar	izox
	{}		{A,B,C,D,E,F,G}	Dastlab daraxt tugunlar to’plami bo’sh
	{D}	(D,A) = 5 V (D,B) = 9 (D,E) = 15 (D,F) = 6	{A,B,C,E,F,G}	Ilk tugun sifatida Dolindi. Unga tegishli yoylar A,B,E,F tugunlarga olib boradi. Ularning minimal yoyligini tanlaymiz. ya’ni A
	{A,D}	(D,B) = 9 (D,E) = 15 (D,F) = 6 V (A,B) = 7	{B,C,E,F,G}
	{A,D,F}	(D,B) = 9 (D,E) = 15 (A,B) = 7 V (F,E) = 8 (F,G) = 11	{B,C,E,G}
	{A,B,D,F}	(B,C) = 8 (B,E) = 7 V (D,B) = 9 sikl (D,E) = 15 (F,E) = 8 (F,G) = 11	{C,E,G}	(D,B)yoy tanlansa xalqa xosil bo’ladi. Shuning uchun uni tanlay olmaymiz.
	{A,B,D,E,F}	(B,C) = 8 (D,B) = 9 sikl (D,E) = 15 sikl (E,C) = 5 V (E,G) = 9 (F,E) = 8 sikl (F,G) = 11	{C,G}
	{A,B,C,D,E,F}	(B,C) = 8 sikl (D,B) = 9 sikl (D,E) = 15 sikl (E,G) = 9 V (F,E) = 8 sikl (F,G) = 11	{G}
	{A,B,C,D,E,F,G}	(B,C) = 8 sikl (D,B) = 9 sikl (D,E) = 15 sikl (F,E) = 8 sikl (F,G) = 11 sikl	{}	Grafdagi barcha tugunlar tekshirib bo’ldi.