АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Мысал..

Анықтама. ТДЖ-ны ену бойынша минимал деп аталады, егер ол осы жиыннан кез келген төбені алып тастағанда доминантты болмаса

Мысал.

Анықтама. Төбелер саны ең кіші болатын ТДЖ-нын қуаты бойынша ең кіші деп атайды.

Мысал.

Анықтама. ТДЖ-ның ең кіші санын графтың доминанттының саны деп атайды және деп белгілейді.

Мысал.

Теорема. .

Ескерту. Бұл теорема § 8- ғы теореманың

Ядро

Анықтама. графтың төбелер жиынының ішкі жиыны ядро деп аталады, егер ол бір мезгілде тәуелсіз және доминантты жиын болса.

Мысал.

Теорема. ТТЖ-ны ТДЖ болады сонда тек сонда,егер ол ТТЖ-ң ену бойынша максималы болса.

Дәлелдеуі.

1. - ТТЖ-ны және ТДЖ-ны болсын. -ның ТТЖ-нңы ену бойынша максимал екенін дәлелдейік.

Егер – ТДЖ-ны болса, онда анықтама бойынша -ға тиісті емес графтың кез келген төбесі -ның кем дегенде бір төбесімен сыбайлас болса. Сондықтан -ның ТТЖ-нын кеңейтуге болмайды.Бұдан, - ТТЖ-ң ену бойынша максималы болады.

2. Пусть - ТТЖ-ң ену бойынша максималы болсын. - ТДЖ болатынын дәлелдейік.Егер - ТТЖ-ң ену бойынша максималы болса, онда анықтама бойынша оны кеңейтуге болмайды.Яғни, -ға тиісті емес графтың кез келген төбесі -ның кем дегенде бір төбесімен сыбайлас болады.Бұдан - ТДЖ болады. Дәлелденді.

ДС 9. Қабырғалардың тәуелсіз жиыны. Графтың қабырғалық бүркеуі.

Қабырғалардың тәуелсіздік жиыны

Ескерту. «Қабырғалардың тәуелсіз жиыны (ҚТЖ)» түсіну- «ҚТЖ» ұғым аналогы.

Анықтама. графтың қабырғалар жиынының ішкі жиыны қабырғалардың тәуелсіздікжиыны (ҚТЖ) деп аталады, егер жиынының кез келген екі қабырғасының ортақ төбесі болмаса.

Ескерту. ҚТЖ үйлестірім деп те аталады.

Мысал.

- қабырғалардың жиыны

Анықтама. ҚТЖ ену бойынша максимал деп аталады, егерде ол ешқандай басқа ҚТЖ – ның ішкі жиыны болмаса, яғни оны «кеңейтуге» болмаса.

Мысал.

Анықтама. Қабырғалар саны ең үлкен болатынҚТЖ, қуаты бойынша ең үлкен ҚТЖ аталады.

Мысал.

Анықтама. ҚТЖ-ның ең үлкен қабырғалар саны қабырғалардың тәуелсіздік саны деп аталып, графының белгіленуі болады.

Мысал.

Қабырғалардың бүркейтін жиыны

Анықтама. графтың қабырғалар жиынның сызықпен ішкі жиыны, қабырғаларды бүркейтін жиыны болады (ҚБЖ), егер осы жиынның кем дегенде бір қабырғасына графтың кез келген төбесі инцидентті болса.

Анықтама. ҚБЖ ені бойынша минимал деп аталады, егер осы жиынның кез келген қабырғасын алып тастағанда ол бүркейтін жиын болмаса.

Мысал.

Анықтама. ҚБЖ ең кіші қабырғалар санымен қуаты бойынша ең кіші деп аталады.

Мысал.

Анықтама. Ең кіші ҚБЖ-ң графтың бүркейтінқабырға санының деп аталып, белгіленеді.

Мысал.

Теорема. бөліктенген төбелілер тұрмайтын): , мұндағы - төбелілер саны .

Мысал.

, . .

Анықтама. графтың қабырғалар жиынының ішкі жиыны кемелденген тәуелсіз қабырғалар жиыны (КТҚЖ) деп аталады, егер ол бір уақытта ҚТЖ мен ҚБЖ болса.

Мысал.

ДС 10. Төбелік және қабырғалық графтардың байланысы

Графтың төбелік байланысы

Анықтама. Ішкі жиын төбелік ішкі жиыны графа егер граф, бағанынан алынған - нан барлық шыңдардың байланысы жоқ немесе бір щыңын өшіру төбелік бөлуші жиыны (ТБЖ) деп аталады

Мысал.

- ТБЖ, дәл осылай бағана

- байланыссыз.

Анықтама. ТБЖ ең аз санының төбесі қуаттың ең азыТБЖ деп аталады.

Мысал.

Анықтама. Төбелерінің санының ең азы ТБЖ төбелерінің байланысты графы деп аталып, былай белгіленеді .

Мысал.

Ескерту. Егер граф байланыссыз немесе бір төбелі болса, онда .

Анықтама. төбенің граф көп төбелердің арасынан , егер граф , графынан алынған төбені өшірсе және гөрі байланыстылық компоненті көп болса, ол мүшелену нүктесі деп аталады.

Мысал.

Төбесі - мүшелену нүктесі, себебі граф

- гөрі байланыстылық компоненті көп

Графтың қабырғаларының байланысы

Анықтама. ішкі жиын қабырғалардың жиыны графы, егер бағана , графы алынған барлық қабырғалардың өшірілуі байланыссыз болса, қабырғалар жиынын бөлу(ҚЖБ) деп аталады.

Ескерту. Сонымен қатар ҚЖБ де қиылған деп аталады.

Мысал.

- қабырғалар жиыны.

-дәл осылай ҚЖБ граф

- байланыссыз.

Анықтама. Ең аз қабырғалар саныҚЖБ қуаттың азаюы ҚЖБ деп аталады.

Мысал.

Анықтама. Ең аз қабырғалар саныҚЖБ қабырғалар байланысы деп аталып, графы белгіленеді.

Мысал.

Ескерту. Егер граф бір төбелі және байланыссыз болса, онда .

Анықтама. қабырға көп қабырғалардан графтан , ал егер графы графынан алынған қабырғасын өшіріп , байланыстылық компоненті құрамында көбірек болса, онда ол көпір деп аталды.

Мысал.

- көпір, дәл сондай граф

- байланыстылық компоненті құрамында көбірек .

Теорема. ,

қайда - ең аз төбелер дәрежесі.

Мысал. , , . .

ДС 11. Есептер және графтар

Графтар теориясының негізімен байланысқан - графтың төбелік дәрежесіне есептер қарастырайық. Олимпиядалық ойында әр түрлі спорт түрлерінің сайыскерлері алдынғы сайыстарда кездескен, сондықтан да олар бір-бірімен таныс.

Мандат коммисиясының мүшелері, тілшілер және оргкомитеттің мүшелері сайыскерлердің анкетасын қарастырып, олардың «танысуларына» байланысты заңдылықтарды білмекші болды. Сол мақсатқа жету үшін олар сайыскерлерді нүкте ретінде, ал олардың «танысуларын» нүктелерді қосатын сызық ретінде алды олар оргкомитетке кіретін математиктан консультация сұрады, бұл түрдегі «суреттер» математика ғылымында граф деген ұғымды білдіретінің білді.

Тілшілер консультация алып, кейбір заңдылықтарды байқады және өздерінің болжамдарын айтты (гипотеза).

Еркін күрес жайлы баяндайтын тілші байқағаны:

Болжам 1: Әрбір балуанда екі таныс болғандықтан, онда бір - бірін білетін кем дегенде 3 жұп балуан табылады.

Күрес жайлы баяндайтын тілшімен бірге, олар бұл гипотезаны қорытындылап және дәлелдеп берді.

Теорема 1. графтың кез келген екі төбесіне олармен бірге көршілес төбе бар болса, онда оның ішінде «ұшбұрыш» бар.

Дәлелдеуі: Бұл графта кем дегенде бір қабырға бар. Ол.. және.. төбелерін байланыстырсын. Шарт бойынша.... төбелерімен бірге.. төбесі де бар. Онда... ұшбұрышты анықтайды.

Мандат комиссиясының мүшесі оқтар атқышына жауапты өкіл байқағаны:

Болжам 2. Әрбір сайыскердің кем дегенде бір танысы бар және танысы жоқ. Ол сайыскерлерді екі топқа бөліп, әрқайсысында кем дегенде бір танысы шықты. Бұл кездейсоқ па?

Тілшілер оған көмектесе алмады оған математик көмектесті.

Теорема 2. Егер p- төбесі бар графта төбелерінің дәрежесі 0 және p-1 дәрежесі болмаса, онда төбелерінің жиынын екі ішкі жиынға бөлуге болады, демек әрбір төбе өзінің кем дегенде бір ішкі төбелер жиынымен кездеседі.

Консультант мандат комиссия мүшелеріне өз бетімен дәлелдеуді ұсынды, және дәл сондай сайыскерлердің екі топқа «бөлінуін» көрсетті, әр сайыскер өзінің тобындағы кем дегенде біреуімен таныс емес.

Ал жебеден атуға жауапты мандат комиссиясының мүшесі, әріптестерімен өзінің пікірімен бөлісті.

Болжам 3. Әрбір сайыскердің кем дегенде бір танысы болса, онда кез келген екіуіне олармен таныс болмайтындай үшіншісі табылады, онда әрбір сайыскердің өзінің тобынан кем дегенде бір танысы болатындай үш топқа бөлу менім қолымнан келеді.

Бұл жағдайда да жалықпайтын консультантқа мандаттық комиссия мүшесінің сөздері ақиқат екенін айтты.

Теорема 3. Егер графта нөлдік дәрежесі болмаса және кез келген жұп төбеге онымен бірге көршілес емес төбе табылады, онда оның әрбір төбесі өзінің ішкі жиынынының кем дегенде бір төбесімен көршілес болатындай үш ішкі топқа бөлуге болады.

Дәлелдеуі. Бұл графта p-1 дәрежесі бар төбе жоқ. Кері жағдайда, егер..- төбесі басқа төбелермен көршілес болатын болса және..- кез келген төбе, онда.. және.. үшін теореманың шарты бұзылады. Онда 2 теореманы қолданып, V төбелер жиынының... және.. ішкі жиындарға бөлінуін аламыз осы екеуінің әрқайсысы «өзінің» ішкі жиыны кем дегенде біреуімен көршілес болатын... және.. құрылған.. графтардың біреуі дәл солай 2 теоремадағы шартты қанағаттандырады.

Оларда шынымен төбелерінің 0 дәрежесі жоқ, демек өзінің ішкі жиындағы кем дегенде біреуімен көршілес болады. Оларда басқаларымен көршілес болатындай төбе жоқ. Егер кері жағдайды болжасақ, демек.. және.. сәйкесінше барлық төбелерімен көршілес болатындай.. және бар болса, онда онда.. және.. мен бір уақытта көршілес болмайтын төбе табылмайды теоремаға қарама-қайшы. Онда, осы осы жиындардың біреуінің екіге бөлінуін қарастырғанда, біз ізделінді V жиынының үш бөлікке бөлінуін аламыз.

Жеңіл атлетика бойынша басты судья, сайыскерлердің құрамын қарастырып анализдар жасап, өз пікірін айтты.

Болжам 4. Сайысқа қатысатындар кем дегенде біреуімен таныс емес, ал екі сайыскер үшін кем дегенде бір таныс бар болса, онда әрбір ауыр атлеттер үшін тура бір күн беріледі, бір-бірін білмейтіндей сайысты 3 күнде өткізуге болады.

Консультанттың көмегін қолданбай ол сөйлемді өзгертіп және қосымша графтың түсінігін қолданып бұл гипотезаның ақиқат екенін дәлелдеді.

Теорема 4. Егер графта дәрежесі бар төбеболмаса, бірақ та олармен бірге көршілес болатын төбе болса, онда Төбелер жиынын үш ішкі жиынға бөлуге болады, демек әрбір төбе өзінің кем бір төбесімен көршілес болмайды. Дәл сондай жағдай дзюдо күресінде болды, бұл сайыстардың бас судьясы өз гипотезасын айтты:

Болжам 5. Сайыскерлердің барлық саны 300-ге тең, олардың кез келген екеуінің бір танысы бар. Сәйкесінше барлығының ішінен маған басқаларын да білетіндей 100 –сайыскерлерді таңдауыма болады.

Консультанттың көмегімен ол өз гипотезасын нақтылады.

Теорема 5. төбесі бар граф үшін кез келген жұп төбелер үшін олармен көршілес болатын төбе табылса, онда басқаларымен кем дегенде біреуімен көршілес болатындай -төбелерді ерекшелеуге болады.

Дәлелдеуі. санына консультант математикалық индукция әдісін қолданды.

1) Шартты қанағаттандыратын жалғыз үштөбелік граф ол «ұшбұрыш» және оның кез келген төбесі шартты қанағаттандырады.

2) үшін болжам дұрыс болсын. төбелері бар графты қарастырайық. Шарт бойынша, кем дегенде бір қабырғасы бар болады. Кабырға және төбелерін қоссын. Онда олармен бірге көршілес болатын төбе табылады. - ұшбұрыш болса, осы барлық төбелерді жойып төбесі бар графты аламыз. Екі жағдай болуы мүмк ін.

а) графында кез келген төбелер жұбы үшін олармен бірге көршілес болатын төбе табылады. Онда индукция болжамы -төбелер жиыны бар, осы жиында қалған кез келген төбелермен көршілес болатын кем дегенде бір төбе бар.

б) графында онымен көршілес болатын үшін олармен бірге көршілес болатын төбе табылмайды.

Ең көп жиналған сайыскерлер жеңіл атлетикадан болды, алайда олардың саны жұп болды және де екі сайыскерлердің таныстарының және таныс еместерінің жұп саны табылда.

Консультантқа оның да кездейсоқ емес екенін дәлелдеуге тура келді.

Теорема 8. Жұп төбелері бар кез келген граф үшін, кем дегенде бір жұп төбелер саны табылады, ол жұппен көршілес болатын төбелерінің саны жұп болады.

Дәлелдеуі. 1) кері жағдайды қарастырайық, демек Кез келген жұп үшін онымен бірге көршілес болатын төбелерінің саны –тақ болсын.

2) графының барлық төбелерінің дәрежесі жұп болады екенін көрсету керек. Егер -кез келген төбе, және -төбелердің -тағы тақ санымен көршілес. Онда, төбелер жиынында -ішкі граф болса, онда -барлық төбелерінің дәрежесі тақ, сәйкесінше олардың саны жұп, демек -жұп. -кез келген төбе болғандықтан, онда -дағы барлық төбелер жұп дәрежелі болады.

3) граф -дағы және төбелерді жойғаннан пайда болғандықтан:

а) -дағы жұп дәреже болса, онда -дағы тақ дәреже болса онда олардың саны жұп болады.

б) қалған төбелерінің саны - тақ са, шарт бойынша жұп, -жұп және -дегі дәрежелерінің саны жұп.

ДС 12. Жазық графтар. Дұрыс және қабырғалық графтардың бояулары.

Жазық графтар. Планарлық графтар. Планарлық графтардың белгілері

Тапсырма (0 3-үйде және 3-құдықта): 2 сүрлеу жол қағыспайтындай етіп әр 3 үйден 3 құдыққа сүрлеу жол жасау керек. Бұны істеу мүмкін бе?

Анықтама. Граф Планарлық деп аталады егер, 2 қабырға «ішкі» нүктеде қағыспаса және оны жазықтықта салса, бұндай графаны жалпақ графа деп атайды.

Мысал.

- Планарлық граф (анықтамамен)

графаны жазықтықта салу:

- жалпақ граф.

Қосымша. Шекараның әрбір жалпақ граф көп нүктелі жазықты бөледі.

Мысал.

Граф 4 шекараны анықтайды. № 4 шекара – сыртқы, қалғандары– ішкі

Теорема 1. ,

- төбелік санд, - қабырға сандары, - шекара сандары.

Дәлелдеуі.

- сүйек графасы , ағаш, қабырғаларды өшіргеннен пайда болған. Бұл ағашқа : . Онда .

графты табу үшін - дан жүйелі түрде қабырға қосамыз. Бұл жағжайда төбенің сандары өзгертілмейтін болады ал шекара мен қабырға сандары одан әрі 1-ге ұлғая түседі. Сондықтан.

Бекіту 1. графы (5 шыңда жалпақ граф) планар емес.

Дәлелдеуі.

1. кері жағдайды - планар болсын.

Онда теорема бойынша 1: .

2. Кез келген тегіс графтың беті тура екі бөліктің шекраларасына немесе көпір болады. Кез келген бөлік шектеулі кем дегенде 3 қабырғамен. Онда .

3. демек . Қарама-қайшылыққа келдік. Сәйкесінше, - планар емес.

Бекітпе 2. Граф (толық екі бөлікті граф әрбір бөлікте 3 төбеден) планар емес.

Дәлелдеуі.

1. Кері жағдайды қарастырайық, демек -графы планар емес.

Тогда по теореме 1: .

2. Кез келген тегіс графтың беті тура екі бөліктің шекаларалары немесе көпір болады. Кез келген бөлік кем дегенде төрт қабырғадан тұрады ( - екі бөлікті болғандықтан және , тақ ұзындығы бар циклы жоқ). Онда .

3. Демек . Қарама-қайшылыққа келдік. Сәйкесінше, - планар емес.

Анықтама. Граф графы называется гомеоморфтык графу , Егер ол қосылуымен байланысты болса, онда оның қабырғаларының дәрежесі екіге тең.

Дата добавления: 2015-09-27 | Просмотры: 1132 | Нарушение авторских прав