|
Graflarni bo'yash. Graf xromatik sinfi va xromatik soni. Bixromatik graflar
|
| bet | 5/7 | | Sana | 09.01.2024 | | Hajmi | 0,74 Mb. | | #132798 |
Bog'liq DISKRET 5 M Institut daftar yuzi, 11, Документ Microsoft Word 123456, BILISH NAZARIYASI, 043-22 (3), «Parametrli teńlemelerdi sheshiwde ornına qoyıw hám jiklew (dizy-hozir.org, Maruza topshiriq, 1-Laboratoriya ishi. Mavzu Electronics Workbench dasturi imkoni, 4740, 23874, deadline, islom m baza 1 amaliy artel, Аннотация Муштари 3, 1ish Demak, G grafning qirralaridan tashkil etilgan qandaydir C2 sikl bor. Bu siklni uning ixtiyoriy v, uchidan boshlab quramiz.Dastlab v, uchga insident bo'lgan ixtiyoriy bir qirrani tanlab, bu qirra bo'ylab harakatlanamiz va uning boshqa uchiga o'tamiz. Har safar, imkoniyati boricha, yangi qirra tanlab va bu qirradan o'tib, uning boshqa uchiga boramiz. Shuni ta'kidlash zarurki, bunday o'tishlar jarayonida faqat qirraning yangisini tanlashga harakat qilinadi, uchlar esa istalganchatakrorlanishimumkin. Demak, G grafning qirralaridan tashkil etilgan qandaydir C2 sikl bor. Bu siklni uning ixtiyoriy v, uchidan boshlab quramiz.Dastlab v, uchga insident bo'lgan ixtiyoriy bir qirrani tanlab, bu qirra bo'ylab harakatlanamiz va uning boshqa uchiga o'tamiz. Har safar, imkoniyati boricha, yangi qirra tanlab va bu qirradan o'tib, uning boshqa uchiga boramiz. Shuni ta'kidlash zarurki, bunday o'tishlar jarayonida faqat qirraning yangisini tanlashga harakat qilinadi, uchlar esa istalganchatakrorlanishimumkin. Har bir uchga insident qirralar soni juft bo'lgani uchun Cxsiklni qurish jarayoni faqat vxuchga borgandagina tugaydi. Bu yerda ikki hosil bo'lishi mumkin: Cxsikl G grafning barcha qirralaridan o'tadi yoki Cxsikl G grafnir.p barcha qirralaridan o'tmaydi. Birinchi holda teorema isbotlandi deyish mumkin. Ikkinchi holda G grafdan Cxsiklga tegishli barcha qirralarni olib tashlaymiz vanatijada hosil bo'lgan grafni Cxdeb belgilaymiz. Bu yerda yakkalanib qolgan uchlarni olib tashlash yoki olib tashlamaslik muhim emas. Har bir uchga insident qirralar soni juft bo'lgani uchun Cxsiklni qurish jarayoni faqat vxuchga borgandagina tugaydi. Bu yerda ikki hosil bo'lishi mumkin: Cxsikl G grafning barcha qirralaridan o'tadi yoki Cxsikl G grafnir.p barcha qirralaridan o'tmaydi. Birinchi holda teorema isbotlandi deyish mumkin. Ikkinchi holda G grafdan Cxsiklga tegishli barcha qirralarni olib tashlaymiz vanatijada hosil bo'lgan grafni Cxdeb belgilaymiz. Bu yerda yakkalanib qolgan uchlarni olib tashlash yoki olib tashlamaslik muhim emas.
|
| |
