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](https://docx.uz/documents/64455435-3ba3-40f8-810b-d7b5d9f48476/page_7.png?v=1)
![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.](https://docx.uz/documents/64455435-3ba3-40f8-810b-d7b5d9f48476/page_9.png?v=1)
![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](https://docx.uz/documents/64455435-3ba3-40f8-810b-d7b5d9f48476/page_11.png?v=1)
![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);](https://docx.uz/documents/64455435-3ba3-40f8-810b-d7b5d9f48476/page_12.png?v=1)
![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;
}
}
}](https://docx.uz/documents/64455435-3ba3-40f8-810b-d7b5d9f48476/page_20.png?v=1)
![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);](https://docx.uz/documents/64455435-3ba3-40f8-810b-d7b5d9f48476/page_21.png?v=1)
Eyler yo‘li va Eyler siklini aniqlash algoritimi