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

Мысалы. Кері жағдайды қарастырайық дем

Теорема 1. .

Дәлелдеуі.

Кері жағдайды қарастырайық демек .

болсын, онда .

Графтың төбелік бояуы дұрыс деп аталады егер екі көршілес төбелер бір түске боялмаса.

Сондықтан да кликалардың төбелік бояуына кем дегенде түрлі түс қажет болады. Қарама-қайшылыққа келдік.

Сәйкесінше,

Теорема 2. ,

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

Дәлелдеуі.

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

1. :

2. Болжайық, .

Дәлелдейік , где - графы төбелерде, төбелерін қосқанда графынан алынған. (Төбелерді қосқан кезде оның қабырғалық инциденттері де қосылуы мүмкін)

, , , ,

графты түске бояуға болады.

графты бояу үшін бояған жеткілікті.

, , бояудан бояуға арналған кем дегенде бір төбе табылады.

.

Теорема 3. ,

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

- тәуелсіз төбелерінің саны.

(дәлелдеусіз)

4 түстің гипотезасы (1850 ж.). .

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

Есеп. 300 адамнан тұратын компанияда ең көп жұппен білмейтін адамдардың саны 10 тең. Бұл компанияны 291 топқа бөлуге болады екенін және бір топтың кез келген екеуі таныс болмайтындай, бірақ 29 топқа бөлінбейтінін дәлелдеңіз. (3 теорема бойынша)

Графтың қабырғалық бояуы

Анықтама. Графтың қабырғалық бояуы деп графтың әрбір төбесіне белгілі бір түспен (номермен) белгілесе.

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

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

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