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!
Do'stlaringiz bilan baham: |