O‘rganish. Ishdan maqsad: Talabalar graflar va ularni dasturda tasvirlashni

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:

𝑎

𝑖𝑗

= {

2, 𝑎𝑔𝑎𝑟 𝑡𝑢𝑔𝑢𝑛𝑑𝑎 𝑠𝑖𝑟𝑡𝑚𝑜𝑞 𝑏𝑜

′

𝑙𝑠𝑎,

1, 𝑎𝑔𝑎𝑟 𝑏𝑢 𝑡𝑢𝑔𝑢𝑛𝑙𝑎𝑟 𝑞𝑜

′

𝑠ℎ𝑛𝑖𝑏𝑜

′

𝑙𝑠𝑎,

0, 𝑎𝑔𝑎𝑟 𝑡𝑢𝑔𝑢𝑛𝑙𝑎𝑟 𝑞𝑜

′

𝑠ℎ𝑛𝑖 𝑏𝑜

′

𝑙𝑚𝑎𝑠𝑎.

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

Munosabat matrisalari

G grafning munosabat matrisasi bu n satr(tugunlar) va m

dan tashkil topgan V matrisa bo‘lib, unda:

YO‘NALTIRILMAGAN GRAF UChUN:

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

Bij = 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

1 1 1 1 0 0 0 0 0 0

1 0 0 0 1 1 1 0 0 0

0 1 0 0 0 0 0 1 1 0

0 0 0 0 1 0 0 0 0 1

0 0 1 0 0 0 0 0 0 0

0 0 0 0 0 1 0 1 0 0

0 0 0 1 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 1

0 0 0 0 0 0 0 0 1 0

0 0 0 0 0 0 1 0 0 0

Bu esa quyidagi ko’rinishda tasvirlanadi:

1 2 3 5 7

2 1 4 6 10

3 1 6 9

4 2 8

5 1 10

6 2 3

7 1

8 4

9 3

10 2 5

• Qo'shnilik(qo'shni tugunlar) ro'yxati Yoylar ro‘yxati (edges list) –

qo‘shni uzellar yoylaridan iborat chiziqli ro‘yxatdir.

Bu A[n] massiv bo'lib, A[i] har bir elementi i tugun bilan qo'shni tugunlar

ro'yxatini o'zida saqlaydi.

va yoylar ro‘yxati

• Yoylar ro‘yxati (edges list) – qo‘shni uzellar yoylaridan iborat chiziqli

ro‘yxatdir.

[2, 6],

[2,10],

[3, 6],

[3, 9],

[4, 8],

[5,10] ]

Xulosa: Qo’shni tugunlar va yoylar ro’yhati bir xil narsani ifodalar ekan!