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

muntazam grafik barcha uchlari bir xil darajaga ega boʻlgan bogʻlangan grafik k. Shunday qilib, masalan, 2-rasmda uning uchlari darajasi bo'yicha 4-regular va 2-regular grafiklar yoki 4-darajali va 2-darajali muntazam grafiklar deb ataladigan muntazam grafiklarga misollar ko'rsatilgan.
Muntazam grafikdagi uchlari soni k-chi daraja past bo'lishi mumkin emas k+1. Toq darajali oddiy grafik faqat juft sonli uchlarga ega bo'lishi mumkin.
3-misol Eng qisqa sikl uzunligi 4 ga teng bo'lgan muntazam grafik tuzing.
Yechim. Biz quyidagicha bahslashamiz: tsiklning uzunligi berilgan shartni qondirish uchun grafikning uchlari soni to'rtga karrali bo'lishi kerak. Agar cho'qqilar soni to'rtta bo'lsa, unda quyidagi rasmda ko'rsatilgan grafik olinadi. Bu muntazam, lekin uning eng qisqa siklining uzunligi 3 ga teng.
Cho'qqilar sonini sakkiztagacha oshiring (keyingi raqam to'rtga ko'paytiriladi). Biz cho'qqilarni qirralar bilan bog'laymiz, shunda tepalarning darajalari uchga teng bo'ladi. Masalaning shartlarini qanoatlantiradigan quyidagi grafikni olamiz.
Gamilton grafigi
Gamilton grafigi Gamilton siklini o'z ichiga olgan grafik deyiladi. Hamilton tsikli ko'rib chiqilayotgan grafikning barcha cho'qqilaridan o'tuvchi oddiy sikl deyiladi. Shunday qilib, sodda qilib aytganda, Gamilton grafigi - bu barcha cho'qqilarni kesib o'tish mumkin bo'lgan va har bir cho'qqi o'tish paytida faqat bir marta takrorlanadigan grafikdir. Gamilton grafigiga misol quyidagi rasmda keltirilgan.
4-misol Ikki tomonlama grafik berilgan, unda n- to'plamdan uchlari soni A, lekin m- to'plamdan uchlari soni B. Grafik qaysi holatda Eyler grafigi, qaysi holatda esa Gamilton grafigi?
Oldingi boblarda biz yo'naltirilmagan grafiklar nazariyasining asosiy natijalarini taqdim etgan edik. Biroq, yo'naltirilmagan grafiklar ba'zi vaziyatlarni tasvirlash uchun etarli emas. Masalan, chekkalari ko'chalarga to'g'ri keladigan grafik bilan yo'l harakati xaritasini tasvirlashda, harakatning ruxsat etilgan yo'nalishini ko'rsatish uchun qirralarga yo'nalish belgilanishi kerak. Yana bir misol - grafik yordamida modellashtirilgan kompyuter dasturi, uning qirralari bir ko'rsatmalar to'plamidan boshqasiga boshqarish oqimini ifodalaydi. Dasturning ushbu ko'rinishida chekkalarga boshqaruv oqimining yo'nalishini ko'rsatish uchun yo'nalish ham berilishi kerak. Yo'naltirilgan grafikni ko'rsatishni talab qiladigan jismoniy tizimning yana bir misoli elektr zanjiridir. Yo'naltirilgan grafiklar va tegishli algoritmlarni qo'llash bobda muhokama qilinadi. 11-15.
Ushbu bobda yo'naltirilgan grafiklar nazariyasining asosiy natijalari keltirilgan. Yo'naltirilgan Eyler zanjirlari va Gamilton sikllari mavjudligi bilan bog'liq savollar muhokama qilinadi. Yo'naltirilgan daraxtlar va ularning yo'naltirilgan Eyler zanjirlari