Курсова работа по Числа на Ремзи



Дата24.10.2018
Размер94.45 Kb.


СУ „Св. Климент Охридски”



Курсова работа

по

Числа на Ремзи
на …………………….,

ф.н. 33233


специалност: информатика






Съдържание

1.Основни понятия........................................................................3

2.Леми и Теореми.......................................................................3

3.Условия и решения на задачи...............................................5

3.1.Задача 1...........................................................................5

3.2.Задача 2...........................................................................7

3.2.Задача 3...........................................................................9

4.Легенда...................................................................................12

5.Използвана литература.........................................................12



Основни понятия
Деф.1.Под граф, ще разбираме схемата на познанства на някаква компания. По такъв начин на всяка компания се съпоставя граф, който я определя напълно. Точките, които изобразяват членовете на компанията, се наричат върхове на графа. Точките изобразяващи членовете на компанията, се наричат върхове на графа. Плътните линии, изобразяващи в схемата запознанствата, се наричат ребра на графа.
Деф.2.За два върха на графа ще казваме, че са съседни, ако са съединени с ребро. За две ребра на графите ще казваме, че са съседни, ако имат общ връх.
Деф.3.Множеството от върхове на графа, всеки два от които са съседни, се нарича клика; в случай че броят на върховете на кликата е s , то тя се нарича s-клика.
Деф.4.Граф, в който множеството от всички върхове е клика, се нарича пълен граф и се означава с Кn, ако n е броят на върховете му.
Деф.5.Нека G и Г са два графа. Ще казваме, че G е подграф на Г, ако всеки връх на G е връх на Г и всяко ребро на G е ребро на Г.
Деф.6.Зададено е 2-оцветяване на ребрата на един граф G, ако всяко от тях е оцветено в един от два предварително зададени цвята. Ще считаме, че единият е черен, а другият е бял.


Теореми

Теорема1.Нека имаме пълен граф G и при всяко 2-оцветяване на ребрата на G не се получава едноцветен триъгълник. Тогава всеки връх на G има най-много 2 бели и най-много 2 черни ребра излизащи от него.
Доказателство:

Да допуснем, че връх А е свързан посредством бяло ребро с : B, C и D. Ако B и C са свързани също с бяло ребро, тогава заедно с А те образуват триъгълник, което е невъзможно.Следователно никои два върха измежду B, C и D не са свързани с бяло ребро, т.е. те са свързани с черно. Тогава B, C и D образуват черен триъгълник, което е в противоречие с условието, следователно допускането не е вярно.

Теорема 1 е доказана.
Теорема2.Нека имаме пълен граф с поне 5 върха и при всяко 2-оцветяване на ребрата не се получава едноцветен триъгълник. Тогава графът се състои точно от 5 върха.
Доказателство:

Съгласно Теорема 1, имаме, че графът има точно 5 върха, като от всеки връх излизат точно 2 бели и 2 черни ребра.

Теорема 2 е доказана.
Теорема3.При всяко 2-оцветяване на ребрата на пълен граф с поне 6 върха се получава или черен или бял триъгълник.

Доказателство:

Ако допуснем, че в графа няма едноцветни триъгълници, тогава по Теорема 1 следва, че всеки връх има точно по две ребра от даден цвят излизащи от него. Тогава общия брой на ребрата на графа е максимум е 20.Следователно графа има най-много пет върха, което е в противоречие с условието.

Теорема 3 е доказана.
Теорема4.При всяко 2-оцветяване на ребрата на граф К6 се получават поне два едноцветни триъгълника.
Доказателство:

От Теорема 3 знаем, че има поне един едноцветен триъгълник. Да допуснем противното на това, коеото трябва да докажем, а именно, че други едноцветни триъгълници няма. Да номерираме върховете с 1, 2, 3, 4, 5, 6 и нека (1,5,6) е единствения триъгълник. За определеност ще смятаме, че (1,5,6) е бял триъгълник. Ще отстраним временно от графа връх с номер 6. Останалите 5 върха образуват граф без едноцветен триъгълник. От Теорема 2 следва, че всеки от тези върхове има точно две бели и две черни ребра излизащи от него. Тогава 1 и 5 са свързани с бяло ребро. Нека другия връх, с който 1 е свързан посредством бяло ребро е 2, а за 5- 3. Значи 2 и 3 не са свързани с бяло ребро, следователно те са свързани с черно. Освен това връх 6 не е свързан с бяло ребро с връх 2, тъй като иначе (1,2,6) щаха да образуват бял триъгълник, а ние сме допуснали, че друг едноцветен триъгълник освен (1,5,6) няма. По същите съображения връх 3 не е свързан с бяло ребро с връх 6. Оказва се, че (2,3,6) образуват черен триъгълник. Така достигнахме до противоречие с допуснатото, следователно то не е вярно. Така теоремата е доказана.



Лема1.При всяко 2-оцвтяване на ребрата на граф К7 има поне три едноцветни триъгълника.
Доказателство:

Съгласно Теорема 3 в пълен граф със 7 върха има поне един едноцветен триъгълник α. Нека А е един от върховете на графа, който участва в този триъгълник α. Нека отстраним връх А от графа и приложим Теорема 4 за останалите върхове от графа. Заклчючаваме, че графа образуван от тези пет върха съдържа поне два едноцветни триъгълника µ и β, които са различни от α понеже α съдържа връх 6, който не участва нито в µ, нито в β.

Лема1 е доказана.
Лема2.При призволно 2-оцвтяване на ребрата на граф К7 има връх участващ в поне два едноцветни триъгълника.

Лема2 е доказана.


Доказателство:

Съгласно Лема 1 в К7 има поне 3 едноцветни триъгълника. Ако допуснем, че никои две от тях нямат общ връх, тогава графа би имал поне 9 върха, което е в противоречие с условието.


Теорема5.При произволно 2-оцветяване на ребрата на граф К7 има поне четири едноцветни триъгълника.
Доказателство:

Съгласно Лема 2 има връх- да го означим с А- който участва в поне два едноцветни триъгълника α и β- на К7. Отстраняваме А и към образувания от останалите върхове граф- К6 прилагаме Теорема 4, за да заключим, че той съдържа поне два едноцветни триъгълника- ν и µ. Триъгълниците α и β съдържат върха А, докато ν и µ не го съдържат. Следователно всички тези четири триъгълници са различни.

С това теоремата е доказана.

Задачи

Задача1. R(G4)=7, т.е. при произволно 2-оцветяване на ребрата на пълния граф К7 винаги има едноцветен (бял или черен) граф G4 и 7 е най-малкото число с това свойство, където G4 е следния граф:


Решение:

Ще покажем, че същесвува пълен граф със 6 върха, от всеки връх на който не излизат повече от 3 ребра от един и същи цвят, т.е. няма връх от който да излизат 4 на брой ребра от един и същи цвят.

В пълния граф с 6 върха, всеки връх е свързан с още пет други. Значи от един връх трябва да имаме най-много три ребра от един и същи цвят. За удобство ще означим върховете на графа с ν 1, ν 2, ν 3, ν 4, ν 5, ν 6. Без ограничение на общността можем да смятаме,че i-тия връх е свързан с (i+1)-ия с бяло ребро i=1,2,…,5 (ν 6 е свързан със ν 1 също). Останалите ребра са черни.

Графът е представен на следващата фигурата:



Нека сега добавим ν 7. Ако го свържем с черно ребро с някой от върховете от ν 1 до ν 6, то за кой да е от тях ще получим, че от него излизат 4 ребра от черен цвят, така получаваме черен граф G4. Ако свържем ν 7 с бяло ребро с останалите върхове. Тогава от него пък излизат 6 бели ребра, което съдържа в себе си 4 и така получаваме бял граф G4. Така твърдението е доказано.





Задача2.R(G5)=6, т.е. при произволно 2-оцветяване на ребрата на пълния граф К6 винаги има едноцветен граф G5 и 6 е най-малкото число с такова свойство.

G5 е следния граф:





Решение:

Нека разгледаме пълен граф с 6 върха. ( с върхове ν 1, ν 2, ν 3, ν 4, ν 5 , ν 6).

В него всеки връх се свързва чрез 5 ребра с останалите. Следователно при произволно 2-оцветяване на ребрата имаме следните възможности:


  • От един връх да излизат 5 ребра, оцветени в единия от цветовете и нито едно ребро, оцветено в другия цвят.

  • От един връх да излизат 4 ребра, оцветени в единия от цветовете и 1 ребро, оцветено в другия цвят.

  • От един връх да излизат 3 ребра, оцветени в единият от цветовете и 2 ребра, оцветени в другия цвят.


Забележка: Изброените възможности са единствени, тъй като останалите 3 можем да получим при преименуване на цветовете, тъй като при гореспоменатите не конкретизираме кои точно са цветовете.

1 сл.) Да допуснем, че от някой връх излизат 5 ребра с черен цвят. За удобствo нека това е ν 1. Ако от някое от ребрата (ν65), (ν54), (ν43), (ν23) (ν62), (ν63) е пак черно ще получим горепосечения граф G5 в черно. Оцветяваме ги в бяло, но тогава получаваме споменатия подграф G5 в бял цвят.




2 сл.)Да допуснем, че от ν 1 излизат 4 ребра с черен цвят- (ν12), (ν12), (ν13) и (ν1,v4). Тогава aкo върховете ν 1, ν 2, ν 3 и ν 4 са свързани с други черни ребра ще получим G5 -в черно Оцветяваме останалите ребра през ν1, ν2, ν3, ν4 в бяло, но сега получаваме G5 в бяло.


3 сл.)Остана да разгледаме случай, в който, от ν 1 излизат три черни ребра- (ν12) ,(ν13) ,(ν14) и 2 бели ребра- (ν15), (ν16). От никой от върховете ν2, ν3, v4 не трябва да излиза ребро в черен цвят към ν5 и ν6, в противен случай ще получим G5 във черно. Тогава от тях излизат ребра в бяло и отново получаваме G5, но във бял цвят:

С това твърдението е доказано.


Забележка: На чертежите не са показани всички ребра за да не се претрупват и да се отличава ясно получения подграф.
Задача3.R(G10)=9, т.е. при произволно 2-оцветяване на ребрата на пълния граф К9 винаги има едноцветен граф G10 и 9 е най-малкото число с такова свойство. G10 има следния вид.

Решение:

Нека покажем, че същесвува пълен граф с 8 върха, в който няма подграф от търсения вид. Това е точно гръфът от следваща фигура:



Нека сега разгледаме пълният граф със 9 върха. В този граф всеки връх се свързва чрез 8 ребра с останалите. Следователно при произволно 2-оцветявания на ребрата имаме следните възможности:



  • От един връх да излизат 4 ребра, оцветени в единия от цветовете и 4 ребра, оцветени в другия цвят.

  • От един връх да излизат 3 ребра, оцветени в единия от цветовете и 5 ребра, оцветени в другия цвят.

  • От един връх да излизат 2 ребра, оцветени в единия от цветовете и 6 ребра, оцветени в другия цвят.

  • От един връх да излизат 1 ребра, оцветени в единия от цветовете и 7 ребро, оцветено в другия цвят.

  • От един връх да излизат нито едно ребро, оцветено в единият от цветовете и 8 в другия.


Забележка: Изброените възможности са единствени, тъй като останалите 5 можем да получим при преименуване на цветовете, тъй като при гореспоменатите не конкретизираме кои точно са цветовете.
1 сл.) Нека от връх ν1 излизат 5 ребра в бяло -(ν12), (ν 1 3), (ν 1 4), (ν15) и 3, оцветени в черно – (ν19), (ν18), (ν17), (ν16). За да не се получи посочения в условието на задачата подграф G10 в черно трябва да оцветим ребрата свързващи върховете ν9, ν8, ν7, ν6 в бяло, аналогично ν2, ν3, ν4, ν5 в черно. Тогава какъвто и цвят да използваме за реброто (ν65) винаги получаваме едноцветен подграф G10 .

2 сл). Нека от връх ν1 излизат 3 ребра в бяло -(ν1, ν2), (ν1, ν3), (ν1, ν4) и 5, оцветени в черно – (ν1, ν9), (ν1, ν8), (ν1, ν7), (ν1, ν6), (ν1, ν5). За да не се получи посочения в условието на задачата подграф G10 в черно трябва да оцветим ребрата свъзващи върховете ν9, ν8, ν7, ν6, ν5 в бяло, но тогава получаваме подграфът G10 оцветен в бяло.



3 сл.) Като следствие от случай 2 може да заключим, че ако имаме 5 едноцветни ребра излизащи от един връх, то винаги ще получаваме едноцветен подграф G10. В случай 1 разгледахме единственият вариант когато от връх не излизат 5.


С това твърдението е доказано.

Забележка: На чертежите не са показани всички ребра за да не се претрупват и да се отличава ясно получените подграфи.




Легенда

- - - - - - - - бяло ребро

________ черно ребро


Използвана литература
1. Хаджииванов Н.,Числа на Рамзи,Изд.Народна Просвета,София(1982)







База данных защищена авторским правом ©obuch.info 2016
отнасят до администрацията

    Начална страница