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

ф.н. 33233

Да допуснем, че връх А е свързан посредством бяло ребро с : 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) образуват черен триъгълник. Така достигнахме до противоречие с допуснатото, следователно то не е вярно. Така теоремата е доказана.

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

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

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

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

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

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

Задачи

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


Решение:

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

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

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

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

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

Нека разгледаме пълен граф с 6 върха. ( с върхове ν ₁, ν ₂, ν ₃, ν ₄, ν _{5 ,} ν ₆).

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

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

1 сл.) Да допуснем, че от някой връх излизат 5 ребра с черен цвят. За удобствo нека това е ν ₁. Ако от някое от ребрата (ν₆,ν₅), (ν₅,ν₄), (ν₄,ν₃), (ν₂,ν₃) (ν₆,ν₂), (ν₆,ν₃) е пак черно ще получим горепосечения граф G₅ в черно. Оцветяваме ги в бяло, но тогава получаваме споменатия подграф G₅ в бял цвят.

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

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

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

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

2 сл). Нека от връх ν₁ излизат 3 ребра в бяло -(ν₁, ν₂), (ν₁, ν₃), (ν₁, ν₄) и 5, оцветени в черно – (ν₁, ν₉), (ν₁, ν₈), (ν₁, ν₇), (ν₁, ν₆), (ν₁, ν₅). За да не се получи посочения в условието на задачата подграф G₁₀ в черно трябва да оцветим ребрата свъзващи върховете ν₉, ν₈, ν₇, ν₆, ν₅ в бяло, но тогава получаваме подграфът G₁₀ оцветен в бяло.

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