p
(v)=3. Dirak
m
teoremasidagi p(v)>y shart grafdagi
hech qaysi uch uchun bajarilmasa ham, bu grafda (1,2,3,4,5,6, 7,8,1) ko'rinishdagi
Gamilton sikli bor bo'lgani uchun u Gamilton grafidir.
1960-yilda O. Ore quyidagi teoremani isbotladi.
3-teorema (Ore). Agar uchlari soni mga (m>2) teng bo'lgan grafdagi qo'shni
bo'lmagan ixtiyoriy uchlar darajalari yig'ndisi m dan kam bo 'Imasa, иholda bu
graf Gamilton graft bo 'ladi. Isboti
o'quvchiga topshiriq sifatida beriladi.
2-misol.
3-shaklda tasvirlangan graflar Gamilton
graflariga misol bo'la oladilar.Bir qarashdayoq se-zish
mumkinki, bu graflarning har birida bir nechtadan
Gamilton
sikllari
mavjud.Mumkin
bo'lgan
ba'zi
Gamilton sikllari shaklda qa-lin chiziqlar bilan
ifodalangan.
Graf teoriyasi matematik va informatika sohasida grafik modellarni
o'rganishga oid qo'shimcha qo'llanmalar va algoritmlarni tuzishda muhim bo'lgan
bir soha hisoblanadi. Bu soha quyidagi asosiy tushunchalar bilan bog'liq:
Graf - bu, birlashmalardan (edges) va g'ishtlardan (vertices) iborat bo'lgan
matematik konsepti. Birlashmalar g'ishtlarni (yoki ularga oid narsalarni)
bog'laydigan yo'llarni (uchramlar) ifodalaydi. Graf uchun birlashmalarni to'g'ri
yo'nalishi, qo'shimcha ma'lumotlar (masalan, birlashmaning og'irligi yoki turi) kabi
xususiyatlarni ta'riflash mumkin.
Zanjir - bu, grafning birlashmalari va g'ishtlari orqali o'tishni ifodalaydi.
Oddiy zanjir, bitta g'ishtdan boshlab, uni boshqa g'ishtlarga o'tib, boshlang'ich
g'ishtga qayta qaytmaydigan yo'l. Zanjirlar grafda yolg'on yo'llarni (sikllarni)
bildirish uchun foydalaniladi.
Marshrut - bu, grafda bitta g'ishtdan boshlab boshqa g'ishtga yetish uchun
boshqa g'ishtlardan o'tadigan yo'l. Uning birlashmalari va g'ishtlari orqali o'tishni
ifodalaydi va grafning alohida qismi bo'lishi mumkin.
Sikl - bu, grafda qator (bir yoki bir nechta birlashmadan iborat yo'l)
boshlang'ich g'ishtga qayta qaytmaydigan yo'l. Sikl grafda "aloqasiz yo'lovchi"ni
ifodalaydi.
Eyler graf - bu, grafning barcha g'ishtlarida bir nechta birlashmalar bor va
har bir birlashma barcha g'ishtlarga yo'l ochish mumkin bo'lgan graf. Eyler graf
uchun, barcha g'ishtlarining darajalarining juft bo'lishi kerak.
XULOSA
Graf teoriyasi foydalanuvchilar uchun axborotni tahlil qilish, ma'lumotlarni
o'rganish va algoritmlar tuzishda katta ahamiyatga ega. Grafdagi zanjir, marshrut
va sikllar, yo'l yo'nalishlarini, mahsulotlar uchun logistika va tarmoq
topologiyasini o'rganishda va yechimlar qidirishda foydalaniladi. Eyler va
Gamilton graf tushunchalari esa grafning xususiyatlari va aniqlik ko'rsatishda
yordam beradi. Bu tushunchalar va grafik modellar matematik, informatika,
elektronika, transport, kommunikatsiya sohalarida intensiv tarqaladi va ularni
o'rganish va tahlil qilish zamonaviy muammolarga yechim topishda yordam
beradi.
FOYDALANILGAN ADABIYOTLAR
1.
"Introduction to Graph Theory" by Douglas B. West and John G.
Oxley - Bu kitob graf teoriyasining keng qamroq o'rgatishiga va
boshlang'ich tushunchalarini tushuntirishga yordam beradi. Zanjir,
marshrut va sikllar kabi grafning asosiy tushunchalariga asoslangan
bo'lib, ularni teorik va amaliy misollar bilan ta'riflaydi.
2.
"Graph Theory with Applications" by J.A. Bondy and U.S.R. Murty -
Bu kitob graf teoriyasi va uning amaliyotdagi foydalanishlariga oid
holatlar va masalalar bilan to'ldirilgan. Zanjir, marshrut va sikllar
tushunchalari kitobda ko'p misollar orqali tushuntirilgan.
3.
Modern Graph Theory" by Béla Bollobás - Bu kitob graf teoriyasi
tushunchalarini, konseptlarini va muammolarni tahlil qiladi. Zanjir,
marshrut, sikllar, Eyler va Gamilton graf tushunchalari bu kitobda
detalga tushirilgan.
4.
"Graph Theory" by Reinhard Diestel - Bu kitob graf teoriyasi
asoslarini, tushunchalarini va algoritmlarni tushuntiradi. Zanjir,
marshrut, sikllar, Eyler va Gamilton graf tushunchalari ko'p misollar
bilan ta'kidlanib, ularning amaliyotdagi foydalanishlariga misollar
keltirilgan.
5.
coursehero.org
|
