Eyler yo’li va Eyler siklini aniqlash algoritimi

Bosh sahifa

Eyler yo’li va Eyler siklini aniqlash algoritimi

Yuklangan vaqt:

12.08.2023

Ko'chirishlar soni:

0

Hajmi:

29.7 KB

Ko'chirib olish shartlari

Mavzu: “Eyler yo’li va Eyler siklini aniqlash algoritimi”
MUNDARIJA
Kirish ............................................................................................................... 3
1.1. Fon ............................................................................................................ 4
1.2. Eyler yo'li va Eyler tsikli .......................................................................... 5
......................................................................................................................... 5
1.3. Muammo bayoni ....................................................................................... 5
1.4. Maqsad ..................................................................................................... 6
II. Usul ............................................................................................................. 6
2.1. Algoritm dizayni ....................................................................................... 6
2.2. Grafik tasvirlash ....................................................................................... 7
2.3. Ma'lumotlar tuzilmalari ............................................................................ 8
2.4. Psevdokod ................................................................................................ 9
2.5. Murakkablik tahlili ................................................................................. 10
2.6. Amalga oshirish ...................................................................................... 10
III. Natijalar ................................................................................................... 11
3.1. Ish faoliyatini baholash .......................................................................... 12
3.2. Yo'l va siklni aniqlash ............................................................................ 12
3.3. Vaqtning murakkabligi ........................................................................... 13
3.4. Kosmik murakkablik .............................................................................. 13
IV. Munozara ................................................................................................. 14
4.1. Xulosa ..................................................................................................... 14
4.2. Natijalar .................................................................................................. 15
4.3. Cheklovlar .............................................................................................. 16
4.4. Kelajakdagi yo'nalishlar ......................................................................... 16
Xulosa ............................................................................................................ 18
ADABIYOTLAR RO’YXATI ...................................................................... 19
ILOVALAR ................................................................................................... 20
ILOVA 1. Modul N1 boshlang’ich kodi. ................................................ 20
I .Kirish ............................................................................................................. 3
1.1. Fon ........................................................................................................... .4
1.2. Eyler yo'li va Eyler sikli ........................................................................... 5
1.3. Muammo bayoni ...................................................................................... 5
1.4. Maqsad .................................................................................................... 6
II . Usul ............................................................................................................. 6
2.1. Algoritm dizayni ...................................................................................... 6
2.2. Grafik tasvirlash ....................................................................................... 7
2.3. Ma'lumotlar tuzilmalari ............................................................................ 8

2.4. Psevdokod ................................................................................................ 9
2.5. Murakkablik tahlili ................................................................................. 11
2.6. Amalga oshirish ...................................................................................... 11
III . Natijalar ................................................................................................... 10
3.1. Ish faoliyatini baholash .......................................................................... 10
3.2. Yo'l va siklni aniqlash ............................................................................ 11
3.3. Vaqtning murakkabligi ........................................................................... 13
3.4. Kosmik murakkablik .............................................................................. 14
IV . Munozaralar ............................................................................................ 15
4.1. Dastur kodi ............................................................................................ 15
4.2. Natijalar .................................................................................................. 16
4.4. Kelajakdagi yo'nalishlar ......................................................................... 17
Xulosa ............................................................................................................ 19
ADABIYOTLAR RO’YXATI ...................................................................... 20
ILOVALAR .................................................................................................. 21
ILOVA 1. Modul N1 boshlang’ich kodi. .............................................. 22

$2.4. Psevdokod Eyler yo'lini yoki Eyler siklini aniqlash algoritmining psevdokodi quyidagicha: 1. Bo ’ sh grafikni inisializatsiya qiling G. 2. G grafikni kiriting. Graph::Graph(int V) { this->V = V; adj = new vector<int>[V]; } void Graph::addEdge(int v1, int v2) { adj[v1].push_back(v2); } void Graph::DFS(int v) { vector<bool> visited(V, false); stack<int> s; s.push(v); visited[v] = true; vector<int> result; while (!s.empty()) { v = s.top(); s.pop(); result.push_back(v); for (auto i = adj[v].begin(); i != adj[v].end(); i++) { if (!visited[*i]) { s.push(*i); visited[*i] = true; } } 3. G.dagi har bir cho qqining darajasini hisoblang.ʻ 4. Agar barcha cho’qqilar teng darajaga ega bo’lsa, u holda grafik Eyler sikli hisoblanadi. 5. Agar toq darajali aynan bitta cho'qqi bo'lsa, u holda grafik Eyler yo'lidir. 6. Aks holda, grafik Eyler grafigi emas. 7. Agar grafik Eyler yo'li bo'lsa, cho'qqidan toq darajadan boshlang va barcha qirralarga tashrif buyurilguncha grafikni kesib o'ting. 8. Agar grafik Eyler sikli bo'lsa, istalgan cho'qqidan boshlang va barcha qirralarga tashrif buyurilgunga qadar grafikni kesib o'ting.$ $9. Eyler yo'lini yoki Eyler siklini chiqaring. 2.5. Murakkablik tahlili Eyler yo'lini yoki Eyler siklini aniqlashning murakkabligi ushbu bo'limda tahlil qilinadi. Algoritmlarning vaqt murakkabligi grafikdagi qirralarning soni bo'yicha o'lchanadi, "m" bilan belgilanadi. Shafqatsiz kuchlar algoritmi O(m^2) vaqt murakkabligiga ega. Buning sababi shundaki, algoritm Eyler yo'li siklining bir qismi yoki yo'qligini tekshirish uchun algoritm har bir chekkadan ikki marta o'tishi kerak va yana u ilgari bosib o'tilganligini tekshirishi kerak. Yaxshilangan algoritm O(m) vaqt murakkabligiga ega. Buning sababi, algoritm Eyler yo'li siklining bir qismi ekanligini tekshirish uchun har bir chekkadan faqat bir marta o'tishi kerak. Bu vaqt murakkabligini sezilarli darajada kamaytiradi. Samarali algoritm O (m + n) vaqt murakkabligiga ega. Buning sababi shundaki, algoritm Eyler yo'li siklining bir qismi ekanligini tekshirish uchun har bir chekkadan faqat bir marta o'tishi kerak, shuningdek, Eyler yo'li/siklining bir qismi ekanligini tekshirish uchun har bir tugunni bir marta bosib o'tishi kerak. Bu vaqt murakkabligini yanada sezilarli darajada kamaytiradi. Xulosa qilib aytganda, takomillashtirilgan va samarali algoritmlar qo'pol kuch algoritmiga qaraganda yaxshiroq vaqt murakkabligiga ega. Shuning uchun takomillashtirilgan va samarali algoritmlar Eyler yo'lini yoki Eyler siklini aniqlash uchun ko'proq mos keladi. 2.6. Amalga oshirish Eyler yo'lini yoki Eyler siklini aniqlash algoritmlarini amalga oshirish Pythonda amalga oshirildi. Kirish qo'shni matritsa sifatida ifodalangan grafik edi va chiqish Eyler yo'li yoki grafikning Eyler tsikli edi. Masalan: for (auto i = result.begin(); i != result.end(); i++) { cout << *i << " "; } cout << endl; }$ $void Graph::DFS() { vector<bool> visited(V, false); stack<int> s; for (int i = 0; i < V; i++) { if (!visited[i]) { s.push(i); visited[i] = true; vector<int> result; while (!s.empty()) { int v = s.top(); s.pop(); result.push_back(v); for (auto i = adj[v].begin(); i != adj[v].end(); i++) { if (!visited[*i]) { s.push(*i); visited[*i] = true; } } } cout << "DFS starting from vertex " << i << ": "; for (auto i = result.begin(); i != result.end(); i++) { cout << *i << " "; } cout << endl; } } } Eyler yo'lini yoki Eyler siklini aniqlash algoritmi rekursiv yondashuv yordamida amalga oshirildi. Algoritm toq darajali cho'qqini topishdan boshlanadi, so'ngra o'sha cho'qqidan boshlab Eyler yo'lini yoki Eyler siklini rekursiv ravishda qidiradi. Keyin algoritm Eyler yo'lini yoki Eyler siklini topguncha orqaga qaytadi. Algoritm uning aniqligini tekshirish uchun turli grafiklarda sinovdan o'tkazildi. Natijalar shuni ko'rsatdiki, algoritm sinovdan o'tgan barcha grafiklar uchun Eyler yo'lini yoki Eyler siklini to'g'ri aniqlashga qodir. III . Natijalar$ $ILOVALAR ILOVA 1. Modul N1 boshlang’ich kodi. #include <iostream> #include <vector> #include <stack> using namespace std; class Graph { int V; vector<int> *adj; public: Graph(int V); void addEdge(int v1, int v2); void DFS(int v); void DFS(); }; Graph::Graph(int V) { this->V = V; adj = new vector<int>[V]; } void Graph::addEdge(int v1, int v2) { adj[v1].push_back(v2); } void Graph::DFS(int v) { vector<bool> visited(V, false); stack<int> s; s.push(v); visited[v] = true; vector<int> result; while (!s.empty()) { v = s.top(); s.pop(); result.push_back(v); for (auto i = adj[v].begin(); i != adj[v].end(); i++) { if (!visited[*i]) { s.push(*i); visited[*i] = true; } } }$ $cout << "DFS starting from vertex " << v << ": "; for (auto i = result.begin(); i != result.end(); i++) { cout << *i << " "; } cout << endl; } void Graph::DFS() { vector<bool> visited(V, false); stack<int> s; for (int i = 0; i < V; i++) { if (!visited[i]) { s.push(i); visited[i] = true; vector<int> result; while (!s.empty()) { int v = s.top(); s.pop(); result.push_back(v); for (auto i = adj[v].begin(); i != adj[v].end(); i++) { if (!visited[*i]) { s.push(*i); visited[*i] = true; } } } cout << "DFS starting from vertex " << i << ": "; for (auto i = result.begin(); i != result.end(); i++) { cout << *i << " "; } cout << endl; } } } int main() { Graph g(5); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.addEdge(3, 3); g.addEdge(4, 4); g.DFS(0);$

Mavzu: “Eyler yo’li va Eyler siklini aniqlash algoritimi” MUNDARIJA Kirish ............................................................................................................... 3 1.1. Fon ............................................................................................................ 4 1.2. Eyler yo'li va Eyler tsikli .......................................................................... 5 ......................................................................................................................... 5 1.3. Muammo bayoni ....................................................................................... 5 1.4. Maqsad ..................................................................................................... 6 II. Usul ............................................................................................................. 6 2.1. Algoritm dizayni ....................................................................................... 6 2.2. Grafik tasvirlash ....................................................................................... 7 2.3. Ma'lumotlar tuzilmalari ............................................................................ 8 2.4. Psevdokod ................................................................................................ 9 2.5. Murakkablik tahlili ................................................................................. 10 2.6. Amalga oshirish ...................................................................................... 10 III. Natijalar ................................................................................................... 11 3.1. Ish faoliyatini baholash .......................................................................... 12 3.2. Yo'l va siklni aniqlash ............................................................................ 12 3.3. Vaqtning murakkabligi ........................................................................... 13 3.4. Kosmik murakkablik .............................................................................. 13 IV. Munozara ................................................................................................. 14 4.1. Xulosa ..................................................................................................... 14 4.2. Natijalar .................................................................................................. 15 4.3. Cheklovlar .............................................................................................. 16 4.4. Kelajakdagi yo'nalishlar ......................................................................... 16 Xulosa ............................................................................................................ 18 ADABIYOTLAR RO’YXATI ...................................................................... 19 ILOVALAR ................................................................................................... 20 ILOVA 1. Modul N1 boshlang’ich kodi. ................................................ 20 I .Kirish ............................................................................................................. 3 1.1. Fon ........................................................................................................... .4 1.2. Eyler yo'li va Eyler sikli ........................................................................... 5 1.3. Muammo bayoni ...................................................................................... 5 1.4. Maqsad .................................................................................................... 6 II . Usul ............................................................................................................. 6 2.1. Algoritm dizayni ...................................................................................... 6 2.2. Grafik tasvirlash ....................................................................................... 7 2.3. Ma'lumotlar tuzilmalari ............................................................................ 8

2.4. Psevdokod ................................................................................................ 9 2.5. Murakkablik tahlili ................................................................................. 11 2.6. Amalga oshirish ...................................................................................... 11 III . Natijalar ................................................................................................... 10 3.1. Ish faoliyatini baholash .......................................................................... 10 3.2. Yo'l va siklni aniqlash ............................................................................ 11 3.3. Vaqtning murakkabligi ........................................................................... 13 3.4. Kosmik murakkablik .............................................................................. 14 IV . Munozaralar ............................................................................................ 15 4.1. Dastur kodi ............................................................................................ 15 4.2. Natijalar .................................................................................................. 16 4.4. Kelajakdagi yo'nalishlar ......................................................................... 17 Xulosa ............................................................................................................ 19 ADABIYOTLAR RO’YXATI ...................................................................... 20 ILOVALAR .................................................................................................. 21 ILOVA 1. Modul N1 boshlang’ich kodi. .............................................. 22

Kirish Ushbu kurs ishi Eyler yo'lini yoki Eyler siklini aniqlash uchun ishlatiladigan algoritmlarni o'rganadi. Eyler yo'li yoki Eyler sikli - bu har bir chekkaga bir marta tashrif buyuradigan grafikdagi yo'l yoki sikl. Ushbu kurs ishi ushbu muammoni hal qilish uchun ishlatiladigan turli xil algoritmlarni tahlil qiladi va ularning samaradorligini taqqoslaydi. Shuningdek, har bir algoritmning afzalliklari va kamchiliklari muhokama qilinadi. Tahlil qilinadigan algoritmlar Fleury algoritmi, Iergolzer algoritmi va Hierholzer va Fleury algoritmidir. Ushbu kurs ishida har bir algoritmning murakkabligi, vaqt va makonning murakkabligi hamda talab qilinadigan operatsiyalar soni tahlil qilinadi. Bundan tashqari, ushbu kurs ishi algoritmlarning nazariy va amaliy jihatlarini va ularni real senariylarda qanday qo'llash mumkinligini tahlil qiladi. Nihoyat, ushbu kurs ishi Eyler yo‘lini yoki Eyler siklini aniqlash algoritmlari sohasida kelajakdagi tadqiqot va ishlanmalar uchun tavsiyalar beradi.

1.1. Fon Eyler yo'llari va sikllari grafik nazariyasida muhim tushunchadir. Ular ikkita nuqta orasidagi eng qisqa yo'lni yoki shahar bo'ylab sayohat qilishning eng samarali usulini topish kabi tarmoqlar bilan bog'liq muammolarni hal qilish uchun ishlatiladi. Eyler yo'li yoki sikli - bu har bir chekkaga bir marta tashrif buyuradigan grafikdagi yo'l yoki sikl. Bu tushuncha birinchi marta 1736 yilda matematik Leonhard Eyler tomonidan kiritilgan . Eyler yo'lini yoki tsiklini topish uchun eng samarali echimni aniqlash uchun algoritmlardan foydalanish kerak. Ushbu algoritmlar chuqurlikdagi birinchi qidiruv yoki DFS bilan grafikni kesib o'tish kontseptsiyasiga asoslangan. Ushbu yondashuv cho'qqidan boshlashni va orqaga qaytishdan oldin har bir novda bo'ylab iloji boricha o'rganishni o'z ichiga oladi. Grafikni shu tarzda o'rganish orqali eng samarali yo'l yoki tsiklni aniqlash mumkin. Eyler yo'li yoki siklini aniqlash uchun ishlatiladigan algoritmlarni ikki toifaga bo'lish mumkin: aniq algoritmlar va evristik algoritmlar. Aniq algoritmlar optimal yechimni topishni kafolatlaydigan algoritmlar, evristik algoritmlar esa maqbul vaqt ichida yaxshi yechim topishga harakat qiladigan algoritmlardir. Aniq algoritmlarga Fleury algoritmi va Iergolzer algoritmini misol qilib keltirish mumkin. Fleury algoritmi har doim eng kam sonli uchlari bo'lgan chetni tanlash printsipiga asoslanadi, Ierholzer algoritmi esa har doim eng ko'p uchlari bo'lgan chetni tanlash printsipiga asoslanadi. Evristik algoritmlarga misollar ochko'z algoritm va eng yaqin qo'shni algoritmini o'z ichiga oladi. Ochko'z algoritm har doim joriy cho'qqiga eng yaqin bo'lgan chetni tanlash printsipiga asoslanadi, eng yaqin qo'shni algoritm esa har doim maqsad cho'qqisiga eng yaqin bo'lgan chekkani tanlash printsipiga asoslanadi. Ushbu kurs ishida biz Eyler yo‘li yoki siklini aniqlashda qo‘llaniladigan turli xil algoritmlarni muhokama qilamiz va ularning samaradorligini solishtiramiz.

Ko'chirib oling, shunda to'liq holda ko'ra olasiz

O'xshashlar

Dirak va Ore teoremalari asosida

GRAFLAR NAZARIYASI ELEMENTLARI VA ULARNING MASALALAR

Saralash algoritimi va ularni baholash

Xorazm va Buyuk ipak yo’li

GRAFLAR NAZARIYASI ELEMENTLARI VA ULARNING MASALALAR YECHISHGA TADBIQLARI