Dastlabki tushunchalar
Agar grafikda grafaning barcha uchlarini bir marta o'z ichiga olgan oddiy sikl bo'lsa, bunday sikl Gamilton sikli, grafik esa Gamilton grafigi deb ataladi. Uning har bir cho'qqisidan o'tuvchi oddiy yo'lni o'z ichiga olgan grafik yarim Gamiltonian deb ataladi. Agar yo'l yo'naltirilgan deb hisoblansa, bu ta'rif yo'naltirilgan grafiklarga kengaytirilishi mumkin.
Gamilton siklida grafikning barcha qirralari bo‘lishi shart emas. Ko'rinib turibdiki, faqat bog'langan grafik Gamiltonian bo'lishi mumkin va har bir Gamiltonian grafigi yarim Gamiltoniandir. E'tibor bering, Gamilton sikli har bir grafikda mavjud emas.
Har qanday G grafigini yetarlicha uchlarini qo‘shish orqali Gamilton grafigiga aylantirish mumkin. Buning uchun, masalan, grafikning v1,…, vp uchlariga u1, …, yuqoriga va {(vi, ui)} {(ui, vi+1)} qirralarning toʻplamini qoʻshish kifoya.
V cho'qqisining darajasi unga tushgan d(v) qirralarning soni bo'lib, pastadir ikki marta hisoblanadi. Yo'naltirilgan grafikda do (v) darajasi chiquvchi yoylar bilan va di (v) kiruvchi yo'llar bilan ajralib turadi.
Grafikda Gamilton sikllari mavjudligi uchun bir nechta etarli shartlarni ko'rib chiqing.
Birinchidan, har bir to'liq grafik Gamiltoniandir. Darhaqiqat, u berilgan grafikning barcha uchlari tegishli bo'lgan shunday oddiy tsiklni o'z ichiga oladi. Ikkinchidan, agar grafik, uning barcha uchlari orqali o'tadigan oddiy tsikldan tashqari, boshqa qirralarni ham o'z ichiga olsa, u ham Gamiltoniandir.
Oddiy (Gamiltonian) sikl qattiq chiziq (1, 2), (2, 3), (3, 4), (4, 5), (5, 1) bilan belgilanadi. E'tibor bering, agar grafikda bitta Gamilton tsikli bo'lsa, u boshqa Gamilton tsikliga ega bo'lishi mumkin.
Agar Gamilton grafigi boshqa cho'qqi bilan chekka bilan birlashtirilsa, shunday qilib osilgan cho'qqi hosil bo'lsa, unda bunday grafik Gamilton emas, chunki u grafikning barcha cho'qqilari orqali o'tadigan oddiy tsiklni o'z ichiga olmaydi.
Bir yoki bir nechta cho'qqilari joylashgan "ko'ndalang chiziq" bilan oddiy tsikl bo'lgan grafik ham Gamiltonian emas.
Teorema (Dirak, 1952) Agar n > 3 cho‘qqisi p(v) > n/2 bo‘lgan oddiy grafikda istalgan v uchi uchun G grafigi Gamiltonian bo‘ladi.
Izoh. Bu mashhur teoremaning bir qancha isbotlari bor, bu yerda D.J.Nyumanning isbotini keltiramiz.
Isbot. Grafikimizga har birini G dan har bir cho‘qqi bilan bog‘lab, k ta yangi cho‘qqi qo‘shamiz. Hosil bo‘lgan G grafigining Gamiltonian bo‘lishi uchun zarur bo‘lgan eng kam cho‘qqilar soni k deb faraz qilamiz. Keyin, k > 0 deb faraz qilsak, qarama-qarshilikka erishamiz.
G grafigida v>p>w>…>v Gamilton sikli bo‘lsin, bunda v, w G dan uchlari, p esa yangi cho‘qqilardan biri bo‘lsin. U holda w v ga qo'shni emas, chunki aks holda biz k ning minimalligiga zid bo'lgan p uchidan foydalana olmadik. Bundan tashqari, w ga qo'shni bo'lgan cho'qqi, aytaylik, v ga qo'shni bo'lgan v cho'qqisini darhol kuzatib bo'lmaydi, chunki u holda biz v>p>w>…>v> w>vni v>v> …>w>w> bilan almashtira olamiz. w…>v halqaning w va v orasidagi qismini teskari aylantirish orqali. Bundan kelib chiqadiki, G ning w ga qo'shni bo'lmagan uchlari soni kamida v ga qo'shni bo'lgan cho'qqilar soniga teng (ya'ni, kamida n/2 + k); boshqa tomondan, G grafigining w ga tutashgan uchlari soni ham kamida n/2 + k bo'lishi aniq. Va G grafigining hech bir cho'qqisi bir vaqtning o'zida w cho'qqisiga qo'shni va qo'shni bo'lishi mumkin emasligi sababli, G grafigining n + k ga teng cho'qqilarining umumiy soni n + 2k dan kam emas. Bu orzu qilingan qarama-qarshilik.
Teorema (Ore) 2. Agar G(V, E) grafigining uchlari soni n > 3 boʻlsa va har qanday ikkita qoʻshni boʻlmagan u va v uchlari uchun quyidagi tengsizlik bajariladi:
d(u) + d(v) > n. va (u, v)E, u holda G grafigi Gamiltonian.
Quyidagi shartlardan biri bajarilsa, G grafigi Gamilton sikliga ega bo‘ladi:
Bondi sharti: d(vi) > i va d(vk) > k => d(vi) + d(vk) > n (k ? i dan) )
Chvatala sharti: d(vk) > k > n/2 => d(vn-k) > n k dan.
Bundan tashqari, ma'lumki, deyarli barcha grafiklar Gamiltonian, ya'ni bu erda H(p) - p uchli Gamilton grafiklari to'plami va G(p) - p uchli barcha grafiklar to'plami. Gamilton siklini yoki unga o'xshash sayohatchi sotuvchi muammosini topish muammosi deyarli talabga ega, ammo uni hal qilishning samarali algoritmi noma'lum (ehtimol, mavjud emas).
Grafiklarni almashtirishning asosiy ko’rinishlar
|
