“Ma’lumotlar tuzilmasi va algoritmlar” fanidan 1-hafta laboratoriya ishi bajarishga namuna

Graflarni tavsiflash. Qo‘shnilik matritsasi

№ tugunlar	1	2	3	4	5
1	0	1	0	0	1
2	1	0	1	1	1
3	0	1	0	1	0
4	0	1	1	0	1
5	1	1	0	1	0

Vaznsiz yo‘naltirilmagan graf

№ tugun	1	2	3	4
1	0	1	0	1
2	0	0	1	1
3	0	0	0	0
4	0	0	1	0

Vaznsiz yo‘naltirilgan graf
Graflarni tavsiflash. Qo‘shnilik matritsasi

№ vershina	1	2	3	4	5
1	0	40	0	0	18
2	40	0	22	6	15
3	0	22	0	14	0
4	0	6	14	0	22
5	18	15	0	20	0

Vaznli yo‘naltirilmagan graf

№ vershina	a	b	c	d	e
1	1	1	0	0	0
2	1	0	1	1	0
3	0	0	0	1	1
4	0	1	1	0	1

Graflarni tavsiflash. Qo‘shnilik matritsasi

№ vershina	a	b	c	d	e
1	1	-1	0	0	0
2	-1	0	1	1	0
3	0	0	0	-1	-1
4	0	1	-1	0	1

Vaznli yo‘naltirilgan graf

Topshiriqlar:

Quyidagi berilgan berilgan grafning qo’shnilik matritsasini hosil qiling, cho’qqi va qirra ma’lumotlarini chop qiluvchi dastur tuzing?

E’tiboringiz uchun rahmat!!!

Laboratoriya topshiriqlarini vaqtida bajaring va mustaqil bilimga ega bo’lin!!!

“Ma’lumotlar tuzilmasi va algoritmlar” fanidan 9-LABORATORIYA ISHI BAJARISHGA NAMUNA (2-kurslar uchun)

Fan o‘qituvchisi: kat.o‘q. Kudratov R.B.

Eng qisqa yo'l muammosi

Eng qisqa yo'l muammosi grafdagi ikkita nuqta (cho'qqi) orasidagi eng qisqa yo'lni (zanjirni) topish muammosi bo'lib, unda yo'lni tashkil etuvchi qirralarning og'irliklari yig'indisi minimallashtiriladi.

Eng qisqa yo'l muammosi graf nazariyasining eng muhim klassik muammolaridan biridir. Bugungi kunda uni hal qilish uchun ko'plab ma'lum algoritmlar mavjud.

Eng qisqa yo'l muammosi

Deykstri algoritmi. Eng qisqa yo‘lni topish misolini ko‘rib chiqing. Shaharni bog‘laydigan yo‘llar tarmog‘i berilgan. Ba'zi yo‘llar bir tomonlama. Shahar markazidan mintaqadagi har bir shaharga olib boradigan eng qisqa yo‘llarni toping.

Deykstri algoritmi. Eng qisqa yo‘lni topish misolini ko‘rib chiqing. Shaharni bog‘laydigan yo‘llar tarmog‘i berilgan. Ba'zi yo‘llar bir tomonlama. Shahar markazidan mintaqadagi har bir shaharga olib boradigan eng qisqa yo‘llarni toping.

Ushbu muammoni hal qilish uchun siz Deykstri algoritmidan foydalanishingiz mumkin - 1959 yilda Gollandiyalik olim E. Dijkstroy tomonidan ixtiro qilingan graflardagi algoritm. Grafning uchidan boshqalarigacha bo‘lgan eng qisqa masofani topadi. Faqat salbiy og‘irlikka ega chizmalar uchun ishlaydi.

Eng qisqa yo'l muammosi
Edsger Wibe Deykstra - 1930 yil 11-may, Rotterdam, Niderlandiya

Topshiriqlar:

Ushbu grafdagi 2 va 5-tugunlar orasidagi eng qisqa yo‘l zanjirini toping. (Deykstr algoritmi yordamida).

Izoh. Har birini qadamma-qadam ko‘rsating.

E’tiboringiz uchun rahmat!!!

Laboratoriya topshiriqlarini vaqtida bajaring va mustaqil bilimga ega bo’lin!!!