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

Эйлер графтар

Анықтама. Графтің әр бір қабырғасы бір рет кіретін циклді эйлер циклі деп аталады, ал осындай циклі бар графті эйлер граф деп аталады.

Мұндай графтар түрін анықтау проблемасы Л. Эйлермен 1736 жылы шешілді.

Теорема 2. графы эйлер графы болу үшін, оның

1) Ол байланысты болу керек;

2)барлық төбелерінің дәрежелері жұп болатыны қажетті және жеткілікті.

Есеп. Қаланың бүкіл түйіскен жерлеріне, екеуінен басқа, 4 жол қиылысады; ал бұл екеуіне – 5 жолдан. Бірақ кез келген түйіскен жерлерінен кез келген басқаға жетуге болады. Қар тазалатқыш әр жолдан бір рет қана өтетіндей етіп, бүкіл жолдарды тазалау мүмкін бе.

Ескерту. Бұл есепте қар тазалатқыштың шыққан жеріне оралуы қажетті емес, сондықтан да теорема 2 пайдалануға болмайды.

Теорема 3. Графтің әр бір қабырғасы бір рет қана кіретіндей тізбегі табылу үшін,

1) граф байланысты болу керек; 2) дәл екі төбесінің дәрежелері тақ болатыны қажетті және жеткілікті.

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

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

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

Ескерту. Осы теореманың тұжырымдамасында тақ дәрежесінде төбелер саны – жұп екендігі есепке алынды.

ДС 4. Гамильтон графтар. Түрлі түсті қабырғалы графтар. Рамси теоремасы

Гамильтон графтар

Анықтама. Графтің әр бір төбесі бір рет кіретін циклді гамильтон циклі деп аталады, ал осындай циклі бар графті гамильтон графы деп аталады.

Гамильтон графтар түсінігі ирландиядан В. Гамильтон ирландияның математигімен байланысты, ол 1859 жылы, додекаэдр графында гамильтон циклі табылатындай, «кругосветное путешествие» ойынын шығарды.

Теорема 1. Егер байланыс графтің ең ұзын жай тізбесі және болса, онда графі гамильтон болып табылады.

Салдар 1. Егер грфтің кез келген сыбайлас емес және төбелері үшін : болса, онда - гамильтон графы. мұндағы - графтің төбелерінің саны, () болу керек.

Салдар 2. Егер графтің кез келген төбесі үшін болса, онда - гамильтон графы. Мұндағы - графтің төбелерінің саны.

Дәллелдеу үшін салдар 1 қолдануға жеткілікті болады.

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

Түрлі түсті қабырғалы графтар. Рамси теоремасы

Есеп. Алты оқушы бір кез келген ойнайтын дайбы турниріне қатысады. Олардың ішінде бір бірімен барлық ойындарда кездескен немесе бір-бірімен бірде-бір ойында кездеспеген 3 оқушысының табылатынын дәлелде.

Графтар теориясының тілінде осы сөйлемді келесідегідей тұжырымдауға болады.

Теорема 1 (Рамсеи теоремасы). Қабырғалары екі түспен боялған екі немесе одан да көп төбені кез келген графтің ішінде бір түсті қабырғаларымен кем дегенде бір үшбұрыш табылады.

ДС 1.

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

Анықтама. - ең кіші бүтін сан үшін әр бір граф төбелерінде не , не бар. Ол сандар Рамси сндары болып табылады.

Мысал.

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

1 қасиет.

2 қасиет.

3 қасиет.

және үшін Рамси сандар табылды. Мысал, , , .

ДС 5. Графтар теория бойынша кейбір экстремалдық есептер. Бағытталған графтар

Графтың экстремалдығы- бұл шекті мүмкін графтар,анықталған қасиеттерге сүйене отыра.

1 мысал. Байланысты графтың қабырға санының ең аз шыңы .

2 мысал. Байланыссыз графтың қабырға санының ең көп шыңы .

Экстремальдық графқа байланысты кейбір есептерді қарастырайық.

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

Сұрақтың жауабы келесі келесі сөйлемде көрсетіледі.

1 теорема (Туран). Үшбұрыштары болмайтын төбелі графтың қабырғаларының ең үлкен саны тең.

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

Мысал.

2 теорема. Гамильтон болмайтын төбелі графтың қабырғаларының ең үлкен саны тең.

граф болып табылады, егер теңдік граф болып табылса.

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

Анықтама. төбесінен төбесіне жетуге болады дейміз, егер басы - да, ал аяғы - да орналасатын бағытталған жол деп аталады.

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

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

Анықтама. бағытталған графтың негізгі табаны байланысты графты әлсіз бағытталған граф деп аталады.

3 теорема. бағытталған графтың күшті байланысты графы болу үшін оның ішінде астофты цикл да табылуы қажетті және жеткілікті.

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

5 теорема. Егер - әлсіз байланысты граф болса және оның кез келген төбесі үшін кіру және шығу жартылай дәрежелері бірдей болса, онда оның ішінен әрбір доғасы бір рет кіретін циклды жол табылады. : .

Есеп. Бір круг турнир волейбол ойнайды. Команданы осындай қатарға қоюға болатынын және бастапқысы соңғысын жеңетінің дәлелдеу керек. (футболмен салыстырғанда волейболдың, баскетболдың, теннистің тең болуы болмайды)

Бұл есепті шешу үшін келесі түсінікті қарастырамыз.

Анықтама. Негізі толық граф болатын бағытталған графты турнир деп аталады.

1 теорема. Әрбір турнирдің ішінен астофты жол табылады.

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

2 теорема. Егер турнирдің төбесі ойнатылған жиынға тиісті болса, онда басы -де болатын астофты жол табылады.

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

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

Есептер (А қиындық деңгейі):

1. Кейбір жарыстардағы тең емес нәтижені кестеде қолдана отырып, лайықты графты құрастырамыз. Оның матрицасының аралас төбесін табамыз.

2. Алдағы есептегі турнирдің астофты жолын табамыз. Бұл турнирде «ұрылған» жиынның төбесі бар ма?

3. күшті байланысты турнирін құрастырыңыз.

4. Контурдың ұзындықтарын табыңыздар:3,4,5,6 алда5ы есептің турнирлері.

5. Турнирдің алты төбесін табыңыздар, кез келген екі бірдей жарты дәрежелі нәтиже болса.

6. Күшті байланысты турнирде «ұрылған» жиынның төбесі бар ма?

7. p=7 төбесінің контурсыз турнирін құрастырыңыз.

8. турнирін құрастырыңыз, кез келген төбеге байланысты v: deg⁺v=deg^-v. Бұл турнирде бағытталған үшбұрыштың санын табыңыздар.([1], 12.17 есеп).

9. турнирін құрастырыңыз, кез келген төбеге байланысты v:|deg⁺v-deg^-v|=1. Бұл турнирде бағытталған үшбұрыштың санын табыңыздар.(12.18 есеп).

10. қатты емес байланысқан турнирінен қатты байланысқан турнирді аламыз (12.7 [1] есеп)

11. 8 төбеден тұратын ұрылған емес жиындағы төбешіктің турнирін құрыңыз.

12. 8 төбелі турнир құрыңыз, егер жарты дәрежелі кез келген төбе нөлден басталса.

13. 7 төбелі турнир құрыңыз, егер жарты дәрежелі төбешіктің бәрі тең болса.

14. 8 төбелі транзитивті турнир құрыңыз.

15. 5 ұзындықты циклдан тұратын 8 төбелі турнирді құрыңыз. Бұл турнирдегі үшбұрыштың бағытталған санын табыңыз. (квант 2007 №5)

Есептер (В қиындық деңгейі):

1. Кез келген турнир қатты байланысқан немесе оны тек бір доғамен бағытталған қатты байланысқан турнирді құруын көрсетіңіз.

2. Егер турнирдің төбесі (n≥3) бірдей жарты дәрежелі болады, егер үшбұрыш бағытталған болса.

3. Кез келген турнирдің төбесінен ең аз арақашықтығына дейінгі кез келген басқа төбе 1және 2-ге тең.

4. Егер к ұзындықты циклдың (n≥3) турнир болса, онда 3 ұзындықты цикл (k-2).

5. Егер турнир жарты дәрежелі барлық төбесі тең болса, онда n төбесінің саны тақ болатынын дәлелдеу керек.

6. Сонда тек сонда егер турнир қатты байланысқан болса, онда оның гамильтон екенін дәлелдеу керек.

Есептер (C қиындық деңгейі):

1. Кез келген турнирде гамильтон жолы болатынын дәлелдеу керек.

Граф транзитивті деп аталады, егер кез келген және екі доғалардан доға шығады.

2. Транзитивті турнирде бір ғана гамильтон жол бар екенін дәлелдеу.

3. n төбелі турнирде кез келген n контурсыз бар екенін дәлелдеу керек.

4. Кез келген төбенің жарты дәрежесі аз болмасын δ жарты дәрежелі төбеден.Кез келген екі турнирдің төбесінен δ төбесінің арақашықтығын дәлелдеу керек.

5. n төбелі турнирдегі үшбұрыштың бағытталған санынан аспайтынын дәлелдеу керек.

6. Турнир бірден артық қайнар және бірден артық тоқ құралмайтынын дәлелдеу.

7. Егер турнирдің әрбір доғасы бір үшбұрышұа ғана бағытталса, онда n≥30, егер n- тақ және n≥4, егер n- жұп.

8. Егер турнир, v: , кез келген төбесі болса, онда үшбұрыштың бағытталған төбесінің саны тең.

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

10. Егер турниріндегі к төбесі кез келген n төбесі (2< k < n) к контурының ұзындығына тиісті болса, онда кез келген (к+1) төбесі {к+1) контурдың ұзындығына тиісті болатындығын дәлелдеу.

11. Кез келген контурсыз турнирде n төбелі бар, бұдан кез келген басқа төбе шығатынын және жарты дәреже о ге тең төбесі бар екенін дәлелдеу.

12. Егер турниріне 0≤ l ≤ n-1 саны бар, v: кез келген төбесі болатын болса, онда бұл турнирде үшбұрыш бағытталған болатынын дәлелдеу.

13. Егер турнирінде кез келген v: төбесі болса, онда бұл турнирдің құрамында үшбұрыш бағытталған болатынын дәлелдеу.

ДС 7. Графтардың сандық сипаттамалары. Графтың метрикасы. Төбелердің тәуелсіз жиыны. Клика

Графтың метрикасы

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

Анықтама. графтағы төбесінің эксцентриситеті деп саны аталады.

Анықтама. байланысты графтың диаметрі деп – барлықэксцентриситетердің максимал санын айтамыз. , .Осы максимал нүктелерді шеткі (периферийный), ал оларды қосатын ең қысқа тізбелерді диаметрлі тізбелер деп атайды.

Анықтама. байланысты графының радиусы деп саны аталады.

Төбелердің тәуелсіз жиыны

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

Ескерту. ТТЖ-ны төбелердің ішкі тұрақты жиыны деп атауға болады.

Мысал.

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

Мысал.

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

Мысал.

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

Мысал.

Теорема: ,

мұнда - графтың төбелерінің саны,

- төбелер дәрежесінің ең үлкені.

Мысал. , болсын. Сәйкесінше граф

1) 000 2) 100 3) 110 4) 010 5) 011 6) 111 7) 101 8) 001

- қуаты бойынша ең үлкен ТТЖ..Оған максимал қуаттың коды сәйкес келеді.

Клика

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

Ескерту. Кликаны толығымен тәуелді жиын деп атауға болады..

Мысал.

Анықтама. Кликаны ену бойынша максимал болады дейміз, егер ол басқа кликалардың ешқайсысының ішкі жиыны болмаса, яғни оны кеңейтуге болмаса

Мысал.

Анықтама. Төбелер саны ең үлкен болатын кликаны қуаты бойынша ең үлкен дейміз.

Мысал.

Анықтама. Кликалардың ең үлкеніндегі төбелер санын кликалық сан немесе тығыздық деп аталады және деп белгіленеді.

Мысал.

Теорема. ,

мұнда - графтың төбелер саны,

- төбелердің ең кіші дәрежесі.

Теорема. графы графтың толықтауышы болсын.Онда – графының кликасы болады сонда тек сонда, – графының ТТЖ-ны болса.

Дәлелдеуі.

1. - графының кликасы болсын. Онда кликаның анықтамасы бойынша . Бірақ бұл толықтауыштың анықтамасы бойынша болатынын білдіреді. Бұдан, ­ – графының ТТЖ-ны болады.

2. - графының ТТЖ-ны болсын. Онда ТТЖ-ның анықтамасы бойынша болады. Бірақ онда толықтауыштың анықтамасы бойынша болады. Бұдан, - графының кликасы болады.

Мысал.

: :

- графының кликасы. - графының ТТЖ-ны.

ДС 8. Графтың төбелік бүркеуі. Төбелердің доминантты жиыны. Графтың ядросы.

Төбелердің бүркеулік жиыны

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

Мысал.

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

Мысал.

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

Мысал.

Анықтама. ТБЖ-ның ең кіші санын графтың төбелік бүркеуінің саны дейміз және деп белгілейміз.

Мысал.

Теорема. , мұнда - графтың төбелер саны.

Дәлелдеуі.

1) Пусть - ТТЖ-ның ең үлкені, онда . Онда - ТБЖ және бұдан .

(*)

2) Пусть - ТБЖ-ң ең кішісі, онда . Онда - ТТЖ және бұдан .

(**)

Онда (*), (**) . Дәлелденді.

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

Ескерту. ТДЖ-н ішкі тұрақты жиын немесе сыбайлас жиын деп атауға болады.

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