Muhammad al-xorazmiy nomidagi Toshkent axborot texnologiyalri universiteti 2-kurs talabasi bo’riyev husanning diskrit tuzilmalar fanidan yozgan Mustaqil ishi Bajardi: Bo’riyev husan Tekshirdi: Begimov o’ktam

Isboti. Avval qirralar soni n bo‘yicha matematik induksiya usulini qo‘llab, m—k < n tengsizlikni isbotlaymiz. Agar grafda qirralar bo‘lmasa (ya’ni matematik induksiya usulining bazasi sifatida n=0 deb olinsa), u holda grafdagi uchlar soni uning bog‘- lamlilik komponentalari soniga tengdir: k=m. Demak, n=0 bolganda, m—k< n munosabat to‘g‘ridir. Induksion о ‘tish. Grafdagi qirralar sonini nQ bilan belgilab, bu son minimal bolsin, ya’ni grafdan istalgan qirrani olib tashlash amali boglamlilik komponentalari soni o‘zgargan graf hosil qilsin, deb faraz qilamiz. Bundan tashqari, matematik induksiya usuli talabiga binoan n=n0 uchun isbotlanishi kerak bolgan tengsizlik o‘rinli bolsin, deb faraz qilamiz. Tabiiyki, bu holda grafdan istalgan qirrani olib tashlasak (bunda olib tashlangan qirraning chetlaridagi uchlar grafga tegishli bo lib qolaveradi), hosil bolgan grafning uchlari soni m ga, qirralari soni (n—1 )ga, bog‘lamlilik komponentalari soni esa (k+1 )ga teng boladi. Induksiya faraziga binoan m—(k+1)< n—1 tengsizlik o‘rinlidir. Bu tengsizlikdan m—k< n tengsizlik isbotlandi.

Tabiiyki, boglamli grafdan qirrani yoki bir necha qirralami olib tashlash natijasida hosil bolgan graf boglamli bolishi ham, bolmasligi ham mumkin. Agar boglamli grafdan qirrani olib tashlash amali grafning boglamlilik xususiyatini buzsa, u holda bunday qirrani ajratuvchi qirra, deb ataymiz. Ravshanki, berilgan boglamli grafda ajratuvchi qirralar ko‘p bolishlari mumkin. Ajratuvchi qirralar to‘plamining hech qaysi qism to‘plami elementlari ajratuvchi qirralar bolmasa, bu qirralar to‘plamini kesim deb ataymiz. Grafdan kesimga tegishli qirralar olib tashlansa, natijada ikki boglamli komponentalari bolgan graf hosil bolishi ravshandir. Agar kesim yagona qirradan iborat bo Isa, u holda bu qirra ко ‘prik, deb ataladi 8-teorema (D. Kyonig). Grafning ikki bo‘lakli bolishi uchun uning tarkibida uzunligi toq son bilan ifodalanuvchi sikl bo ‘Imasligi zarur va yetarlidir. Isboti o‘quvchiga havola qilinadi. ■ Berilgan G—( V, U) grafning ikki bolakliligini aniqlashning sodda usuli bor. Bu usul ko‘ndalangiga izlash, deb ataluvchi soddagina izlash g‘oyasiga asoslangan.