Дәріс №1 Кіріспе. Жиындар теориясының негізгі ұғымдары. Жиындарға амалдар қолдану
жүктеу/скачать 1,12 Mb.
|
Лекция дискретка каз
| 2.Графтарды бояу есебі
жазық графының дұрыс n-түсті боялуы деп :V(G){1,2,...,n} бейнесі аталады және егер оның шекарасы v1 мен v2 болатындай r R(G)қабырғасы бар болса, (v1)(v2 ) өрнегі орындалады. Сонымен, төрт бояу проблемасын келесі тұжырым түрінде қорытындылаймыз. 1-теорема. Кез келген жазық граф дұрыс 4 түсті бояуды ұйғарады. Осы проблеманы шешу мәселесіне жүз жылдан астам уақыт жұмсалды. Бірақ бір қарағанда әлсіз болып көрінетін дұрыс 5 түсті бояу туралы тұжырым оңай дәлелденеді. Дәлелдеуге төбелер, қабырғалар және облыстар санын байланыстыратын Эйлер формуласы керек болады. M шектеулі жиыны элементтерінің санын білдірсін. Эйлер теоремасы. Кез келген жазық граф үшін |V(G) |+| D(G)|= 2 + |R(G)| . 2- теорема. Кез келген жазық граф 5 түсті бояуды ұйғарады. Дәлелдеуі. Алдымен графты ықшамдаймыз.Егер небір төбелер жұбынбіріктіретін бірнеше қабырғалар бар болса (бұндай жағдай екі елдің бірнеше өзара байланыспайтын шекара тілімдері бар болғанда туындайды, мысалы Ресей мен Қытай сияқты), онда тек бір қабырға қалтырамыз: осындай кішірейтілген графты дұрыс түстеп бояу, ізделінген түстеп бояудың дұрыс болуына кепілдік береді. Граф төбелері санымен индукция жүргіземіз. Үш төбесі бар граф үшін теорема тұжырымы орындалатыны айқын. Бұл тұжырым n -1 төбелі барлық графтар үшін әділ. D1,D2,...,Dm –түгел m =D(G)граф облыстарының толық жиынтығыболсын, ал N(Di ) – графтың i - інші облысының шекарасын құратын қабырғалар саны. Сонымен қатар кез келген i үшін N(D) >3. Кез келген қабырға екі облыс шекарасына енеді, сондықтан N(D1) + N(D2 ) +...+ N(Dm) = 2R(G) . N(Di ) теңсіздігінен 2R(G) = N(D1) + N(D2 ) +...+ N(Dm) 3m = 3D(G) аламыз, осыдан 2R(G) 3D(G) . Эйлер формуласынан |V (G)|-2 + |D(G) |=|R(G)|, осыдан 3| R(G)| =3|V(G)|-6+3 |D(G)| 3|V(G)|-6+2|R(G)| және |R(G)| |V (G)|-6 (1) шығарылады. Екі еселенген қабырғалар санын басқа да граф сипаттамасымен теңдестіруге болады. ... , n=V(G) граф төбелерінің толық жиынтығы болсын, ал M() – j нөмірлі төбеге жинақталатын қабырғалар саны. Бірақ әр қабырға екі төбемен шектеледі, сондықтан 2R(G) =M( ) +M()+ ... +M(). Сонымен қатар, (1) теңсіздігінен шығарылатындай, 2| R(G)| 6|V(G)|-12. Ендеше,
Соңғы теңсіздіктен бестен артық емес қабырға жинақталатын, ең болмаса, бір төбе болатыны тұжырымдалады. Шынымен, қарсы тұжырымды қабылдайық, яғни j M() болсын. Онда M( )+M()+...+M() 6n = 6|V(G)|, бұл (2)-ге қайшы болады. Төбелерді төбесіне бестен артық емес қабырға жинақталатындай етіп, қайта нөмірлейік. Егер төбесінде төрттен артық емес қабырға жинақталса, онда G \ графын қарастырамыз, ол G -дан төбесін және төбеге тірелетін қабырғалардың бәрін аластаудан алынады. G\ графы индукция болжамымен дұрыс 5 түсті бояуды ұйғарады. Ал қабырғалар төбені кіші графтың төрт төбесімен біріктіретіндіктен, - ны дұрыс түстеп бояу үшін, ең болмаса, бір түс қалады (бесеуден). Енді - ға бес қабырға жинақталсын. Бес төбеден құралған H Gграфын қарастырайық,оған - дан шығатын және біріктіретін (G-да) қабырғалар келеді. H графында міндетті түрде қабырғалармен біріктірілмейтін екі төбе табылады. Расында да керісінше болса H бесбұрышында қабырға болады (оны есептеу қиын емес). Бірақ (1)-ге сәйкес |R(H)||V(H)|-6= 3*5-6=9 сөйтіп, қайшылыққа тірелеміз. мен - H -тың өзара байланыстырылмаған төбелері болсын. Олар G\ графындада біріктірілмеген. G\ графынан өзгертілумен алынған графын қарастырайық, мен өзгерту нәтижесінде теңестірілген. Бұл жағдайда төбелерін теңестіргеннен ілмек пайда болмайтындықтан, G - жазық граф. Бірақ үшін индукция болжамы әділ болады және оған дұрыс 5 түсті бояу бар. Бұл боялған графта мен төбелерін ажыратайық. Онда дұрыс 5 түсті бояуды G\ графы да алады, және оған теңдігі әділ болады. Басқаша айтқанда, мен бірдей түспен боялған, ендеше төбесімен көршілес H графының бес төбесін түстеп бояуға төрттен артық емес түс қолданылады. Қалған түсті төбесін бояуға қолданамыз және G -дің дұрыс 5 түсті бояуын аламыз. Бір қарағанда төрт бояу проблемасы математиканың басқа тарауларымен және іс жүзіндегі есептермен аз байланысатын тұйық есеп сияқты болып көрінеді. Шындығында олай емес. Бұл проблеманың алгебра, статикалық механика және жоспарлау есептерімен байланыстыратын 20-дан астам тұжырымы бар. Бұл да математикаға тән қасиет: таза қызығушылықпен зерделенген есеп шешімі нақты және табиғаты бойынша мүлде әртүрлі болатын объектілер мен процестерді сипаттауға пайдалы болып шығады. Төрт бояу теоремасының дәлелдеуі туралы К. Аппель мен У. Хакен дәлелдеуін математикалық қауымның қабылдағанына қарамастан, осы уақытқа дейін белгілі бір күдік тудырып отыр. Математикамен үстірт таныс оқырманды айтылған сөйлем, әрине, таңдандырады, себебі математикадағы үшінші тұжырым аластатылған: немесе әділ, немесе жоқ деген принцип қайда? – деген сұрақ еріксіз туындайды. Мәселе оңай емес. Дәлелдеу авторлары былай деп жазады: «Оқырман 50 бет мәтінді және диаграмманы, 2500 диаграммасы бар 85 бетті, тағы диаграммасы бар 400 бет микрофишаларды, негізгі мәтінде жазылған 24 леммадағы мыңдаған жеке тұжырым тексерістерін зерделеуі керек. Сонымен қатар оқырман кейбір фактілерді тексеруге 1200 сағат компьютерлік уақыттың кеткенін біледі, ал егер қолмен тексерілсе одан да көп уақыт керек екендігі айтпаса да түсінікті. Мақалалар стилі мен ұзындығы бойынша адам шошырлықтай күрделі, оны біршама болса да толығырақ зерделеген математиктер өте аз». Турасын айтқанда, дәлелдеудің компьютерлік бөлігін қолмен тексеру мүмкін емес, ал дәлелдеудің дәстүрлі бөлігі өте ұзақ және күрделілігі соншалық, оны толығымен ешкім тексермеген. Сонымен, тексеруге болмайтын дәлелдеу – нонсенс. Осындай дәлелдеумен келісу, авторларға сене салумен бірдей. Бірақ бұл арада да бәрі күрделірек. Ұзақ уақыт Евклид тұжырымдамалары мен дәлелдеулері математикалық қаталдық идеалы болып келген, оларда теоремаларды аксиомалардан шығару белгілі ережелермен орындалған (айқын емес тұжырымдарды айқын тұжырымдардан алуға мүмкіндік беретін дедукция әдісі). Бұл қаталдық үлгісі қазіргі заманда да мектеп математикасы курсында қол жетпес үлгі, бірақ жаңа замандағы таза математикаға Евклид стандарттары жеткіліксіз. Евклид, жазықтықты түзу неге екі бөлікке бөлетіні туралы ойланбаған сияқты (және ол нені білдіреді), «арасында» деген түсінікті анықтамаған, бұл түсінік онсыз да айқын деп есептеген және т.б. Осындай тұжырымдардың үлкен бөлігі соңғы жүз жылдықта ғана дәлелденіп, геометрия аксиоматикасына енгізілген. Жаңа аксиома жүйесінен формалды қорытындылар көне замандағы қорытындыларға қарағанда өте ұзын орындалған. Сонымен, төрт бояу теоремасын дәлелдеу мәселесі таза математика тұрғысынан ашық болып қала береді. жүктеу/скачать 1,12 Mb. Достарыңызбен бөлісу:
|