Graflarni bo'yash. Graf xromatik sinfi va xromatik soni. Bixromatik graflar

G grafning bog'lamliligiga ko'ra, Cxsikl va Gxgraf hech bo'lmasa, bitta umumiy uchga ega bo'lishlari kerak. Shu sababli, C, siklda Gxgrafning qirralariga ham insident bo'lgan qandaydir v2 uch bor. Bu v uchdan boshlab faqat Gxgrafning qirralaridan tashkil topgan yangi Сsiklni qurish mumkin.Сsiklni qurish jarayoni faqat v2 uchga kelib tugashi mumkin. Oldin qurilgan Cxsiklni ikki qismga ajratamiz:

G grafning bog'lamliligiga ko'ra, Cxsikl va Gxgraf hech bo'lmasa, bitta umumiy uchga ega bo'lishlari kerak. Shu sababli, C, siklda Gxgrafning qirralariga ham insident bo'lgan qandaydir v2 uch bor. Bu v uchdan boshlab faqat Gxgrafning qirralaridan tashkil topgan yangi Сsiklni qurish mumkin.Сsiklni qurish jarayoni faqat v2 uchga kelib tugashi mumkin. Oldin qurilgan Cxsiklni ikki qismga ajratamiz:

Cj siklning Vj uchidan boshlanib v2 uchida tugovchi qismi (bu oddiy zanjirni C,(Vj,v2) bilan belgilaymiz) va Cj siklning v2 uchidan boshlanib, v} uchida tugovchi qolgan qismi (CfavJ). Agar C2 sikl Eyler sikli bo'lsa, teoremaning tasdig'i isbotlandi desa bo'ladi.Aks holda yuqorida bayon etilgan jarayonni takrorlaymiz. Berilgan G grafdagi qirralar soni chekli bo'lganligidan, bu jarayon chekli jarayondir.Bu jarayonni yetarlicha takrorlagandan so'ng, albatta, u Eyler siklini qurish bilan yakunlanadi.

Cj siklning Vj uchidan boshlanib v2 uchida tugovchi qismi (bu oddiy zanjirni C,(Vj,v2) bilan belgilaymiz) va Cj siklning v2 uchidan boshlanib, v} uchida tugovchi qolgan qismi (CfavJ). Agar C2 sikl Eyler sikli bo'lsa, teoremaning tasdig'i isbotlandi desa bo'ladi.Aks holda yuqorida bayon etilgan jarayonni takrorlaymiz. Berilgan G grafdagi qirralar soni chekli bo'lganligidan, bu jarayon chekli jarayondir.Bu jarayonni yetarlicha takrorlagandan so'ng, albatta, u Eyler siklini qurish bilan yakunlanadi.

Xulosa Xulosa qilibaytganda Graflar nazariyasi xozirgi zamon matematikasining asosiy qismlaridan biridir. turli paytlarda turli xil ABT va diskret xususiyatlariga ega bo'lgan xisoblash jihozini loyixalashda (yasashda) graflarning axamiyati oshamiyati yanada kengaytirildi. Bu kurs ishini yozish davomida oʻtilgan mavzularni takrorladim va graflar haqida toʻliq umumiy tasavvurga ega boʻldim.