|
|
bet | 5/8 | Sana | 04.06.2022 | Hajmi | 374,8 Kb. | | #637308 |
| Bog'liq Графлар устине амеллер
1- teorema. Eger graftag’i ha’r bir to’benin’ lokal da’rejesi ekiden kishi bolsa’ykes a, onda bul graf tsiklga iye.
Grafti’n’ baylanislig’i tu’sinigi. Eger orientirlenbegen grafta shetleri ha’m to’belerden ibarat marshrut tabilsa, bul ha’m to’beler baylanisqan dep, marshrutti’n’ o‘zi bolsa ha’m to’belerin baylanistiriwshi marshrut dep ataladi’.
Eger qanday da to’belerdi baylanistiriwshi marshrut bazi bir to’beden bir neshe ma’rte o‘tse, onda marshrutti’n’ tsiklik bo’legin alip taslap (bunda tsiklik bo’lekti’n’ ornina marshrutta tek to’be qaldiriladi) ja’ne sol to’belerdi baylanistiriwshi a’piwayi shinjir su’wretindegi marshrutti payda etiwi mu’mkin. Sonin’ to’bein, marshrut penen baylanisqan to’beler ha’mme waqi’tta apiwayi shinjir menen de baylanisqan boladi’ degen juwmaqqa kelemiz.
Bir-biri menen u’stpe-u’st tu’speytug’in qa’legen eki to’beleri baylanisqan graf baylani’sli’ graf dep ataladi’.
Eger grafdag’i eki to’beni bazi bir a’piwayi shinjir menen tutastiriw mu’mkin bolsa, onda bul eki to’be ekvivalent (baylanisqan) delinedi. Bunday to’beler ko’pligi grafta ekvivalentlik qantasi menen aniqlang’an dep esaplanadi. To’beler ko’pligi boyinsha ekvivalentlik qatnasin esapqa alg’an halda berilgen grafti’ baylanisliliqkomponentalari (qisqasha, komponentalari) dep ataliwshi baylani’sli’ boleklerinin’ birikpesi dep qaraw mu’mkin. Bul jerda berilgen graf baylanisliliq komponentalari’na boleklenedi (ajratildi) dep aytiw mu’mkin. Da’lilleniwilew mu’mkin, ha’r qanday graf o‘zinin’ baylanisliliq komponentalari’nin’ dizyunktiv birikpesi sipatinda an’latiliw mu’mkin, bunda grafti’n’ baylanisliliq komponentalari’na bolekleniw bir ma’nisli aniqlanadi.
Keyingi mag’li’wmatlardi’ bayan etiw to’besin jag’i tu’singi za’ru’r boladi’. Tegislikte geometrik an’latiliw grafin qaraymiz. Bul grafqa tiyisli bolmag’an (yag’niy grafti’n’ hesh qaysi to’besi menen u’stpe-u’st tu’speytug’in ha’m onin’ hesh qaysi qabi’rg’ainda jatpaytug’in ) bazi bir noqatti hesh qaysi noqati grafqa tiyisli bolmag’an u’zliksiz siziq penen tutastiriw mumkin bolg’an barli’q noqatlar ko’pligi grafti’n’ nuqtati o‘zinde saqlawshi jag’i dep ataladi’.
Jag’i tu’sinigine berilgen Ani’qlamag’a muwapi’q jaq garfti’n’ geometrik an’lati’li’wi’ ja’rdeminde tegislikti’n’ “qabi’rg’aqip” alinatug’in bo’leginen ibarat . Tekislikte geometric an’latiliw qa’legen grafti’n’ hesh bolmag’anda bir jag’i boli’wi’ da onin’ bir jag’I shegarag’a iye emesligi (sheksizligi) o’z-o’zinen belgili.
Do'stlaringiz bilan baham: |
|
|