ILM-FAN VA INNOVATSIYA
ILMIY-AMALIY KONFERENSIYASI
in-academy.uz/index.php/si
17
GRAFIKLAR NAZARIYASI VA UNING ALGORITMLARDA QOʻLLANILISHI
O‘ktamov Madadjon O‘ktam o‘g‘li
SHDPI “Matematika va ta’limda axborot texnologiyasi”
kafedrasi o‘qituvchisi
Ochilova Surayyo Shavkat qizi
SHDPI “Matematika va informatika yoʻnalish talabasi”
https://doi.org/10.5281/zenodo.14998196
Annotatsiya:
Grafiklar nazariyasi matematikada va kompyuter ilm-fanida muhim o‘rin
tutadi, chunki u tizimlar orasidagi munosabatlarni ifodalash va tahlil qilishda keng
qo‘llaniladi. Grafiklar bo‘g‘inlar (vertices) va ularni bog‘laydigan qirralardan (edges) tashkil
topgan strukturalardir. Bu nazariya turli xil masalalarni hal qilishda, xususan, tarmoq tahlili,
yo‘lni topish, sosial tarmoqlar va kompyuter grafikasi kabi sohalarda keng qo‘llaniladi.
Абстрактный.
Теория графов играет важную роль в математике и информатике,
поскольку она широко используется для представления и анализа взаимосвязей между
системами. Графы — это структуры, состоящие из вершин и соединяющих их ребер.
Эта теория широко применяется при решении различных задач, особенно в таких
областях, как сетевой анализ, поиск пути, социальные сети и компьютерная графика.
Abstract.
Graph theory is an important field in mathematics and computer science, as it
is widely used to describe and analyze relationships between systems. Graphs are structures
consisting of vertices and the edges connecting them. This theory is widely used in solving
various problems, in particular in areas such as network analysis, pathfinding, social
networks, and computer graphics.
Kalit soʻzlar
.
Grafiklar, bo‘g‘inlar (Vertices), qirralar (edges), yo‘nalgan grafik (directed
graph), algoritmlar, chuqurlik bo‘yicha izlash (DFS), kenglik bo‘yicha izlash (BFS), dijkstra
algoritmi, bellman-Ford algoritmi, kruskal
algoritmi., prim
algoritmi, floyd-Warshall algoritmi,
eng qisqa yo‘l , tarmoq tahlili, kompyuter grafikasi.
Ключевые слова:
Графы, Вершины, Ребра, Направленный граф, Алгоритмы,
Поиск в глубину (DFS), Поиск в ширину (BFS), Алгоритм Дейкстры, Алгоритм Беллмана-
Форда, aлгоритм Крускала, aлгоритм Примаб алгоритм Флойда-Уоршелла, cамый
короткий маршрут, cетевой анализ, компьютерная графика.
Keywords:
Graphs, Vertices, Edges, Directed Graph, Algorithms, Depth-First Search
(DFS), Breadth-First Search (BFS), Dijkstra's Algorithm, Bellman-Ford Algorithm, kruskal's
Algorithm, prim's Algorithm, floyd-Warshall Algorith., shortest Path, network Analysis,
computer Graphics.
Grafiklar nazariyasi
–
bu matematikada va kompyuter ilm-fanida turli tizimlar va
ularning o‘zaro aloqalarini tasvirlash va tahlil qilishga mo‘ljallangan soha. Grafiklar, bo‘g‘inlar
(vertices) va ular orasidagi qirralardan (edges) tashkil topgan strukturadir. Har bir bo‘g‘in
ma'lum bir ob'ektni, qirra esa bu ob'ektlar orasidagi bog‘lanishni ifodalaydi. Grafiklar
nazariyasining o‘rganilishi turli sohalarda, xususan, kompyuter tarmoqlari, transport
tizimlari, sosial tarmoqlar va biotexnologiyalarda keng qo‘llaniladi. Bugungi kunda grafiklar
nazariyasining algoritmlari ko‘plab amaliy masalalarni hal qilishda muhim vosita bo‘lib
ILM-FAN VA INNOVATSIYA
ILMIY-AMALIY KONFERENSIYASI
in-academy.uz/index.php/si
18
xizmat qilmoqda. Masalan, tarmoq tahlili, eng qisqa yo‘lni topish, minimal bog‘lovchi daraxtni
qurish, ijtimoiy tarmoqlarda aloqalar tahlili va boshqalar grafiklar nazariyasining algoritmlari
yordamida hal qilinadi. Maqolada grafiklar nazariyasining asosiy tushunchalari va uning
algoritmlarda qo‘llanilishiga oid muhim masalalar ko‘rib chiqiladi. Grafiklarni tahlil qilish va
o‘rganish uchun ishlab chiqilgan algoritmlar, jumladan, DFS (Depth-First Search), BFS
(Breadth-First Search), Dijkstra algoritmi, Kruskal va Prim algoritmlari kabi usullar
grafiklarning turli turlarini va muammolarni hal qilishda qanday samarali ishlatilishini
ko‘rsatadi. Grafiklar nazariyasining bu algoritmlari nafaqat matematik tahlil, balki real
hayotdagi tizimlar va muammolarni samarali hal qilishda ham muhim ahamiyatga ega.
Grafiklar nazariyasi, asosan, ikkita asosiy tarkibiy qismdan iborat. Bo‘g‘inlar (vertices) –
Grafikdagi nuqtalar yoki ob'ektlar.1736-yil Königsberg. Shahar boʻylab Pregel daryosi oqib
oʻtadi. Yuqoridagi rasmda ko'rsatilganidek, shaharda ettita ko'prik mavjud. Qadim
zamonlardan beri Koenigsberg aholisi jumboq bilan kurashib kelishgan: har bir ko'prikdan bir
marta o'tib, barcha ko'priklardan o'tish mumkinmi? Bu muammo nazariy jihatdan ham,
qog'ozda ham, amalda ham, xuddi shu ko'priklardan o'tish orqali hal qilindi. Hech kim buni
amalga oshirish mumkin emasligini isbotlay olmadi, lekin hech kim ko'priklar bo'ylab bunday
"sirli" yurish qila olmadi.
Bellman-Ford algoritmi
-
Bu algoritm ham og‘irlikli grafiklar uchun ishlatiladi, lekin
Dijkstra algoritmiga qaraganda u barcha qirralar uchun ishlayveradi va salbiy og‘irliklar bilan
ham ishlay oladi. Manfiy og‘irlikli qirralarga ega grafiklarda ham ishlaydi.
Agar yana yangilash mumkin bo‘lsa, demak, manfiy tsikl mavjud. Floyd-Warshall
algoritmi. Barcha tugunlar orasidagi eng qisqa yo‘lni topadi.Dinamik dasturlashga asoslangan.
Minimal qoplovchi daraxt (Minimum Spanning Tree, MST) algoritmlari. Minimal qoplovchi
daraxt grafikning barcha tugunlarini eng kam og‘irlik bilan bog‘laydigan daraxtdir.
Prim algoritm - har doim eng kichik og‘irlikli qirrani qo‘shadi. Qirralarni og‘irlik bo‘yicha
tartiblab, eng arzonlarini qo‘shib boradi.Grafiklarning real hayotdagi qo‘llanilishi.Grafik
algoritmlari turli sohalarda qo‘llaniladi. Yo‘l topish va navigatsiya (Google Maps, GPS tizimlari
– Dijkstra). Ijtimoiy tarmoqlar tahlili. (Facebook, Twitter – BFS, DFS). Elektr tarmoqlari va
kompyuter tarmoqlari (MST algoritmlari). Biologiya va genomika (Protein tarmoqlari – Floyd-
Warshall). Sun'iy intellekt va tavsiyalar tizimi (Graph Neural Networks, PageRank). Grafiklar
nazariyasi kompyuter fanlarining muhim qismi bo‘lib, turli murakkab masalalarni samarali
hal qilishga imkon beradi. Eng mashhur algoritmlar – BFS, DFS, Dijkstra, Bellman-Ford, Floyd-
Warshall, Prim, Kruskal – real hayotda ko‘plab muammolarni hal qilishda ishlatiladi.
Grafiklarni tushunish va ulardan foydalanish dasturlash va algoritmlarni o‘rganishda muhim
qadam hisoblanadi.Matematikada grafik ta'rifi quyidagicha berilgan: grafik - bu nuqtalarning
cheklangan to'plami bo'lib, ularning ba'zilari chiziqlar bilan bog'langan. Nuqtalar grafikning
cho'qqilari, bog'lovchi chiziqlar esa qirralar deb ataladi.Kompyuter grafikasida ham grafiklar
nazariyasi muhim ahamiyatga ega. Tasvirlarni ko'rib chiqish va ularda geometrik shakllarni
yaratishda grafiklar yordamida formulalar tuziladi.
Kompyuter ko'rish tizimlari, virtual haqiqat (VR) va 3D modellashda grafiklar
nazariyasidan foydalaniladi.Grafiklar nazariyasi nafaqat matematik soha, balki amaliyotda
keng qo'llaniladigan bir qator sohalar uchun ham asosiy vosita hisoblanadi. Grafiklar orqali
turli tizimlar va tarmoqlarda bog'lanishlarni aniqlash, optimallashtirish va samarali ishlashni
ILM-FAN VA INNOVATSIYA
ILMIY-AMALIY KONFERENSIYASI
in-academy.uz/index.php/si
19
ta'minlash mumkin. Shuningdek, kompleks tizimlarda hamkorlik va ma'lumot almashish
jarayonlarini tushunish va optimallashtirish uchun grafiklar nazariyasining qo'llanishi juda
muhimdir.
Foydalanilgan adabiyotlar/Используемая литература/References:
1.
Musurmanova, Yayra, and Jasmina Toshpo‘lotova. "Iqtisodiyotni raqamlashtirish
sharoitida iqtisodiy jarayonlar va moliyaviy munosabatlarning transformatsiyasi." (2024): 38-
41.
2.
Uktamov, M. "Modeling the professional training development of future teachers
through computer training." Science and innovation 2.B9 (2023): 139-141.
3.
Октамов, Мададжон, Жасмина Тошполотова, and Яйра Мусурманова. "Aniq fanlarni
o ‘qitishda zamonaviy pedagogik texnologiyalarni qo ‘llagan holda dars jarayonlarini tashkil
etish." Новый Узбекистан: наука, образование и инновации 1.1 (2024): 432-434.
4.
Madadjon, O‘Ktamov. "PEDAGOGIKA OLIY TA’LIM MUASSASALARI TALABALARINING
INFORMATIKADAN
AXBOROT-TEXNOLOGIK
KOMPETENTLIGINI
RIVOJLANTIRISH
METODIKASI." Academic research in educational sciences 4.CSPU Conference 1 (2023): 275-
281.
5.
O’G’Li, Madadjon O’Ktam. "Kuzatuv quduqlarida yer osti suvlarini gidrorejim
parametrlarini masofaviy nazorat qilishning avtomatlashgan tizimlari." Science and Education
2.12 (2021): 202-211.
6.
Usmon o‘g‘li, Musirmanov Shohboz. "IJTIMOIY TARMOQLAR ORQALI TURISTIK
JOYLARNI REKLAMA QILISH VA MIJOZLAR BILAN SAMARALI ALOQA O ‘RNATISH." Scientific
Journal of Actuarial Finance and Accounting 4.10 (2024): 369-374.
7.
Xabibullayevich, Abdullayev Safibullo, et al. "TECHNOLOGY OF ORGANIZATION OF
ENVIRONMENT FOR THE DEVELOPMENT OF ERGONOMIC CULTURE." Harvard Educational
and Scientific Review 1.1 (2021).
8.
Beknazarova, Saida, et al. "METHOD OF FILTERING DIGITAL IMAGES BY PULSE
CHARACTERISTIC IN THE SPECTRAL REGION." Актуальные вопросы развития
инновационно-информационных технологий на транспорте 2021 (2021): 66-69.
9.
Musirmanov, Shohboz. "TURIZM SOHASIDA KADRLAR TAYYORLASHDA AMALIYOT VA
NAZARIYANING PEDAGOGIK UYG ‘UNLIGI." Ижтимоий-гуманитар фанларнинг долзарб
муаммолари/Актуальные проблемы социально-гуманитарных наук/Actual Problems of
Humanities and Social Sciences. 4.11.
