O'zbеkiston respublikasi axborot texnologiyalari va kommunikatsiyalarini rivojlantirish vazirligi toshkеnt axborot tеxnologiyalari univеrsitеti

O'ZBЕKISTON RESPUBLIKASI AXBOROT

TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH

VAZIRLIGI TOSHKЕNT AXBOROT TЕXNOLOGIYALARI

UNIVЕRSITЕTI

“Algoritmlarni loyihalash” fanidan

MUSTQIL ISH

Mavzu: Yo'naltirilmagan grafga ta'rif bering va misolda ifodalab korsating

Guruh: CAL008

Bajardi: Sobirov Muhammad

Tekshirdi: Yusupova Zaynab

Toshkent_2020

44-VARIANT

44. Yo'naltirilmagan grafga ta'rif bering va misolda ifodalab korsating.

Yo’naltirilmagan graflar- (a,b)∈U juftlikni tashkil etuvchi a va b uchlarning joylashish tartibidan bog‘liq holda, ya’ni yo‘nalishning borligi yoki yo‘qligiga qarab, uni turlicha atash mumkin .

Agar (a,b) juftlik uchun uni tashkil etuvchilarning joylashish tartibi ahamiyatsiz, ya’ni (a,b) = (b,a) bo‘lsa, (a,b) juftlikka yo‘naltirilmagan(oriyentirlanmagan) qirra (yoki, qisqacha, qirra) deyiladi.Barcha qirralari yo'naltirilmagan graf- yo'naltirilmagan grafik deb nomlanadi.Boshqacha qilib aytganda, yo'naltirilmagan grafikning chekkalari yo'nalishni o'z ichiga olmaydi .Agar G = (V,U) grafda U kortej faqat qirralardan iborat bo‘lsa, u holda yo‘naltirilmagan (oriyentirlanmagan) graf, qisqacha, orgraf deb ham ataladi

3



2

3



7



6

4



5

4

1



1



10



6

9


Ushbu grafik to'rtta vertikal va to'rtta yo'naltirilmagan qirralardan iborat.

Ko‘p hollarda oriyentirlanmagan qirralari ham, oriyentirlangan qirralari ham bo‘lgan graflar bilan ish ko‘rishga to‘g‘ri keladi. Bunday graflar aralash graflar deyiladi . Agar G = (V,U) grafning (orgrafning) U korteji tarkibida V ×V to‘plamdan olingan takrorlanuvchi elementlar bo‘lsa, u holda ular karrali yoki parallel qirralar (yoylar) deb ataladi. Karrali qirralari yoki yoylari bo‘lgan graf multigraf deyiladi. Ikkala chetki (boshlang‘ich va oxirgi) uchlari ustma-ust tushgan qirra (yoy), ya’ni grafning (a,a)∈U elementi sirtmoq deb ataladi. Sirtmoq, odatda, yo‘naltirilmagan deb hisoblanadi. Qirralari (yoylari) orasida sirtmoqlari bo‘lgan graf psevdograf deyiladi.

Bir nechta juft tugunlararo qirralardan iborat bo’lgan turlicha yo’llar to’plami mavjud bo’lishi mumkin. Yopiq yo’llar – sikllarning mavjud bo’lishi tarmoqlarga xos xususiyatdir.

Yonaltirilmagan graf yoki simmetrik bog’liqlik

Yonaltirilmagan graf yoki nosimmetrik bog’liqlik

qirra yoylar

Ilmoq – aynan bitta tugundan chiqib, yana shu tugunga kiruvchi qirra.

Yo’naltirilmagan graf qo’shma matritsasi

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

Munosabat matritsasi

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

Qo’shnilik ro’yxati


1

2

4

4

1

2

1

4

4

2

3

2

3

5

7

4

1

1

2

2

5

3

7

6

9

6

4

10

5

9

4

6

3

6

6

10


Yoylar ro’yxati


1

2

4

1

4

1

2

3

3

22

4

2

3

4

6

3

5

7

4

6

10

5

6

9

N

XULOSA

Ushbu mavzuni o'rganish davomida muayyan ob’yektlarning graf modelini uchlar qo‘shniligi va insidentlik matritsalari yordamida hosil qilish, hosil qilingan graf modellarini uchlar orasidagi masofa matritsasi, graf radiusi, diametri, markazlarini aniqlash algoritmi tuzildi va vizuallashtirilgan dasturiy vosita ishlab chiqildi. Bu dasturiy vositadan foydalanib, uchlar qo‘shniligi va insidentlik matritsalari yordamida turli graflarni hosil qilish va ularini graflarning metrik xarakteristikalari: uchlar orasidagi masofa matritsasi, graf radiusi, diametri, markazlarini aniqlash bo‘yicha bir necha masalalar ko‘rib chiqildi Ishda olingan natijalar va unda qo‘llanilgan usullardan turli iqtisodiy, ijtimoiy sohalarning ko‘pgina amaliy masalalarining graf modellarini hosil qilishda, ularning dastury vositalarini ishlab chiqishda, “Graflar nazariyasi”, “Axborot xavfsizligi”, “Kompyuter injineringi”, “Dastur injineringi” va shu kabi fanlarning amaliy mashg‘ulotlari o‘quv jarayonlarida dasturiy vosita sifatida foydalanish mumkin.

Foydalanilgan adabiyotlar

1. Окулов С. М. Программирование в алгоритмах.– М.: БИНОМ. Лаборатория знаний, 2004. – 341 с: ил.

2. Головешкин В. А., Ульянов М. В. Теория рекурсии для проrраммистов.

М.: ФИЗМАТЛИТ, 2006. 296 с.

3. Ахо, Альфред, В., Хопкрофт, Джон, Ульман, Джеффри, Д. Структуры

данных и алгоритмы. : Пер. с англ. : Уч. пос. – М. : Издательский дом

"Вильяме", 2000. – 384 с. : ил. – Парал. тит. англ. (рус).

4. Ф.А. Новиков Дискретная математика для программистов. СПб: Питер,

2000. – 304 с.

5. Иванов Б.Н. Дискретная математика. Алгоритмы и программы:

6. http://olo.looblogs.info/issledovanie-funkcij-maple.html

7. http://maple.plusby.com/index.html