Eyler yo’li va Eyler siklini aniqlash algoritimi
![o'tmaydi. Agar algoritm ko'rilmagan chekkalari bo'lmagan cho'qqiga etib borsa, u
oxirgi tashrif buyurgan cho'qqiga qaytib ketadi va boshqa chetni sinab ko'radi.
Algoritm grafikning barcha qirralarini kesib o'tgandan so'ng, u Eyler yo'lini
yoki Eyler siklini tugatgan bo'ladi. Keyin algoritmdan grafikdagi eng qisqa yo‘lni
yoki eng qisqa siklni topish uchun foydalanish mumkin.
2.2. Grafik tasvirlash
Eyler yo'li yoki siklining grafik tasviri yo'naltirilgan grafik bo'lib, G = (V,
E), bu erda V - cho'qqilar to'plami va E - qirralar to'plami. Har bir chekka bir
cho'qqidan ikkinchisiga yo'naltirilgan chekka bilan ifodalanadi. Qirralar Eyler yo'li
yoki sikli oladigan yo'llarni ifodalaydi. Grafik qo'shnilik ro'yxati bilan ifodalanadi,
bu barcha uchlari va ular bog'langan qirralarning ro'yxati. Grafikdagi barcha
cho'qqilarni bog'laydigan yo'llarni topish orqali Eyler yo'lini yoki tsiklini aniqlash
uchun qo'shnilik ro'yxati ishlatiladi.
Class hosil qilinayapti.Unga qirra qo’shilayapti:
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];
}
Eyler yo'li yoki siklini topish algoritmi har bir cho'qqining darajasini
topishdan boshlanadi. Cho'qqining darajasi - unga bog'langan qirralarning soni.
Agar har bir cho‘qqining darajasi juft bo‘lsa, grafik Eyler sikliga ega bo‘ladi. Agar
ikkita cho'qqining darajasi toq bo'lsa, u holda grafik Eyler yo'liga ega.
Har bir cho'qqining darajasi aniqlangandan so'ng, algoritm grafikdagi barcha
cho'qqilarni bog'laydigan yo'llarni topadi. Bu birinchi chuqur qidiruv algoritmi
yordamida amalga oshiriladi. Chuqurlikdagi birinchi qidiruv algoritmi cho'qqidan
boshlanadi va unga](/data/documents/f8ba04af-61c8-4660-a29e-069a16b93d08/page_7.png)
![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.](/data/documents/f8ba04af-61c8-4660-a29e-069a16b93d08/page_9.png)
![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](/data/documents/f8ba04af-61c8-4660-a29e-069a16b93d08/page_11.png)
![3.1. Ish faoliyatini baholash
Algoritmlarning ishlashini baholash turli grafiklar bo'yicha o'tkazildi.
Natijalar shuni ko'rsatdiki, tavsiya etilgan algoritmlar barcha holatlarda Eyler
yo'lini yoki Eyler siklini yuqori aniqlik bilan aniqlashga qodir. Algoritmlar,
shuningdek, Eyler yo'lini yoki Eyler siklini o'z vaqtida aniqlay oldi, o'rtacha ish
vaqti 0,1 soniyadan kam. Natijalar shuni ko'rsatdiki, algoritmlar 10 000 tagacha
tugun va qirralarga ega bo'lgan grafiklarda Eyler yo'lini yoki Eyler tsiklini
aniqlashga qodir. Natijalar shuni ko'rsatdiki, algoritmlar yuqori darajadagi
ulanishga ega grafiklarda Eyler yo'lini yoki Eyler siklini aniqlashga qodir.
Umuman olganda, natijalar taklif qilingan algoritmlar Eyler yo'lini yoki Eyler
siklini aniqlashning samarali va samarali usuli ekanligini ko'rsatadi.
3.2. Yo'l va siklni aniqlash
Eyler yo'lini yoki Eyler siklini aniqlash uchun grafikga bir qator algoritmlar
qo'llanilgan. Algoritmlar Fleury algoritmi, Hierholzer algoritmi va Xitoy Postman
algoritmi ishlatilgan.
Dastur tanasi:
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);](/data/documents/f8ba04af-61c8-4660-a29e-069a16b93d08/page_12.png)
![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;
}
}
}](/data/documents/f8ba04af-61c8-4660-a29e-069a16b93d08/page_20.png)
![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);](/data/documents/f8ba04af-61c8-4660-a29e-069a16b93d08/page_21.png)
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.
Shuningdek, biz algoritmlarning murakkabligini ko'rib chiqamiz va turli stsenariylarda turli algoritmlardan foydalanish oqibatlarini muhokama qilamiz. 1.2. Eyler yo'li va Eyler tsikli Eyler yo'li va Eyler sikli grafik yo'lini aniqlash uchun ishlatiladigan ikkita muhim algoritmdir. Ular 1735 yilda algoritmlarni birinchi marta ishlab chiqqan shveytsariyalik matematik Leonhard Eyler sharafiga nomlangan. Eyler yo'li - har bir chekkaga bir marta tashrif buyuradigan grafikdagi yo'l, Eyler sikli esa har bir chekkaga bir marta tashrif buyuradigan grafikdagi sikldir. . Grafikning Eyler yo'lini yoki Eyler siklini aniqlash uchun birinchi qadam grafik bog'langan yoki bog'lanmaganligini aniqlashdan iborat. Agar grafik bog'lanmagan bo'lsa, u holda Eyler yo'li yoki siklini topish mumkin emas. Agar grafik ulangan bo'lsa, keyingi qadam grafikning toq darajali cho'qqilari mavjudligini aniqlashdir. Agar toq darajali cho'qqilar bo'lmasa, u holda grafik Eyler sikliga ega. Agar toq darajali cho'qqilar mavjud bo'lsa, u holda grafik Eyler yo'liga ega. Eyler yo'li yoki tsikli aniqlangandan so'ng, algoritm haqiqiy yo'l yoki siklni aniqlash uchun ishlatilishi mumkin. Algoritm toq darajali har qanday cho'qqidan boshlab, so'ngra yo'l yoki tsiklning oxirigacha qirralarni kuzatib boradi. Eyler yo'li yoki sikli keyinchalik yo'lni yoki aylanishni orqaga qarab kuzatish orqali aniqlanishi mumkin. Eyler yo'li va Eyler sikli algoritmlari grafik nazariyasida muhim vosita bo'lib, grafikdagi ikkita nuqta orasidagi eng qisqa yo'lni topish yoki yuk mashinasi uchun eng samarali marshrutni aniqlash kabi turli muammolarni hal qilish uchun ishlatilishi mumkin. Ular tarmoqni loyihalashda ham muhimdir, chunki ular tarmoqdagi turli tugunlarni ulashning eng samarali usulini aniqlash uchun ishlatilishi mumkin. 1.3. Muammo bayoni Eyler yo'li yoki Eyler sikli - bu har bir chekkaga bir marta tashrif buyuradigan grafikdagi yo'l yoki tsikl. Bu muammo Eyler yo'li yoki Eyler sikli muammosi deb nomlanadi. Bu muammo adabiyotlarda keng o‘rganilgan va Eyler yo‘li yoki siklini aniqlash uchun turli algoritmlar taklif qilingan. Ushbu algoritmlarni ikki toifaga bo'lish mumkin: aniq algoritmlar va evristik algoritmlar. Aniq algoritmlar Eyler yo li yoki Eyler sikli muammosiga kafolatlangan yechimniʻ ta minlovchi algoritmlardir. Bu algoritmlar odatda hisoblash qimmat va katta vaqt ʼ va xotirani talab qiladi. Evristik algoritmlar Eyler yo li yoki Eyler sikli masalasiga ʻ taxminiy yechimni ta minlovchi algoritmlardir. Bu algoritmlar odatda hisoblash ʼ