Maktabga bo'lgan yo'lim bo'yash kitobi. Yo'l qoidalari sahifalarni bo'yash

Sayt yangilanishi
10.12.2006 15:46
Avtomobillar va multfilmlar muxlislari uchun - "Avtomobillar" multfilmidan rang berish sahifalari.

Disney va Pixar tufayli 2006 yil iyun oyida butun dunyo multfilmni ko'rdi, unda faqat avtomobillar qahramonga aylandi.

“Avtomobillar” (“Avtomobillar”) multfilmidagi avtomobillar oddiy hayot kechiradi – biri kauchuk do‘konida, ikkinchisi tyuning studiyasida, ba’zilari esa shunchaki o‘z zavq-shavqlari uchun yashaydi, masalan, hippi Fillmor (Volkswagen T1) yoki uning do‘sti – faxriy Ikkinchi jahon urushi Serj (Willys). "Chaqmoq" laqabli Makkuinning bosh qahramoni faqat poyga, g'alaba va shon-shuhratni orzu qiladi. Bir marta AQShning mashhur 66-magistralidagi Radiator tumanida "yashil" McQueen darhol hammaga qanchalik tez va salqin ekanligini aytadi. Biroq, NASCAR poygasidagi birinchi start uning illyuziyalarini yo'q qiladi. Do'stlar qahramonga yo'qotishdan omon qolishga yordam berishadi - eski Meiter evakuatori (GMC Pick-up), murabbiy Dok Hudson (Gudson Hornet) va haqiqiy Ferrarini ko'rishni orzu qiladigan kichkina Luidji (Fiat 600).

Xo'sh, qayerda romantik go'zallik Sally (maftunkor 911 tatuirovkasi bilan Porsche) bo'lmasa! Ularga katta rahmat, Makkuin asosiy raqibi Chikoni (Plimut Xemi Kuda) mag'lub etib, poygada g'olib chiqadi. Luidjining orzusi ham amalga oshadi – bir kuni “Maranellolik ayg‘ir” o‘z do‘koniga shinalarni almashtirish uchun qo‘ng‘iroq qiladi, darvoqe, buni “Qizil baron” Mixael Shumaxerning o‘zi aytgan edi.

Shunisi e'tiborga loyiqki, rasm yaratuvchilar ham, uni ovozga qo'yganlar ham avtomobillarga aloqador odamlardir. Misol uchun, rejissyor Jo Lasseter bolaligining ko'p qismini Chevrolet zavodida o'tkazgan, u erda otasi bosh dizaynerlardan biri bo'lgan. Maslahatchi sifatida Ford konsernining yetakchi dizayneri Jey Meys ishladi. Qahramonlar ovozini berishda yuqorida aytib o‘tilgan Formula 1 bo‘yicha yetti karra jahon chempioni Mixael Shumaxerdan tashqari, NASCAR yulduzlari Richard Petti va Pol Nyuman, shuningdek, afsonaviy poygachi Maykl Andretti ham ishtirok etishdi.

Faqat avtomobilning asl shovqinidan foydalanilgan - masalan, poyga epizodlari uchun, NASCAR musobaqalarida ovoz bir necha hafta davomida Amerika ovallarida yozilgan. Byudjeti 70 million dollarni tashkil etgan suratni yaratish uchun ikki yildan ko'proq vaqt ketdi. Shu vaqt ichida avtomobillarning 43 ming xil eskizlari yaratildi va har bir chizmaga 17 soatdan ko‘proq vaqt kerak bo‘ldi. Filmda yangi Porsche va Ferrarilardan tortib antiqa Ford Tsgacha jami 120 ta avtomobil personajlari mavjud.

O'g'il bolalarni qum qutisida mashinalar bilan o'ynashga taklif qilsangiz, ularni uzoq vaqt band qilishingiz mumkin. Ammo tashqarida sovuq bo'lsa, bola zerikadi. Bunday holda, siz quyidagi avtomobil yo'llari shablonlarini yuklab olishingiz va chop etishingiz mumkin. O'yin-kulgi barcha halqalarni, burilishlarni va tekis yo'llarni kesish bilan boshlanadi. Ushbu shablonlardan bola har qanday shakldagi yo'lni qurishi mumkin, faqat kerakli miqdordagi A4 varaqlari chop etilganligiga ishonch hosil qiling.

Avtomobillar uchun to'g'ri yo'l yuklab olish

Ushbu varaqlar eng ko'p kerak bo'ladi. A4 formatidagi varaqda biz chop etish va kesish kerak bo'lgan 3 ta yo'lni joylashtirdik. Farzandingizga qismni kerakli uzunlikka aylantirish uchun yo'lni qanday qilib to'g'ri burchak ostida kesish kerakligini ko'rsating.

Avtomobillar uchun yo'l: halqa

Yo'llarni ulash uchun sizga shablon yuqorida keltirilgan halqa kerak bo'ladi va undan infratuzilmangizni qurishni boshlang.

Avtomobil yo'li: To'g'ri burilish

Taqdim etilgan burilishlar bolaga yo'lni 90 darajaga, o'zi kerak bo'lgan tomonga burish imkonini beradi.

Avtomobillar uchun yo'lning keskin burilishi emas

Quyidagi A4 shablon yo'lni istalgan radius ostida burishga yordam beradi.

Siz yo'lni bo'yash sahifasidasiz. Siz ko'rayotgan rang sahifamiz tashrif buyuruvchilarimiz tomonidan quyidagicha ta'riflangan "" Bu yerda siz onlaynda juda ko'p rang berish sahifalarini topasiz. Siz yo'llarni bo'yash sahifalarini yuklab olishingiz va ularni bepul chop etishingiz mumkin. Ma'lumki, ijodiy faoliyat bolaning rivojlanishida katta rol o'ynaydi. Ular aqliy faoliyatni faollashtiradi, estetik didni shakllantiradi va san'atga muhabbat uyg'otadi. Yo'l mavzusidagi rasmlarni bo'yash jarayoni nozik vosita mahoratini, qat'iyatlilik va aniqlikni rivojlantiradi, atrofimizdagi dunyo haqida ko'proq ma'lumot olishga yordam beradi, sizni ranglar va soyalarning xilma-xilligi bilan tanishtiradi. Har kuni biz o'g'il bolalar va qizlar uchun yangi bepul rang berish sahifalarini veb-saytimizga qo'shamiz, ularni onlayn bo'yashingiz yoki yuklab olishingiz va chop etishingiz mumkin. Kategoriyalar bo'yicha tuzilgan qulay katalog to'g'ri rasmni topishni osonlashtiradi va rang berish sahifalarining katta tanlovi har kuni rang berish uchun yangi qiziqarli mavzuni topishga imkon beradi.

Bolaning Yo'l harakati qoidalarini bilishi uning ko'chada xavfsizligining asosiy shartlaridan biridir. Ko'pgina piyodalar, shu jumladan kattalar ham ushbu qoidalarga nisbatan beparvo munosabatda bo'lishadi, bu ko'pincha turli darajadagi yo'l-transport hodisalariga sabab bo'ladi. Bolalar qishloqda ko'chada bo'lish, ular yo'lning to'liq ishtirokchisi ekanligini aniq tushunishlari kerak, shuning uchun yo'l harakati qoidalariga rioya qilish ularning mas'uliyati.

Rangli sahifalar bolalar uchun yo'l qoidalari.

Bolaga ko'chada o'zini tutish qoidalarini (yo'llar, yo'laklar, shahar transporti) o'rgatish juda erta yoshdan, u mustaqil ravishda yurish va yugurishni o'rganmasdan boshlanishi kerak. Va bu erda bola ko'chada bo'lgan ota-onalar va boshqa kattalar misoli juda muhimdir. Siz bolangizga nafaqat yo'l qoidalarini aytib berishingiz va tushuntirishingiz, balki ularga o'zingiz ham qat'iy rioya qilishingiz kerak. Ushbu sahifadagi yo'l harakati qoidalarini bo'yash sahifalari birinchi navbatda maktabgacha yoshdagi bolalar uchun mo'ljallangan va bolalarga yo'lda, shuningdek, uning yonida xatti-harakatlar asoslarini o'rganishga yordam beradi.

1. Svetoforning rang berish sahifasi.

Yo'lni xavfsiz kesib o'tish uchun eng yaxshi joy svetoforlar bilan jihozlangan piyodalar o'tish joyidir. Svetoforni bo'yash sahifalarida bolalar undan foydalanish qoidalarini osonroq eslab qolishlariga yordam beradigan kichik qofiyalar ham mavjud.

• Har doim faqat svetoforning yashil chirog'i yonganda haydashni boshlang.
• Hech qachon qizil yoki sariq svetoforlarda, hatto yaqin atrofda transport vositalari bo'lmasa ham, yo'lni kesib o'tmang.
• Yashil chiroqni yoqqaningizda, qo'shimcha ravishda xavfsiz ekanligingizga ishonch hosil qiling - chapga, keyin o'ngga qarang.

2. Piyodalar o'tish joyini bo'yash.

Farzandingizni qatnov qismini faqat piyodalar o'tish joyida kesib o'tishga o'rgating. Piyodalar o'tish joylarini bo'yash sahifalari bolalarni yo'lni to'g'ri kesib o'tishga o'rgatadi. Svetofor bilan jihozlanmagan o'tish joyi tartibga solinmagan deb ataladi.

• Piyodalar o'tish joyi yo'l yuzasida zebra bilan belgilangan.
• Yo'lni kesib o'tishdan oldin uni diqqat bilan tekshiring, yaqin atrofda harakat yo'qligiga ishonch hosil qiling.
• Yo'lni kesib o'ting, kesib o'tmang.
• Ko'chani kesib o'tmang.
• Ko'rinishingizni to'sib qo'yadigan tik turgan transport vositalariga alohida e'tibor bering.
• Piyodalar o'tish joyidan o'tayotganda telefonda gaplashishni to'xtating.
• Agar yaqin atrofda er osti yoki baland o'tish joylari bo'lsa, ulardan foydalanishga ishonch hosil qiling, bunday joylarda transport ayniqsa qizg'in.

3. Piyodalar yo‘laklari.

Piyodalar yo'lakchasi piyodalar harakatiga mo'ljallangan. Bolalarni piyodalar yo'laklarida, ayniqsa transport zich joylashgan joylarda o'zini to'g'ri tutishga undash.

• Yo'l bo'ylab piyodalar yo'lagida harakatlanayotganda, unga juda yaqinlashmang.
• Avtoulovlarning hovlilardan, xiyobonlardan chiqishi mumkin bo'lgan joylarini diqqat bilan kuzatib boring.
• Yo'lakda to'p o'ynamang, yugurmang.

4. Shahar jamoat transportida va avtobus bekatlarida bolalarning xulq-atvori qoidalari aks etgan rang sahifalari.

Ushbu rang berish sahifalari bolalarga jamoat transportidan xavfsiz foydalanish qoidalarini o'rgatadi.

• Jamoat transporti to'xtash joyi xavfli joy bo'lib, yo'lning yomon ko'rinishi va ko'plab odamlar bolani tasodifan piyodalar yo'lakchasidan yo'l qismiga surib qo'yishi mumkin. Bu erda siz ayniqsa ehtiyot bo'lishingiz kerak.
• Transport eshiklariga faqat u to'liq to'xtaganidan keyin yaqinlashing.
• Avtomobilni tark etgandan so'ng, to'xtash joyidan chiqqandan keyingina yo'lni kesib o'tishni davom eting.

Yo'l harakatining ushbu asosiy qoidalariga qo'shimcha ravishda, bolalar yo'l belgilarini bo'yashga qiziqishadi. Yo'l harakati qoidalariga muvofiq taqdim etilgan rang berish sahifalari bolalar, maktabgacha yoshdagi bolalar va boshlang'ich maktab yoshidagi o'quvchilar uchun, shuningdek, bolalar bog'chalarida va boshlang'ich maktab darslarida foydalanish uchun javob beradi. Yo'l harakati qoidalari bilan barcha rasmlar mutlaqo bepul - ularni yuklab olish va chop etish mumkin.

(Ushbu yozuv matematikadan ma'lumotga ega bo'lgan o'quvchilar va xayrixohlar uchun qiziqarli bo'lishi mumkin)

Boshqa kuni men grafik nazariyasidan qiziqarli muammo - yo'lni bo'yash gipotezasi haqida o'qidim. Bu faraz 37 yil davomida ochiq edi, lekin uch yil oldin buni isroillik matematik Avraam Traxtman isbotlagan. Dalil juda oddiy bo'lib chiqdi va ba'zi qiyinchiliklar bilan (miyam atrofiyaga uchraganligi sababli) men uni o'qishga va tushunishga muvaffaq bo'ldim va hatto buni ushbu yozuvda tushuntirishga harakat qilaman.

Muammoni misol bilan tushuntirish mumkin. Har bir chorrahada siz to'rt yo'nalishdan biriga - shimolga, janubga, sharqqa va g'arbga borishingiz mumkin bo'lgan shahar xaritasini tasavvur qiling. Agar mashina biron bir chorrahadan boshlansa va ba'zi yo'nalishlar ro'yxatiga amal qilsa - "shimol, shimol, sharq" va hokazo. - keyin u boshqa chorrahaga yetib boradi. Qaerda boshlanganidan qat'i nazar, mashinani bir joyga olib boradigan bunday yo'nalishlar ro'yxatini, ehtimol, uzoqni topish mumkinmi? Agar xarita Manxettenga o'xshasa - oddiy to'r - yo'q, lekin unda ko'plab o'lik nuqtalar va kutilmagan burilishlar bormi?

Yoki boshqa misol. Sizning do'stingiz markazni topishingiz kerak bo'lgan labirintda qolib ketdi va sizga yordam so'rab qo'ng'iroq qildi. Siz labirint qanday ishlashini bilasiz, lekin do'stingiz qaerdaligini bilmaysiz. Do'stingizni qayerda bo'lishidan qat'i nazar, albatta markazga olib boradigan buyruqlar ketma-ketligi bo'lishi mumkinmi?

Ushbu ikkita misolda har bir nuqtadagi "yo'nalishlar" aniqlangan va yechim mavjud yoki yo'q. Ammo umumiyroq holatda, bu muammo so'raydi: agar biz, masalan, "g'arbiy, shimol, sharq, janub" nuqtalarini, har bir chorrahada o'ziga xos tarzda tanlay olsak, "sinxronlashuvchi so'z" mavjudligini ta'minlay olamizmi? " - buyruqlar ketma-ketligi, qaysi bir joydan bitta sobitga olib keladi?

Umumiy holda, yo'naltirilgan G grafigi bo'lsin - uchlari orasidagi "o'q" qirralari bilan. Bu grafik bir xil chiquvchi darajaga ega bo'lsin d - bu aniq d qirralarning har bir cho'qqidan chiqib ketishini anglatadi. Shu bilan birga, har bir alohida tepaga har xil raqam, albatta, d emas, kirishi mumkin. Aytaylik, bizda qandaydir alifboning d harflari to'plami bor, biz ularni "gullar" deb ataymiz. Keyin grafikning "rangi" har bir cho'qqi uchun uning chiqadigan qirralarining d uchun barcha d harflarini belgilash orqali beriladi. Shunday qilib, agar biz biron bir cho'qqida "joylashgan" bo'lsak va biz a rangiga ko'ra biror joyga "ketmoqchi" bo'lsak, rang berish har doim bizga qaysi chekkaga qaysi yangi cho'qqiga borishimiz kerakligini aytadi. "So'z" har qanday harf ranglari ketma-ketligidir. Keyin, agar grafikda rang berilgan bo'lsa va x - qandaydir cho'qqi va w - qandaydir so'z bo'lsa, xw biz erishadigan cho'qqini x dan boshlab va w so'zidan keyin bildiradi.

Rang berish kitobi deyiladi sinxronlash, har qanday x cho'qqisini bitta qo'zg'almas x 0 ga olib boradigan so'z w bo'lsa. Bu holda w deyiladi so'zni sinxronlash. Yo'lni bo'yash muammosi so'ragan savol: har doim sinxron rang berish bormi? Grafikning chekkalarini har doim hamma uchlarini bittaga qisqartiradigan tarzda ranglash mumkinmi?

Bu muammo, masalan, Vikipediyada o'qilishi mumkin bo'lgan bir nechta turli sohalarda ilovalarga ega. Masalan, kompyuter fanida, avtomatlar nazariyasida. Rangli grafikni deterministik chekli holat mashinasi sifatida ko'rish mumkin, uning cho'qqilari holatlar bo'lib, qirralari ular orasida qanday harakat qilishni ko'rsatadi. Aytaylik, biz bu avtomatni masofadan turib boshqarib, qandaydir ma'lumot kanali orqali buyruqlar yuboramiz va ba'zi buzilishlar tufayli bu kanal ifloslangan, avtomat noto'g'ri ko'rsatmalar olgan va endi biz uning qanday holatda ekanligini umuman bilmaymiz. Keyin, agar sinxronlash so'zi bo'lsa, biz uni hozir qaerda bo'lishidan qat'i nazar, ma'lum holatga keltira olamiz.

Xo'sh, sinxron rang berish qachon mavjud? Yo'lni bo'yash bo'yicha gipoteza grafikda yana ikkita cheklovni qo'yadi (har bir cho'qqida aniq d qirrasi borligidan tashqari). Birinchidan, grafik kuchli bog'langan bo'lishi kerak, ya'ni har qanday cho'qqidan boshqasiga marshrut mavjud. Ikkinchidan, grafik davriy bo'lmasligi kerak. Tasavvur qiling-a, barcha grafik uchlarini V 1 , V 2 , ... V n toʻplamlarga boʻlish mumkin, shunda grafikning istalgan chekkasi baʼzi V i va V i+1 yoki V n va V 0 dan uchlarini bogʻlaydi. Har bir V ning cho'qqilari o'rtasida chekkalar yo'q va ular har qanday V o'rtasida ham "sakrash" mumkin emas, faqat tartibda. Bunday grafik davriy deb ataladi. Bunday grafik sinxronlashtiruvchi rangga ega bo'lmasligi aniq, chunki siz qanday rang va qanday so'zlarni o'tishingizdan qat'i nazar, har xil V i dagi ikkita cho'qqi hech qachon birlashmaydi - ular tsikl bo'ylab harakatlanadi.

Yo'lni bo'yash teoremasi bu shartlar etarli ekanligini aytadi: Har bir cho'qqidan d qirrali har qanday davriy bo'lmagan kuchli bog'langan yo'naltirilgan grafik sinxronlashtiruvchi rangga ega. U birinchi marta 1970 yilda faraz sifatida shakllantirilgan va o'shandan beri alohida holatlarni isbotlovchi ko'plab qisman natijalar mavjud edi, ammo to'liq isbot faqat 2007 yilda paydo bo'ldi. Quyida men deyarli barcha dalillarni qayta aytib beraman (bitta texnik lemmadan tashqari).

Davriylik

Avvalo, davriy bo'lmagan shartni unga ekvivalent bo'lgan boshqa shart bilan almashtiramiz. Grafikda har qanday sikl uzunligini ajratuvchi N>1 raqami mavjud bo‘lgandagina grafik davriy hisoblanadi. Bular. Davriylik talabimiz bunday N yo‘qligini aytishga teng, yoki boshqacha qilib aytganda, grafikdagi barcha davrlar uzunliklarining eng katta umumiy bo‘luvchisi 1 ga teng. Bu shartni qanoatlantiradigan har qanday grafikning rang berishni sinxronlash.

Davriylikning "har qanday sikl uzunligi bo'linadigan N>1 bor" shartiga ekvivalentligini isbotlash bir yo'nalishda ahamiyatsiz, ikkinchisida esa oson. Agar siz buni ishonch bilan qabul qilishga tayyor bo'lsangiz, ushbu paragrafning qolgan qismini osongina o'tkazib yuborishingiz mumkin; qolgan dalillar uchun bu muhim emas. Grafik davriy bo'lsa, ya'ni. Cho'qqilarni V 1 , V 2 , ... V n to'plamlarga bo'lish mumkin bo'lganligi sababli, chekkalar ular orasidan bir tsiklda o'tadi, demak, har qanday tsiklning uzunligi n ga bo'linishi kerakligi aniq bo'ladi, ya'ni. yangi shart bajariladi. Bu arzimas yo'nalish, ammo bizning o'rnimizni almashtirish uchun bizga faqat ikkinchi yo'nalish kerak. Faraz qilaylik, har qanday sikl uzunligini ajratuvchi shunday N>1 bor. Grafikimizda ildizi r cho'qqisida joylashgan bir nechta yo'naltirilgan kengaytmali daraxtni (ko'lamli daraxt) quraylik. Bu daraxtda l(x) uzunlikdagi ildizdan boshlanadigan istalgan x tepasiga marshrut mavjud. Endi biz grafikdagi istalgan p-->q chekkasi uchun l(q) = l(p) + 1 (mod N) bo‘lishini da’vo qilamiz. Agar bu gap to'g'ri bo'lsa, unda biz darhol barcha uchlarni l(x) mod N ga ko'ra V i to'plamlarga bo'lishimiz mumkin, va grafik davriy bo'ladi. Nima uchun bu bayonot haqiqat? Agar p-->q yoyilgan daraxtning bir qismi bo'lsa, bu aniq, chunki u holda faqat l(q) = l(p) + 1. Agar bunday bo'lmasa, u holda r ildizidan boshlab marshrutlarni yozamiz. p,q uchlari R p va R q kabi. Shuningdek, R r grafikdagi q dan r gacha bo'lgan marshrutni bildirsin (grafik bog'langan, shuning uchun u mavjud). Keyin ikkita sikl yozishimiz mumkin: R p p-->q R r va R q R r. Shartga ko'ra, bu sikllarning uzunliklari N ga bo'linadi, umumiy qiymatlarni ayirish va bekor qilish orqali biz isbotlanishi kerak bo'lgan l(p)+1 = l(q) mod N ni olamiz.

Barqaror do'stlik va induksiya

G grafigining qandaydir bo'yalishi berilsin.Ikkita cho'qqini p,q do'st deb ataymiz, agar biron bir w so'zi ularni bir cho'qqiga olib kelsa: pw = qw. Keling, p,q dushmanlarini "uchrashmasalar" deylik. Har qanday so'zni bajargandan so'ng ular do'st bo'lib qolsalar, keling, p,q barqaror do'stlarni chaqiraylik: pw qw bilan bir xil cho'qqiga chiqmasligi mumkin, lekin yana bir necha w" dan keyin kelishi mumkin. Barqaror do'stlar hech qachon dushman bo'lmaydi.

Cho'qqilar orasidagi barqarorlik munosabati, birinchidan, ekvivalentlikdir (u refleksli, simmetrik va o'tishli), ikkinchidan, u grafik tuzilishi bilan saqlanadi: agar p, q barqaror do'stlar bo'lsa, p p bilan chekka bilan bog'langan. , q bilan q" va bu qirralar bir xil rangda, keyin p" va q" ham barqaror do'stlardir. Bu barqaror do'stlik ekanligini anglatadi muvofiqlik va uni ajratish mumkin: yangi grafik yaratish G ", uning cho'qqilari barqaror do'stlik ekvivalentlik sinflar bo'ladi G. Agar G kamida bitta barqaror juft bo'lsa, keyin G" hajmi G dan kichik bo'ladi. Bundan tashqari, agar asl grafigida har bir cho‘qqidan G ning d chekkalari bo‘lsa, G” da ham xuddi shunday bo‘ladi. Masalan, agar P yangi grafikning cho‘qqisi bo‘lsa, ya’ni p1, p2 asl cho‘qqilarning ekvivalentlik klassi... , va a har qanday rang bo'lsa, u holda p1--a--> q1, p2---a-->q2 va hokazo qirralarning barchasi q1, q2... cho'qqilariga olib keladi, ular har biri bilan barqaror do'stlikda bo'ladi. boshqa va shuning uchun bitta yangi Q cho'qqisida yotadi, shunda bu qirralarning barchasi yangi chekka P --a-->Q ga aylanadi va har bir d rang uchun shunday davom etadi.

Bundan tashqari, agar G davriy bo'lmagan bo'lsa, u holda G" bo'ladi. Chunki - davriylikning muqobil ta'rifidan foydalangan holda - G dagi har qanday tsikl G" dagi tsiklga aylanadi, shuning uchun G" dagi barcha tsikl uzunliklari n > 1 ga bo'linadigan bo'lsa, u holda G. ning barcha sikllari uchun ham xuddi shunday.

Faraz qilaylik, G" da biz sinxronlashtiruvchi rangni topdik. Endi uni biz boshlagan rang o'rniga G da ishlatish mumkin: har qanday chekka p-->q chekkaning yangi rangiga ko'ra yangi rang oladi. P-->Q. Aniqroq qilib aytadigan bo'lsak: G" grafigining har bir P cho'qqisida barcha ranglarning o'zgarishi bilan yangi rang beriladi p P: a rangi bilan bo'yalgan chekka yangi rangga ega bo'ladi. rang p P (a). Keyin dastlabki G grafigida, barqarorlik sinfi P dan har bir p cho'qqisida uning qirralarini qayta bo'yash uchun bir xil p P almashtirishni qo'llaymiz. G grafigining yangi bo'yalishi odatda "do'stlik", "dushmanlik" va "barqarorlik" kabi ba'zi yangi tushunchalarni belgilaydi, ular asl tushunchalarga o'xshamaydi. Ammo shunga qaramay, agar ikkita p, q cho'qqilari eski rangda barqaror do'st bo'lsa - bir xil P sinfiga tegishli bo'lsa, yangisida ular barqaror do'st bo'lib qoladilar. Buning sababi shundaki, p,q ni bitta cho'qqiga olib keladigan har qanday w ketma-ketligi yo'l bo'ylab p ning har bir cho'qqisida p P almashtirish yordamida eski rangdan yangisiga yoki aksincha, "ko'chirilishi" mumkin. P,q eski rang berishda barqaror bo'lgani uchun va "butun yo'lda" shundayligicha qolib ketganligi sababli, p,q dan umumiy cho'qqigacha bo'lgan yo'lda p n, q n cho'qqilarning har bir oraliq juftligi barqaror bo'ladi, ya'ni. bir xil cho'qqi ichida yotadi P n va shuning uchun bir xil almashtirishni qabul qiladi p P n .

Yangi rang berish G" uchun sinxronlashtirilmoqda, ya'ni qandaydir w ketma-ketligi barcha cho'qqilarni bitta P cho'qqisiga olib keladi. Agar G'dagi yangi rangga w qo'llasak, u holda barcha cho'qqilar "P ichida" bir joyda birlashadi. Yuqorida aytib o'tilganidek, hammasi P sinfidagi cho'qqilar yangi rang berishda barqaror bo'lib qoladi, ya'ni biz endi w ni davom ettirishimiz mumkin, qolgan juft uchlarini bir-biridan ajratib, qayta-qayta birlashtirib, hamma narsa bir G cho'qqisiga yaqinlashguncha. Shunday qilib, yangi rang berish G uchun sinxronlashtirilmoqda.

Bularning barchasidan kelib chiqadiki, teoremani isbotlash uchun shartlarga javob beradigan har qanday grafikda bir juft barqaror do'stlar mavjud bo'lgan rang mavjudligini isbotlash kifoya. Chunki u holda G grafigidan G" grafigiga o'lchami kichikroq bo'ladi va u ham barcha shartlarga javob beradi. Induktiv argumentdan foydalanib, kichikroq o'lchamdagi grafiklar uchun masala allaqachon yechilgan deb taxmin qilishimiz mumkin. keyin G" uchun sinxronlashtiruvchi rang ham G uchun sinxronlashtiriladi.

Kliklar va maksimal to'plamlar

Grafik cho'qqilarining har qanday A kichik to'plami va w so'zi uchun Aw biz A ning barcha uchlaridan boshlab va w so'zidan keyin keladigan cho'qqilar to'plamini bildiradi. Agar biz umumiy grafikning barcha uchlaridan boshlasak, buni Gw bilan belgilaymiz. Ushbu belgida rangni sinxronlash, Gw bitta element to'plami bo'ladigan w mavjudligini anglatadi.

Agar A cho'qqi to'plami ba'zi w uchun Gw ko'rinishiga ega bo'lsa va qo'shimcha ravishda A ning istalgan ikkita cho'qqisi dushman bo'lsa, ya'ni. hech qachon birlashmang, keling, A ni chaqiraylik klik. Kliklar mavjud, chunki biz har doim butun G bilan boshlay olamiz, bir juft do'st uchlarini olamiz, ularni bog'laydigan w ni kesib o'tamiz va uchlari sonini bittaga kamaytiramiz; faqat dushmanlar qolmaguncha yoki faqat bitta cho'qqi qolmaguncha shunday davom eting - bu holda ham bir guruh, shunchaki ahamiyatsiz.

Agar A klik bo'lsa, u holda har qanday so'z uchun w Aw ham klik; bu aniq, chunki dushmanlar dushman bo'lib qoladilar. Agar x grafaning istalgan cho'qqisi bo'lsa, unda x ni o'z ichiga olgan klik mavjud. Bu A guruhining mavjudligidan kelib chiqadi (oldingi xatboshiga qarang); agar p unda cho'qqi bo'lsa, u holda p dan x gacha bo'lgan w so'zi mavjud, chunki bog'langan grafik; u holda Aw - x, shu jumladan, klika.

Bosish bizga barqaror do'stlar bilan rang berish mavjudligini isbotlashga yordam beradi - oldingi bo'limga ko'ra, bu teoremani isbotlash uchun etarli. Ushbu bo'lim davomida biz ikkita A va B kliklari mavjud bo'lsa, ulardagi barcha cho'qqilar umumiy bo'lsa, A va B dagi bittadan tashqari, bu ikki cho'qqi barqaror do'st ekanligini isbotlaymiz. Shunday qilib, muammo A va B guruhlarini o'z ichiga olgan rangni topishga tushadi.

Kliklarning qanday ishlashini yaxshiroq tushunish uchun grafikdagi cho'qqilarga og'irliklarni belgilash foydalidir. Keling, har bir x cho'qqisiga musbat og'irlik w(x) ni belgilash yo'li borligini ko'rsatamiz, shuning uchun agar biron bir x cho'qqi uchun bo'lsa. x ning qirralari bo'lgan barcha cho'qqilarning og'irliklarini yig'ing, keyin biz d * w (x) olamiz, bu erda d - har bir tepadan qirralarning soni. Bu chiziqli algebradan kelib chiqadi va agar siz o'z qiymat nima ekanligini bilmasangiz, ushbu paragrafning qolgan qismini o'tkazib yuboring va imon bo'yicha bunday w(x) ning mavjudligini qabul qiling. Agar M grafigining G matritsasi bo'lsa (i-->j chekkasi bo'lsa, katakcha (i,j) 1, bunday chekka bo'lmasa 0), u holda men ularni tasvirlaganimdek w(x), xos vektorning elementlari hisoblanadi chap xos qiymat uchun bu matritsa d. Biz bilamizki, bunday vektor mavjud, chunki d xos qiymat: u arzimas xos vektorga ega. o'ngda(1,1,....1) - bu har bir cho'qqidan to'liq d qirralarning chiqishidan darhol kelib chiqadi.

Agar A har qanday cho'qqilar to'plami bo'lsa, w(A) A dagi barcha cho'qqilarning og'irliklari yig'indisini bildiradi; va w(G) - grafikdagi barcha cho'qqilarning og'irliklari yig'indisi. Bundan tashqari, agar s har qanday so'z bo'lsa, As -1 siz s bo'ylab "teskari yo'nalishda" ketsangiz, A dan kelgan cho'qqilar to'plamini bildirsin, har bir qadamda har bir cho'qqi o'sha cho'qqilar bilan almashtiriladi (agar mavjud bo'lsa) bu unga mos rangda boradi.

Keling, bir nuqtaga birlashtirilishi mumkin bo'lgan barcha cho'qqilar to'plamini ko'rib chiqaylik, ya'ni. Shunday qilib, ba'zi w uchun Aw faqat bitta cho'qqini o'z ichiga oladi. Ularning ichida maksimal og'irligi w(A) bo'lgan A to'plamlari maksimal to'plamlar deyiladi. Agar rang berish sinxronlashayotgan bo'lsa, u holda butun G grafigi maksimal to'plamdir (noyob), lekin aks holda bunday emas.

Agar A har qanday cho'qqilar to'plami bo'lsa, u holda a barcha d rang bo'ylab o'tadigan barcha w (Aa -1) yig'indisi d * w (A) ga teng - bu faqat bittadan asosiy og'irlik xususiyatining umumlashtirilishi. A cho'qqilar to'plamiga cho'qqi. Agar bundan tashqari, A maksimal to'plam bo'lsa, w(Aa -1) ning har biri w(A) dan katta bo'lishi mumkin emas, chunki bu to'plamlar ham bir cho'qqiga yaqinlashadi. Va bu og'irliklarning d yig'indisi d*w(A) ga teng bo'lgani uchun ularning har biri w(A) ga teng va bu to'plamlarning hammasi ham maksimaldir. Bu darhol shuni anglatadiki, agar A maksimal bo'lsa, u holda Aw -1 har qanday w so'zi uchun ham maksimaldir.

Maksimal to'plamlar foydalidir, chunki ularning ajratilgan misollari butun grafikni qamrab olishi mumkin. Keling, buni isbotlaylik.

Juft bo‘lib kesishmaydigan va bir xil w so‘zi bo‘yicha a 1 ...a n gacha bo‘lgan maksimal A 1 ...A n to‘plamga ega bo‘lsin (dastlabki holatda n=1 bo‘ladi va faqat bitta to'plam, shuning uchun boshlash oson). Barcha a 1 ...a n bir-biridan farq qilishi aniq, chunki aks holda maksimal to'plamni bir xil yakuniy cho'qqiga ega bo'lgan boshqasining elementlari orqali yanada kengaytirish mumkin edi. Faraz qilaylik, barcha A i birgalikda G ning barcha uchlarini hali tugatmagan va x barcha A i dan tashqaridagi cho‘qqi bo‘lsin. Grafik ulanganligi sababli, 1 dan x gacha bo'lgan ba'zi bir marshrut h mavjud. Keyin n maksimal to'plam A i h -1 w -1 whw so'zi bo'yicha oxirgi a 1 ...a n cho'qqilariga boradi va maksimal A 1 to'plam qandaydir cho'qqiga chiqadi Awhw = (Aw)hw = (a 1 h)w = xw. Bu cho'qqi xw ham barcha a 1 ...a n dan farq qilishi kerak, chunki aks holda maksimal A i to'plamini x elementi bilan to'ldirish mumkin edi. Va bu n + 1 to'plamlarning barchasi - barchasi A i h -1 w -1 va A 1 - whw bo'ylab turli cho'qqilarga o'tganligi sababli, ularning barchasi juft bo'lib ajratilgan. Ushbu kengayishni to'plamdan tashqarida hech qanday cho'qqilar bo'lmaguncha davom ettiramiz.

Shunday qilib, biz butun G grafigini ajratilgan maksimal to'plamlar bilan qoplashimiz mumkin. Ular maksimal bo'lganligi sababli, ularning barchasi bir xil umumiy w max ga ega va shuning uchun ularning qoplamadagi soni N max = w(G)/w max.

Endi juft-juft dushmanlardan tashkil topgan har qanday A to'plamini ko'rib chiqing. Misol uchun, klik bunday to'plamga misol bo'ladi (shuningdek, Gw shakliga ega). Maksimal to'plam ichida bir juft dushman bo'lishi mumkin emas, chunki u birlasha olmadi. Demak, N max maksimal to'plamlar qoplamasida har birida ko'pi bilan bitta A a'zosi mavjud, shuning uchun A ning o'lchami ko'pi bilan N max bo'ladi. Xususan, bu har qanday klik hajmining yuqori chegarasi.

A Gw ko'rinishdagi klika bo'lsin, bu erda w qandaydir so'z. Keyin G = Aw -1 , va shunga ko'ra w(G) w(aw -1) yig'indisiga teng bo'ladi, bu erda a A ning barcha uchlari bo'ylab o'tadi. Oldingi paragrafga ko'ra atamalar soni ko'pi bilan N max. , va har bir aw -1 to'plamini bir nuqtaga (w so'zi bilan a nuqtaga) kamaytirish mumkin, shuning uchun uning og'irligi maksimal w max dan katta emas. Butun yig'indi w(G) = N max *w max bo'lganligi sababli, atamalar soni aniq N max va har bir a'zo aynan w max degan xulosaga kelamiz. Biz barcha bosishlar bir xil o'lchamga ega ekanligini isbotladik: aynan N maksimal element.

Ikkita A va B kliklari bo'lsin, shunda A ichida barcha elementlar B bilan umumiy bo'lsin, bittadan tashqari: |A| - |A∩B| = 1.

A va B bir xil o'lchamga ega bo'lgani uchun bizda ham |B| mavjud - |A∩B| = 1, ya'ni. A va B ning barcha elementlari umumiy bo‘lib, A da bitta p cho‘qqi va B cho‘qqisi q cho‘qqisidan tashqari. Biz bu p,q cho‘qqilarning barqaror do‘st ekanligini isbotlamoqchimiz. Agar bunday bo'lmasa, unda qandaydir so'z w ularni dushman qiladi, ya'ni. pw va qw dushmandir. Yuqorida ko'rsatilganidek, Aw va Bw ham to'siqlardir va yana ular pw va qw dushmanlaridan tashqari barcha umumiy elementlarga ega ekanligi aniq. Keyin Aw ∪ Bw to'plami juft dushmanlar to'plamidir. Darhaqiqat, unda Aw ning barcha elementlari juftlik dushmanlaridir, chunki u klikdir; Bw elementlariga ham xuddi shunday; va faqat bir juft pw, qw qoldi - dushmanlar ham. Ammo bu to'plamda N max +1 element mavjud va yuqorida biz har qanday juftlik dushmanlari to'plami N dan ortiq elementga ega bo'lmasligini ko'rsatdik. Bu qarama-qarshilik va shuning uchun pw va qw hech qanday w uchun dushman bo'la olmaydi. Boshqacha qilib aytganda, p va q barqaror do'stlardir.

Kengaytirilgan grafiklar va kliklar

Berilgan G grafigining barcha cho‘qqilarini olamiz va har bir cho‘qqidan faqat bitta chiquvchi chetni tanlaymiz. Bunday tanlov subgrafni belgilaydi, biz uni chaqiramiz tarqaladigan grafik(ko'lamli grafik). Turli xil diapazonli grafikalar juda ko'p bo'lishi mumkin, ammo ularning qanday ko'rinishi haqida bir oz o'ylab ko'raylik. R ni o'z ichiga oluvchi grafigi bo'lsin. Agar biz uning har qanday x cho'qqisini olib, uning chekkalarini kuzatishni boshlasak, har safar bizda yagona tanlov qoladi, chunki Rda har bir cho'qqidan faqat bitta chekka chiqadi va ertami-kechmi yopiq tsikl. Balki bu sikl x da yopilmasligi mumkin, lekin biror joyda "keyingi" yopiladi - masalan, x-->y-->z-->s-->y. Keyin x dan bu tsiklga "dum" olib keladi. Agar biz boshqa cho'qqidan boshlasak, biz ham, albatta, tsiklga kelamiz - bu yoki boshqa. Ma'lum bo'lishicha, R ning har qanday cho'qqisi tsiklda yotadi (ulardan bir nechtasi bo'lishi mumkin) yoki tsiklga olib keladigan "dum" ning bir qismidir. Bu shuni anglatadiki, R quyidagicha ko'rinadi: ma'lum miqdordagi tsikllar va ularning ustiga ma'lum miqdordagi "teskari" daraxtlar qurilgan: har bir daraxt boshlanmaydi, lekin tsikllardan birida yotadigan "ildiz" bilan tugaydi.

Grafikning har bir tepasiga biz belgilashimiz mumkin Daraja, berilgan diapazonli grafigda uning sikldan masofasiga mos keladi R. Tsiklda yotuvchi cho’qqilar 0 darajaga ega, siklga biriktirilgan daraxt ustida joylashgan cho’qqilar esa o’z daraxtidagi “ildiz”gacha bo’lgan masofaga teng darajani oladi. "tsiklda yotish. Grafikimizning ba'zi uchlari maksimal darajaga ega L. Ehtimol, u odatda 0 ga teng - ya'ni. daraxtlar yo'q, faqat tsikllar bor. Ehtimol, u noldan kattaroqdir va bu maksimal darajaning cho'qqilari turli davrlarga yoki biriga bog'langan turli xil daraxtlarning barcha turlarida yotadi.

Biz R diapazonini shunday tanlamoqchimiz maksimal darajadagi barcha uchlari bir daraxtda yotadi. Intuitiv ravishda buni amalga oshirish mumkinligiga ishonish mumkin, chunki agar bunday bo'lmasa - masalan, ular turli xil daraxtlar bo'ylab tarqalib ketgan bo'lsa - u holda bunday maksimal cho'qqilardan birini tanlash mumkin x va R ga bir chetini biriktirib, uning darajasini oshirish mumkin. x ga. Keyin boshqa bir chekka tashqariga tashlanishi kerak bo'ladi va u boshqa narsaga zarar keltirmasligi aniq emas ... lekin bu texnik muammo, bu haqda keyinroq. Men shunchaki aytishga harakat qilyapmanki, bu intuitiv jihatdan juda murakkab ko'rinmaydi.

Aytaylik, biz R ni tanlashimiz mumkin, shunda maksimal darajadagi barcha uchlari bitta daraxtda yotadi. Bu daraxt noaniq deb hisoblanadi, ya'ni. maksimal daraja L > 0. Ushbu taxminga asoslanib, biz oldingi bo'limning shartini qondiradigan A va B kliklari bilan bo'yashni quramiz va bu bu rangning barqaror juft do'stlari borligini isbotlaydi.

Bo'yash quyidagicha bo'ladi: biz a rangini tanlaymiz va biz R grafigining barcha qirralarini shu rangda, G grafigidagi qolgan barcha qirralarni - har qanday tarzda boshqa ranglarda (agar bitta bo'lsa) rang beramiz. rang, keyin R G bilan mos keladi, shuning uchun muammo yo'q). Shunday qilib, a rangidan iborat so'zlar o'z daraxtlari bo'ylab R cho'qqilarini tsikllar tomon "oldinga" olib boradi va keyin ularni tsikllar bo'ylab harakatlantiradi. Bizga faqat shunday so'zlar kerak.

R da x maksimal darajali L ning istalgan cho'qqisi, K esa x o'z ichiga olgan har qanday klik bo'lsin; bilamizki, bunday guruh bor. K maksimal darajadagi L ning boshqa cho'qqilarini o'z ichiga oladimi? Bizning taxminimizga ko'ra, bunday cho'qqilarning barchasi x bilan bir daraxtda, ya'ni a L so'zi ularni x bilan bir joyga - ya'ni tsiklda yotgan bu daraxtning ildiziga olib boradi. Demak, bunday cho'qqilarning barchasi x ning do'stlaridir va shuning uchun u bilan bir xil guruhda yotolmaydi. Shuning uchun, x dan tashqari, K faqat pastki darajadagi cho'qqilarni o'z ichiga olishi mumkin.

Keling, A = Ka L-1 to'plamini ko'rib chiqaylik. Bu ham klik bo'lib, unda x dan tashqari barcha cho'qqilar R da o'zlarining ba'zi davrlariga yetib borganlar, chunki A ning x dan tashqari barcha uchlari L dan past darajaga ega. Faqat x hali ham sikldan tashqarida, tsikl bo'yicha uning ildiziga to'liq 1 masofada. Keling, R dagi barcha tsikl uzunliklarining ko'paytmasi bo'lgan m raqamini olaylik - masalan, barcha tsikl uzunliklarining ko'paytmasi. m shunday xususiyatga egaki, agar y cho'qqi Rda siklda bo'lsa, u holda a m so'zi uni o'z joyiga qaytaradi: ya m = y. B = Aa m klikiga qaraylik. A ning barcha uchlari, x dan tashqari, tsikllarda yotadi va shuning uchun B da u erda qoldi; va faqat x nihoyat o'z tsikliga kirdi va u erda biror joyga joylashdi. Bu shuni anglatadiki, A va B kesishmasi A ning barcha uchlarini o'z ichiga oladi, bittadan tashqari: |A| - |A∩B| = 1. Ammo bu avvalgi bo'limga ko'ra, bizning rang berishimiz isbotlanishi kerak bo'lgan barqaror juftlikka ega ekanligini anglatadi.

Maksimal darajani qurish.

R diapazonini har doim shunday tanlash mumkinligini isbotlash kerakki, u notrivial maksimal daraja L > 0 ga ega bo'ladi va bu darajaning barcha cho'qqilari bir daraxtda yotadi.

Ushbu dalilning bir qismi men o'qigan va sinab ko'rgan juda zerikarli va texnik lemmadir, lekin men buni takrorlamayman, faqat qiziquvchilar uchun maqolaning qaerdaligini aytaman. Ammo men sizga bu lemmaga qanday borishni aytaman.

Bizga G grafigiga qo'yishimiz mumkin bo'lgan ikkita cheklov kerak bo'ladi. Birinchidan, biz G'da looplar yo'qligini aytamiz, ya'ni. bir cho'qqidan bir xil cho'qqigacha bo'lgan qirralar. Gap shundaki, agar grafikda halqa mavjud bo'lsa, unda sinxronlashtiruvchi rangni boshqa yo'l bilan topish juda oson. Keling, bu halqani qandaydir a rangga bo'yaymiz, so'ngra bu cho'qqidan qarama-qarshi yo'nalishda "o'qlarga qarshi" o'tib, a rangi har doim shu cho'qqiga olib borishi uchun qirralarni ranglaymiz. Grafik ulanganligi sababli, buni tartibga solish oson va keyin tsikl a ning qandaydir quvvati butun grafikni ushbu cho'qqiga olib kelishini ta'minlaydi.

Keyin, bir lahzaga faraz qilaylik, qandaydir p cho'qqidan barcha d qirralar bir xil q cho'qqisiga olib boradi. Bunga shartlar ruxsat beradi, ammo bu holda biz bu qirralarning to'plamini chaqiramiz to'plam. Bizning ikkinchi cheklovimiz: turli p va q cho'qqilaridan ikkita zveno olib keladigan r cho'qqisi yo'q. Nega biz uni majburlashimiz mumkin? Chunki agar p va q dan r gacha bo'lgan bog'lanishlar mavjud bo'lsa, u holda har qanday rang berish uchun p,q birinchi rangdan keyin r cho'qqisiga yaqinlashadi va shuning uchun ular barqaror do'stlardir. Shunday qilib, bu holda, bizga barcha diapazonli grafiklar va kliklarning qurilishi kerak emas, biz darhol barqaror do'stlarga ega bo'lamiz. Shuning uchun, biz bunday emas deb taxmin qilishimiz mumkin.

Nihoyat, har doim ham cho'qqilari tsikllarda yotmaydigan, lekin ba'zi bir ahamiyatsiz daraxtlar mavjud bo'lgan R diagrammasi mavjudligini isbotlaylik. Biz ba'zi R ni tanlaymiz va uning barcha uchlari tsikllarda yotadi deb faraz qilamiz. Agar G grafigida barcha qirralar to'plamlarda yotsa - ya'ni. har doim bitta cho'qqidan chiqadigan barcha d qirralar bir xil cho'qqiga olib keladi - keyin R ni tanlash har bir to'plamdan faqat bitta chetni tanlashni o'z ichiga oladi. Bunday holda, R da faqat bitta tsikl bo'lishi mumkin (axir, R dagi bir nechta sikllarni bog'langan G grafigida bir-biriga bog'lab bo'lmaydi - G ning barcha qirralari R ning chekkalari bilan bir xil cho'qqilarni bog'laydi, chunki bular ligamentlardir - va G ulanganligi sababli, bu mumkin emas) va G dagi har qanday tsikl oddiygina ushbu tsiklning bog'lanishlaridan boshqa qirralarni tanlaydi, lekin aslida u bir xil tsikl, bir xil uzunlikdir. Ammo bu shuni anglatadiki, G dagi barcha sikllarning uzunligi shu uzunlikka bo'linadi, bu esa G ning davriy emasligiga ziddir. Shuning uchun Gda barcha qirralar bog'ichlarda yotishi mumkin emas, ya'ni ba'zi ikkita p qirralari borligini bildiradi. R dagi -- >q va R dan tashqarida p-->s (p ning ba'zi chetlari nafaqat chiziqli grafada yotmasligini, balki boshqa s cho'qqisiga ham olib kelishini isbotlash uchun bizga bog'lovchilar haqida uzoq argument kerak edi). Keyin p-->q ni p-->s bilan almashtiramiz va bu tsiklni "buzadi", unda qandaydir ahamiyatsiz bo'lmagan quyruq hosil qiladi. Bu quyruq bizga yangi grafikda ahamiyatsiz daraxtni beradi.

Endi, ahamiyatsiz bo'lmagan daraxtlarga ega bo'lgan barcha R diagrammalaridan biz aylanishlarning maksimal soniga ega bo'lgan R ni tanlashimiz mumkin. T.e. u tsikllarda emas, balki cho'qqilarga ega, lekin bu cheklovdan tashqari, tsikllardagi cho'qqilar soni maksimallashtiriladi. Ushbu grafikda maksimal darajali L ning ba'zi bir cho'qqilari mavjud va biz ularni turli xil ildizlarga olib boradigan daraxtlarda deb taxmin qilishimiz mumkin, aks holda biz allaqachon kerakli narsaga erishdik. Biz x cho'qqisini tanlaymiz. Biz grafikni shunday o'zgartirmoqchimizki, bu cho'qqi L dan uzunroq daraxtdagi uzunroq marshrutning bir qismiga aylanadi va qolgan daraxtlar o'zgarmaydi, keyin esa maksimal daraja faqat bitta daraxtda bo'ladi, biz nima qilamiz. istayman. Grafikni uchta usulda o'zgartirishingiz mumkin:

a) y-->x qirrasini oling va uni R ga qo'shing va u erda mavjud bo'lgan y-->z chetini tashlang;
b) b-->r chekkasini oling, bu x dan o'z tsikliga (sikldagi r) yo'lda oxirgi bo'lib, uni tashlang va boshqa b-->z ni qo'shing.
c) siklning bir qismi bo'lgan c-->r chetini oling va uni tashlang va boshqa c-->z qo'shing.

Trachtman maqolasining 7-Lemmasi bu o'zgarishlarning biri (yoki ba'zi hollarda ikkitasi) kerakli natijaga olib kelishini batafsil isbotlaydi. Jarayon R ning maksimalligidan (agar ba'zi o'zgarishlar R ga qaraganda tsikllarda ko'proq cho'qqilar soniga ega bo'lgan grafikga olib kelsa, bu uning maksimalligiga zid keladi) va yuqorida tavsiflangan ikkita bog'lovchi olib boradigan cho'qqi yo'qligi shartidan foydalanadi. Natijada, har qanday holatda, biz R grafigini olamiz, unda maksimal darajaning barcha cho'qqilari bitta ahamiyatsiz bo'lmagan daraxtda joylashgan.

Yangilash, bir haftadan keyin: Shunday bo'lsa-da, men ushbu yozuvni to'liq o'z-o'zini ta'minlashga qaror qildim va oldingi paragrafda eslatib o'tgan lemmaning isbotini qayta aytib berdim. Buni diagramma bilan qilish yaxshiroq bo'lar edi, lekin men uni chizish yoki maqoladan yirtib tashlashni xohlamayman, shuning uchun men so'z bilan harakat qilaman. Shunday qilib, tasavvur qilaylik, bizda arzimas daraxtlarga ega bo'lgan R diapazonli grafigi bor va undagi barcha bunday grafiklardan eng ko'p cho'qqilar soni tsikllarda yotadi. Biz R ni maksimal darajadagi barcha uchlari bir daraxtda yotadigan kengayuvchi grafikga aylantirmoqchimiz; Sinab ko'rish jarayonida biz bunday grafikni olishimiz bilanoq, biz darhol tugatamiz (va biz tsikllardagi cho'qqilar soni bo'yicha maksimal grafik yo'qolishi mumkinligiga ahamiyat bermaymiz, bu biz uchun muhim emas, biz undan faqat jarayonda foydalanamiz). X maksimal darajali L cho‘qqisi, T u yotgan daraxt, r C siklining T tugaydigan cho‘qqisi, b-->r dan oldingi r dan oldingi oxirgi cheti x dan C siklgacha bo‘lgan yo‘l bo‘lsin. Taxmin qilishimiz mumkinki, bu tsiklga hali ham ba'zi daraxtlar qo'shiladi yoki L darajasidagi cho'qqilarga ega bo'lgan boshqalar mavjud - aks holda hamma narsa allaqachon bajarilgan. Bundan kelib chiqadiki, agar biz T dan L dan kattaroq elementga ega bo'lgan daraxtni olsak va boshqa daraxtlarni uzaytirmasak, unda ish tugadi.

Birinchidan, yuqoridagi a) operatsiyasini bajarishga harakat qilaylik: G ning y-->x chetini oling - u mavjud, chunki grafik bog'langan va ko'chadan holda, va R da yotmaydi, chunki x maksimal daraja. Keling, uni R ga qo'shamiz va ilgari u erda bo'lgan y-->z ni chiqarib tashlaymiz. Agar y T daraxtida bo'lsa, u holda y-->x yangi tsiklni yopadi va yangi grafikda ko'proq cho'qqilar tsikllarda yotadi va hali ham ahamiyatsiz bo'lmagan daraxtlar mavjud (hech bo'lmaganda R da bo'lgan boshqalar), bu R ning maksimalligiga ziddir. Agar y T da yotmasa va y-->z C siklining bir qismi bo‘lmasa, y-->z ni o‘chirish bu siklni buzmaydi, y-->x ni qo‘shish esa uzaytiriladi. daraxtning T ning maksimal darajasi kamida bittaga, qolgan daraxtlar esa cho'zilmaydi, shuning uchun biz tugatdik. Qolgan variant y-->z C siklida yotsa, u endi buzilgan va yangi sikl hosil bo'lganida: r dan y gacha, keyin y-->x, so'ngra oldingi daraxt bo'ylab x dan r gacha. Bu siklning uzunligi l(ry)+1+L, eski C sikl uzunligi esa l(ry)+1+l(zr) ga teng edi. Yangi tsikl eskisidan uzoqroq bo'lishi mumkin emas, bu R ning maksimalligiga zid keladi, shuning uchun biz L ≤ l (zr), ya'ni ekanligini ko'ramiz. eski pastadirda z dan r gacha bo'lgan marshrut uzunligi. Boshqa tomondan, yangi grafikda z cho'qqisi endi kamida l(zr) darajasiga ega va agar bu L dan katta bo'lsa, biz bajaramiz. Shunday qilib, biz l(zr)=L deb taxmin qilishimiz mumkin. Xulosa qilib aytadigan bo'lsak: a) ishlamayapti deb faraz qilamiz va keyin y-->z C, l(zr) = L siklda yotishini bilamiz.

Endi b operatsiyasini sinab ko'ramiz: b-->r chetini boshqa b-->d chetiga almashtiring. Keling, yangi d cho'qqisi qayerda yotganini ko'rib chiqaylik. Agar T daraxtida bo'lsa, biz oldingisini buzmasdan yangi tsikl yaratdik va R ning maksimalligini rad etdik. Agar boshqa daraxtda bo'lsa, u holda T ning maksimal cho'qqilari, shu jumladan x, endi L dan kattaroq darajaga ega bo'ladi. Boshqa daraxtlar bo'lmaydi va biz tugatdik. Agar C emas, balki boshqa sikl bo'lsa, biz endi a) bilan birga b) ham a) bajaramiz: y-->z C da yotishini bilganimiz uchun, bu operatsiya C ni buzadi, lekin yangi sikl emas. u endi bog'langan daraxt P, va bu daraxt endi L dan kattaroq darajadagi cho'qqilarga ega bo'ladi va biz yana tugatdik.

Qolgan variant b-->d C sikliga ham ulangan bo'lsa, r dan boshqa joyda yoki o'sha joyda va keyin d=r. Biz b-->r ni b-->d bilan almashtirganimizdan so'ng, biz avvalgidek vaziyatga ega bo'ldik - T daraxti, L darajasidagi x tugun va boshqalar. - endi aylanaga faqat daraxt d cho'qqisi orqali bog'langan. Endi a amalini ko'rib chiqsak, (u ishlamasa) l(zd) = L degan xulosaga kelamiz, xuddi avvalroq l(zr) = L degan xulosaga kelganimizdek. Ammo l(zd)=l(zr) bo'lsa, ya'ni. z dan sikl bo'ylab masofa d va r gacha bir xil bo'lsa, u holda bu bir xil cho'qqi: d=r. Demak, agar b) ishlamasa, b dan istalgan chekka r ga olib kelishi kerak, ya'ni. b dan qirralari to'plam hosil qiladi.

Nihoyat, C siklida yotgan c-->r chetini ko'rib chiqing. Biz b ning barcha qirralari r ga olib boruvchi zvenoda yotadi deb taxmin qilishimiz mumkin bo'lganligi sababli, biz yuqorida aytib o'tilgan ikkita bog'lanish bo'lishi mumkin bo'lmagan cheklovni ham qo'yishimiz mumkin. bitta cho'qqi, c dan r ga hamma qirralar emas, lekin u erda bir qancha chekka c-->e bor. c-->r ni c-->e bilan almashtiramiz. E cho'qqisi qayerda yotishi mumkin? T daraxtida emas, chunki bu R ning maksimalligiga zid bo'lgan C tsiklini "uzaytiradi". Shunday qilib, e boshqa daraxtda yoki boshqa tsiklda yoki hatto bir xil C tsiklida yotadi, lekin r tepasida emas. . Keyin T daraxti, tsiklga ulanishdan oldin, endi r dan chiqadigan kamida bitta chekka bilan uzaytiriladi va ehtimol undan ko'p (faqat bittasi e r dan keyin darhol yotsa va c--> e C tsiklini yana yopadi, undan faqat r hosil qiladi). Bu shuni anglatadiki, x cho'qqisi va boshqa maksimal cho'qqilar T darajasi hozirda kamida L + 1, va boshqa daraxtlar cho'zilmagan va yana bizda kerakli narsa bor.