O’zbekiston respublikasi oliy va o’rta-maxsus ta’lim

1- natija. Bog‘lamli graf yarim Eyler grafi bo‘lishi uchun undagi ikkitadan ko‘p bo‘lmagan uchlarning darajalari toq bo‘lishi zarur va yetarlidir.
Isboti 1- teoremaning isbotidan ba’zi o‘zgartirishlar natijasida hosil qilinishi

mumkin.

1- teorema asosida Kyonigsberg ko‘priklari haqidagi masalaning (ushbu bobning 1- paragrafiga qarang) yechimi mavjud emas degan xulosaga kelamiz, ya’ni Kyonigsberg shahrining ixtiyoriy qismida joylashgan uydan chiqib Pregel daryosi ustiga qurilgan yettita ko‘priklardan faqat bir martadan o‘tgan holda, yana o‘sha uyga qaytib kelish mumkin emas.
Oriyentirlangan graflarda oriyentirlangan Eyler yo‘lini izlash bilan shug‘ullanish mumkin. Har bir yoydan faqat bir marta o‘tadigan yo‘l oriyentirlangan Eyler yo‘li deb ataladi. Tarkibida oriyentirlangan Eyler yo‘li bor bo‘lgan oriyentirlangan graf oriyentirlangan Eyler grafi deb ataladi.
3- teorema (Ore). Agar uchlari soni ga ( ) teng bo‘lgan grafdagi qo‘shni bo‘lmagan ixtiyoriy uchlar darajalari yig‘ndisi dan kam bo‘lmasa, u holda bu graf Gamilton grafi bo‘ladi.
4- misol. 5- shaklda tasvirlangan grafda Gamilton zanjiri mavjud emas.

Berilgan grafda Gamilton zanjirining mavjudligi shartlarni o‘rganish bo‘yicha izlanishlar davom etayotganligi va bu sohadagi ishlar bugungi kunda ham dolzarbligini yo‘qotmaganligi yuqorida qayd etilgan edi. Grafdagi uchlar soni ning qiymatiga nisbatan ko‘phad bilan chegaralangan sondagi qadam ishlatib istalgan grafda Gamilton zanjiri mavjudligini tekshiradigan algoritm hozirgacha topilmagan. Shuning uchun ham Gamilton zanjirini topish masalasi graflar nazariyasida markaziy masalalardan biri bo‘lib qolmoqda, Albatta, grafdagi ta uchlarning ta turli ketma-ketliklarini (aniqrog‘i, takrorlanmaydigan o‘rin almashtirishlarini) tuzib grafda Hamilton zanjiri mavjudligi masalasini hal qilish mumkin. Shunday bo‘lishiga qaramasdan, barcha ta o‘rin almashtirishlarini bajarmasdan qadamlar sonini jiddiy qisqartiradigan umumiy algoritm bor.

Uchlar qoshnilik matritsasi:

0 -1 1 1 1 0 1 0 -1 1 0 1 1 0 1 1

#include

#include
#define NODE 5
using namespace std;
int graph[NODE][NODE] = {
{0, -1, 1, 1, },
{1, 0, 1, 0, },
{-1, 1, 0, -1, },
{1, 0, 1, 1, },
};//uchlar qo'shnilik matritsasi
/*int graph[NODE][TUGUN] = {{0, 1, 1, 1, 1},
{1, 0, 1, 0, 0},
{1, 1, 0, 0, 0},
{1, 0, 0, 0, 1},

{1, 0, 0, 1, 0}};*/ //Eyler sxemasini va yo'lni tekshirish uchun izohni bekor qiling

/*int grafigi[NODE][TUGUN] = {{0, 1, 1, 1, 0},
{1, 0, 1, 1, 0},
{1, 1, 0, 0, 0},
{1, 1, 0, 0, 1},
{0, 0, 0, 1, 0}};*/ //Non Eulerian Grafikni tekshirish uchun izohni olib tashlang
void traverse(int u, bool visited[]) {
visited[u] = true; //v tashrif buyurilgan deb belgilang
for(int v = 0; vif(graph[u][v]) {
if(!visited[v])
traverse(v, visited);
} } }
bool isConnected() {
bool *vis = new bool[NODE];
//boshlanish nuqtasi sifatida barcha u nuqtalari uchun barcha tugunlar ko'rinadigan yoki yo'qligini tekshiring
for(int u; u < NODE; u++) {
for(int i = 0; ivis[i] = false; // hech qanday tugunga tashrif buyurmaganligi sababli ishga tushirish
traverse(u, vis);
for(int i = 0; iif(!vis[i]) //agar o'tish orqali tashrif buyurilmagan tugun bo'lsa, grafik ulanmagan

return false;
} }
return true;}
int isEulerian() {
if(isConnected() == false) //grafik ulanmagan bo'lsa
return 0;
vector degree(NODE, 0);
int oddDegree = 0;
for(int i = 0; ifor(int j = 0; jif(graph[i][j])
degree[i]++;//darajani oshiring, ulangan chekka topilganda
}
if(degree[i] % 2 != 0) //cho'qqilar darajasi toq bo'lganda
oddDegree++; //toq darajali uchlarini sanash
}
if(oddDegree > 2)//toq darajali uchlari 2 dan katta bo'lganda
return 0;
return 1; // oddDegree 0 bo'lsa, bu Eyler davri, 2 bo'lsa, Eyler yo'li.
}
int main() {
if(isEulerian() != 0) {

cout << "Grafikda Eyler yo'li mavjud." << endl;

} else {
cout << "Grafikda Eyler yo'li mavjud emas." << endl;
} }