3-laboratoriya mashg‘uloti Graflar va ularni dasturda tasvirlash. Graflar bilan ishlash algoritmlari. Yo‘naltirilgan graflar. Eng qisqa yo‘lni topish algoritmlarini o‘rganish. Ishdan maqsad

3-laboratoriya mashg‘uloti

Graflar va ularni dasturda tasvirlash. Graflar bilan ishlash algoritmlari.Yo‘naltirilgan graflar. Eng qisqa yo‘lni topish algoritmlarini o‘rganish.

Ishdan maqsad: Talabalar graflar va ularni dasturda tasvirlashni o‘rganishlar kerak. Graflar ustida amallar bajarish algoritmlarini tadqiq qilishlari va o‘rganishlari kerak, bu algoritmlarning dasturiy realizatsiyasini amalga oshirish ko‘nikmasiga ega bo‘lishlari kerak.

Qo‘yilgan masala: Har bir talaba topshiriq varianti olib, undagi masalaning qo‘yilishiga mos grafni tadqiq qilishga oid dasturni ishlab chiqishlari kerak.

Ish tartibi:

• 
  Tajriba ishi nazariy ma’lumotlarini o‘rganish;
  
• 
  Berilgan topshiriqning algoritmini ishlab chiqish;
  
• 
  C++ dasturlash muhitida dasturni yaratish;
  
• 
  Natijalarni tekshirish;
  
• 
  Hisobotni tayyorlash va topshirish.
  

Topshiriq

Xar bir talaba yo‘naltirilgan va yo‘naltirilmagan graf yasasin.Tugunlar soni 10-12 ta. Unga mos qo‘shma , munosabat matrisalari va qo‘shnichilik va yoylar ro‘yxati tuzilsin.

Yo’naltirilgan Graf:


Yo’naltirilmagan graf:

1. 
   Qo’shma matrissasi – tugunlarga nisbatan o’zaro bog’lovchi umumiy qirra bor yo’qligini ifodalovchi:
   

	1	2	3	4	5	6	7	8	9	10
1	0	1	1	0	1	0	1	0	0	0
2	1	0	0	1	0	1	0	0	0	1
3	1	0	0	0	0	1	0	0	1	0
4	0	1	0	0	0	0	0	1	0	0
5	1	0	0	0	0	0	0	0	0	1
6	0	1	1	0	0	0	0	0	0	0
7	1	0	0	0	0	0	0	0	0	0
8	0	0	0	1	0	0	0	0	0	0
9	0	0	1	0	0	0	0	0	0	0
10	0	1	0	0	1	0	0	0	0	0

Munosabat matrisalari

G grafning munosabat matrisasi bu n satr(tugunlar) va m ustunlar(qirralar) dan tashkil topgan V matrisa bo‘lib, unda:

YO‘NALTIRILMAGAN GRAF UChUN:

B_ij = 1 agar i tugun j qirra bilan to‘qnashgan bo‘lsa

B_ij = 0 agar i tugun j qirra bilan to‘qnashmagan bo‘lsa

	1-2	1-3	1-5	1-7	2-4	2-6	2-10	3-6	3-9	4-8	5-10
1	1	1	1	1	0	0	0	0	0	0	0
2	1	0	0	0	1	1	1	0	0	0	0
3	0	1	0	0	0	0	0	1	1	0	0
4	0	0	0	0	1	0	0	0	0	1	0
5	0	0	1	0	0	0	0	0	0	0	1
6	0	0	0	0	0	1	0	1	0	0	0
7	0	0	0	1	0	0	0	0	0	0	0
8	0	0	0	0	0	0	0	0	0	1	0
9	0	0	0	0	0	0	0	0	1	0	0
10	0	0	0	0	0	0	1	0	0	0	1