3-laboratoriya mashgnaltirilgan graflar. Eng qisqa yorganish

xmlns:w="urn:schemas-microsoft-com:office:word"
xmlns="http://www.w3.org/TR/REC-html40">
3-laboratoriya mashgnaltirilgan graflar. Eng qisqa yorganish
3-laboratoriya mashgnaltirilgan graflar. Eng qisqa yorganish.


Ishdan maqsad: Talabalar graflar va ularni dasturda tasvirlashni organishlari kerak, bu algoritmlarning dasturiy realizatsiyasini amalga oshirish kolishlari kerak.
Qoyilishiga mos grafni tadqiq qilishga oid dasturni ishlab chiqishlari kerak.
Ish tartibi:

• 
  Tajriba ishi nazariy marganish;
  
• 
  Berilgan topshiriqning algoritmini ishlab chiqish;
  
• 
  C++ dasturlash muhitida dasturni yaratish;
  
• 
  Natijalarni tekshirish;
  
• 
  Hisobotni tayyorlash va topshirish.
  

Nazariy qism.
Graf - bu murakkab chiziqsiz kolamli dinamik tuzilma bo bu tugunlar(uchlar)dan iborat bosh boplam va tugunlarni birlashtiruvchi yoylar majmuidir.



Obyektlar tugun yoki graf uzellari konaltirilgan qirralar kabi ifodalanadi.




Graf turlari



Ixtiyoriy tugundan boshqa bironta tugunga murojaat mavjud bonaltirilmagan graf deyiladi (1-rasm).






Agar graf tugunlari olangan bolsa, u xolda bunday graflar yoirlikka ega bo bu qirralari (yoylari) ogirligi w_ij kabi belgilanadi.








Graflarni ifodalash usullari




Graflar nazariyasining ayrim bir belgilanishlari:



graf, V qirralar;




tugunlar soni;



graf olsa, unga ilmoqli qirra deyiladi.









Xalqa(cycle) l xisoblanadi: (4, 6, 7, 8, 3, 4)




Tugun darajasi



(vertex degree) INDISI JUFT(TOQ) QIYMATLI BO JUFT BOlmaydi.




To bu istalgan tugunlari qolgan graf xisoblanadi. (barcha tugunlar oldiruvchisi bu aynan bir tugunlar va aynan bir qirralardan tashkil topgan va mavjud grafni tolishini taliq, yoyinganligi (density):








To bu qirralar soni bolgan maksimalga teng bo bu qirralari soni tugunlar soniga yaqin boni xotirada tashkil etish mumkin va uning bashma matrisa ;

Munosabat matrisasi;

Qoyxati;

Qirralar roshma matrisasi bu n olib,

YOlsa

Aij = 0 agar i va j tugunlar birlashtirilmagan bolib, unda:

YOqnashgan boqnashmagan boNALTIRILGAN GRAF UChUN :

B_ij = -1 agar i tugun j yoyning boshi boqnashmagan bolsa

Qoyxati (qo bu A[n] massiv boshni uzellar rozida saqlaydi.

Yoylar ro qoyxatdir.





Qoshnilik royxati










Graflarni kotkazish

Grafni kotkazish (Graph traversal) rib chiqish prosedurasidir.




Ikkita usuli mavjud:



Tubiga qarab(Depth-First Search BFS)



Bu usullar berilgan V tugundan boshlab bironta konteynerni qorib chiqadi.




Tubiga qarab kollaniladi.



Eniga qarab konaltirilgan va yoshma , munosabat matrisalari va qoyxati tuzilsin.
http://hozir.org