Sharof rashidov nomidagi samarqand davlat unversititi urgut felyali beznisni boshqarish va tabiiy fanlar fakulteti axborot tizimlari va texnologiyalari yo

O’ZBEKISTON RESPUBLIKASI OLIY VA O’RTA TA’LIM VAZIRLIGI

SHAROF RASHIDOV NOMIDAGI SAMARQAND DAVLAT UNVERSITITI

URGUT FELYALI BEZNISNI BOSHQARISH VA TABIIY FANLAR FAKULTETI

AXBOROT TIZIMLARI VA TEXNOLOGIYALARI YO’NALISHI 107-GURUH TALABASI

AXTAMOVA JAHONANING DISKIRIT MATEMATIKA VA MATMATIK MANTIQ FANIDAN

MUSTAQIL ISHI

MAVZU; Gamilton grafigi
REJA

1. 
   Gamilton grafigi haqida ma’lumot
   
2. 
   SHaxmat o’yindagi ELYER maslasi
   
3. 
   Graflarning matrik xarakteristikalari
   

Bir-biri bilan ustmaust tushmaydigan ixtiyoriy ikkita uchlari bog‘langan graf 
bog‘langan graf deb ataladi.Agar grafdagi ikkita uchni biror oddiy zanjir bilan 
tutashtirish mumkin bo`lsa,u holda bu ikkita uch bog‘langan deyiladi. Bunday 
uchlar to‘plami grafda ekvivalentlik munosabati bilan aniqlangan deb 
hisoblanadi. Uchlar to‘plami bo‘yicha ekvivalentlik munosabatini inobatga
olgan holda berilgan grafni bog‘lamlilik komponentlari deb ataluvchi
bog‘lamli qismlarning birlashmasi deb qarash mumkin.Eyler grafi. Gamilton grafi. Sodda zanjirlarni aniqlash.Yo'naltirilmagan G graf berilgan bo`lsin. Eyler sikli shunday siklki, unda grafning ma'lum bir uchidan chiqib, barcha qirralardan faqat bir marta o'tib, yana shu uchga qaytib kelishi kerak. Grafda Eyler sikli mavjud bo`lishi uchun:
a) Graf bog`langan bo`lishi; 
b) Grafning barcha uchlarining darajalari juft bo`lishi kerak;
Grafda Eyler zanjiri mavjud bo`lishi uchun:
a) Graf boglangan bo`lishi; 
b)Grafning 2 ta uchi darajalari toq bo`lib, qolgan barcha uchlarining darajalari juft
bo`lishi kerak. Grafning barcha qirralaridan bir martadan o`tgan zanjir eyler zanjiri deyiladi Agar G yo`naltirilmagan grafda Eyler sikli mavjud bo`lsa, bunday grafga eyler grafi deyiladi. Boshqacha aytganda,grafning barcha uchlaridan 
o`tuvchi karrali qirralar va ilmoqlarga ega bo`lmagan graf eyler grafi deyiladi. Agar bog`liqli grafda barcha uchlar juft bo`lsa, bu graf eyler sikliga ega bo`ladi. Teskari tasdiq ham o`rinli: agar graf eyler sikliga ega bo`lsa, uning barcha uchlari darajalari juft bo`ladi.Agar grafda oddiy cikl mavjud bo`lib, bu ciklda grafning barcha uchlari qatnashsa, bunday sikl Gamilton sikli deyiladi. Oddiy zanjir Gamilton zanjiri deyiladi, agar bunday grafda uchlarning hammasi ishtirok etsa. Boshqacha aytganda, agar zanjir grafning barcha uchlaridan bir martadan o`tsa, bunday zanjirga gamilton zanjiri deyiladi. Unda uch va qirralar takrorlanmasligi kerak. Grafda Gamilton tsikli mavjud bo`lsa, bu graf Gamilton grafi deyiladi. Yoki agar bog`liqli grafda har bir uchdan faqat bir martadan o`tuvchi sikl mavjud bo`lsa, bunday graf gamilton grafi deyiladi.Berilgan grafikada Hamiltoniya yo'li yoki tsiklining mavjudligi to'g'risida savolga qarang Gemilton yo'lining muammosi.

Oltita tepalik tarmog'i atrofida gamilton davri.In matematik maydoni grafik nazariyasi, a Gemilton yo'li (yoki kuzatiladigan yo'l) a yo'l har biriga tashrif buyuradigan yo'naltirilmagan yoki yo'naltirilgan grafikada tepalik aniq bir marta. A Gamilton tsikli (yoki Gamilton davri) - bu Hamiltoniya yo'li, bu a tsikl. Bunday yo'llar va tsikllarning grafikalarda mavjudligini aniqlash bu Gemilton yo'lining muammosi, bu To'liq emas.

Gamilton yo'llari va tsikllari nomi bilan atalgan Uilyam Rovan Xemilton ixtiro qilgan ikosian o'yini, endi nomi ham tanilgan Xemilton jumboq, ning chekka grafikasida Hamilton tsiklini topishni o'z ichiga oladi dodekaedr. Xemilton bu muammoni ikosian hisobi, an algebraik tuzilish asoslangan birlikning ildizlari ga juda ko'p o'xshashliklari bilan kvaternionlar (shuningdek, Xamilton tomonidan ixtiro qilingan). Ushbu echim o'zboshimchalik bilan grafikalar uchun umumlashtirilmaydi.Hamilton nomi bilan atalganiga qaramay, ko'p qirrali Hamilton davrlari bundan bir yil oldin ham o'rganilgan edi Tomas Kirkman, xususan, Hamilton tsikllari bo'lmagan ko'pburchakka misol keltirgan.^[1] Hamilton davrlari va undan oldinroq ham ritsar grafigi ning shaxmat taxtasi, ritsar safari, 9-asrda o'rganilgan Hind matematikasi tomonidan Rudrata va shu vaqtning o'zida Islom matematikasi tomonidan al-Adli ar-Rumiy. 18-asrda Evropada ritsar turlari tomonidan nashr etilgan Avraam de Moivre va Leonhard Eyler. A Gemilton yo'li yoki kuzatiladigan yo'l a yo'l grafaning har bir tepasiga aniq bir marta tashrif buyuradi. Gamilton yo'lini o'z ichiga olgan grafik a deb nomlanadi kuzatiladigan grafik. Grafik Gemilton bilan bog'liq agar har bir tepalik uchun ikkala tepalik o'rtasida Gemiltoniya yo'li bo'lsa.A Gamilton tsikli, Gamilton davri, vertex tur yoki grafik tsikli a tsikl har bir tepaga aniq bir marta tashrif buyuradi. Gamilton tsiklini o'z ichiga olgan grafik a deb ataladi Gamilton grafikasi.Shunga o'xshash tushunchalar uchun ta'rif berilishi mumkin yo'naltirilgan grafikalar, bu erda yo'lning yoki tsiklning har bir qirrasi (yoyi) faqat bitta yo'nalishda kuzatilishi mumkin (ya'ni tepaliklar o'qlar bilan bog'langan va qirralar "quyruqdan boshga").A Gemilton dekompozitsiyasi grafilning Gamilton davrlariga chekka dekompozitsiyasi.A Xemilton labirinti mantiqiy jumboqning bir turi bo'lib, unda berilgan grafikada noyob Hamilton tsiklini topish maqsad qilingan.
Grafiklarning turlari ularni qurishning umumiy tamoyillari (masalan, ikki tomonlama grafik va Eyler grafigi) bilan aniqlanishi mumkin yoki ular uchlari yoki qirralarning ma'lum xususiyatlariga bog'liq bo'lishi mumkin (masalan, yo'naltirilgan va yo'naltirilmagan grafik, oddiy grafik). ).