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

Факултет по математика и информатика

Изготвил: МАТ

Специалност: Компютърни науки

Курс: 1

Факултетен номер: *****

Проверяващ: проф. Н.Хаджииванов

София 2011

Съдържание

1. Понятия........................................................................3

2. Доказателство за R(C₅) .......................................................3

2.1 Съществуване на R(C₅) за 8 елемента ............3

2.2 Доказателство ................................................4

3. Доказателство за R(G₂) ...............................................9

4. Използвана литература.........................................................11

Понятия:

С R(n, m) се представя минималният брой върхове на граф G, така че при двойно оцветяване на ребрата в него да има черна n-клика или червена m-клика. Съответно:

R(C₅, C₅) - при двойно оцветяване има черен или червен цикъл.

R(G₁, G₁) - при двойно оцветяване има черен или червен такъв граф.

Под n-цикъл разбираме свързан граф с n върха, чието обхождане започва от един връх, преминава през останалите n-1 върха само по веднъж и последното ребро е свързано с първоначалния връх. Ще го бележим с C_n.

Доказателство за R(C₅, C₅) = 9
Целта на тази част от проекта ни е да докажем че при произволно черно-червено оцветяване минималният брой върхове е 9, така че да има черен или червен 5-цикъл.

Ще докажем това, като видим че има такова оцветяване за 8 върха така че няма 5-цикъл и съответно ще допуснем, че в граф с 9 върха не съществува едноцветен 5-цикъл.

Нека нашият граф има върхове 1, 2, 3, 4, 5, 6, 7 и 8.

Ще начертаем 2 графа, като в единия ще са само червените, а в другия само черните ребра за по-добра видимост:

(Строенето на тази граф е по същия начин, както и за 9 елемента, за това не е описано. Самото построяване ще видим по-надолу.)

• 
  Има такова оцветяване с 8 елемента, така че да няма едноцветен 5-цикъл.
  
• 
  R(C₅) ≥9
  

Сега ни предстои да докажем, че за всяко оцветяване с 9 елемента, съществува C₅.

Допускаме че C₅ не съществува в оцветяване с 9 елемента.

Нека нашият граф има върхове 1, 2, 3, 4, 5, 6, 7, 8 и 9.

Сега ще използваме, че R(C₄) = 6

• 
  в нашия граф също ще има такова оцветяване.
  

1. 
   Без ограничение (заради симетрията) ще вземем върховете 1, 2, 3 и 4 да образуват цикъл C₄ оцветен в червено, като съответно ребрата са: (1, 2), (2, 3), (3, 4), (4, 1).
   
2. 
   За останалите 5 върха - 5, 6, 7, 8 и 9 е възможно всеки от тях да е свързан с два несъседни върха на C₄ с поне една двойка черни ребра. Защото ако примерно връх 5 е свързан с 1 и 2 с червено ребро получаваме цикъл C₅ от червени ребра. Т ака за всеки връх излиза поне една двойка черни ребра към два несъседни върха на C₄.
   
3. 
   След така построен нашият граф, ще разгледаме няколко случая за черно-червено оцветяване на този граф:
   

0. 
   Ако 2 двойки ребра са свързани с едната двойка срещуположни върхове от C₄, а останалите 3 с другата двойка срещуположни върхове.
   
1. 
   Ако 4 двойки ребра са свързани с едната двойка срещуположни върхове от C₄, а останалата двойка ребра с другата двойка срещуположни върхове.
   
2. 
   Ако 5 двойки ребра са свързани с едната двойка срещуположни върхове от C₄ .
   

Разглеждаме:

Да разгледаме върховете 5, 4, 7, 2, 6. Ако реброто (5, 6) е черно, то при последователното им свързване се образува черен 5-цикъл. Затова нека (5, 6) да бъде червено ребро.

Аналогично за върховете 6, 4, 5, 2, 7 и реброто (6, 7) и 5, 4, 6, 2, 7 и реброто (7, 5)

• 
  ребрата (5, 6), (6, 7) и (7, 5) са червени
  

От върховете 5 и 6 излиза поне едно черно ребро към 1 или 3, т.к. ако от 5 и 6 излиза по една двойка червени ребра, ще се получим червен 5-цикъл, например (4, 1, 5, 6, 3). Затова избираме реброто (1, 5) да бъде черно.

Да разгледаме върховете 2, 7, 9, 1, 5. Ако реброто (7, 9) е черно, то при последователното им свързване се образува черен 5-цикъл. Затова нека (7, 9) да бъде червено ребро.

Аналогично за върховете 2, 7, 8, 1, 5 и реброто (7, 8) и 5, 1, 9, 6, 4 и реброто (6, 9)

• 
  ребрата (7, 9), (7, 8) и (6, 9) са червени
  

• 
  3, 9, 1, 5, 8 образуват черен 5-цикъл, което води до противоречие с допускането
  

3.2) По описания начин по-горе ще свържем 9 с 1 и 3 и също 8, 7, 6 и 5 с 2 и 4. Както е показано на фигурата:

Да разгледаме върховете 4, 7, 2, 6, 5. Ако реброто (5, 6) е черно, то при последователното им свързване се образува черен 5-цикъл. Затова нека (5, 6) да бъде червено ребро.

Аналогично за върховете: 8, 4, 7, 6, 2 и реброто (7, 6)

8, 4, 5, 2, 7 и реброто (8, 7)

2, 6, 4, 8, 5 и реброто (5, 8)

• 
  Ребрата (5, 6), (7, 6), (8, 7) и (5, 8) са червени
  

От случай 3.1) избрахме реброто (5, 1) да е черно. Използвайки същите разсъждения избираме тук реброто (5, 1) да е черно.

Аналогично за върховете: 4, 5, 1, 9, 8 и реброто (9, 8)

• 
  Ребрата (7, 9)и (9, 8) са червени
  

• 
  9, 8, 5, 6, 7 образуват червен 5-цикъл, което води до противоречие с допускането
  

3.3) По описания начин по-горе ще свържем 9, 8, 7, 6 и 5 с 2 и 4. Както е показано на фигурата:

От втори случай вече сме доказали, че ребрата (5, 6), (6, 7), (7, 8) и (8,5) са червени.

Да разгледаме върховете 7, 9, 4, 5, 2. Ако реброто (7, 9) е черно, то при последователното им свързване се образува черен 5-цикъл. Затова нека (7, 9) да бъде червено ребро.

Аналогично за върховете: 8, 9, 4, 5, 2 и реброто (8, 9)

• 
  Ребрата (7, 9) и (9, 8) са червени
  

• 
  9, 8, 5, 6, 7 образуват червен 5-цикъл, което води до противоречие с допускането
  
• 
  След като разгледахме 3-те възможни случая, установихме, че в граф с 9 върха съществува едноцветен 5-цикъл.
  
• 
  R(C₅) = 9
  

Ще използваме, че R(G₂) ≥ 5.

Тогава първо ще трябва да намерим 2-оцветяване с което да покажем, че R(G₂) ≠ 5 и R(G₂) ≠ 6, т.е. ще покажем 2-оцветяване на пълен граф с 5 върха и пълен граф с 6 върха, при което нямаме граф G₂, нито в черен, нито в червен цвят.

Сега ще докажем, че при всяко 2-оцветяване на пълен граф със 7 върха винаги се получава граф G₂ в единия или другия цвят. За целта ще се допуснем, че има 2-оцветяване, при което това не е изпълнено.

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

При всяко такова оцветяване винаги може да се намери едноцветен триъгълник. Нека си вземем един връх. От него излизат 3 едноцветни ребра(фиг.1). Ако допуснем, че няма едноцветен триъгълник, тогава ребрата (3,4), (2,3) и (2,4) трябва да са от другия цвят(червени), защото в противен случай ще се получи едноцветен триъгълник или от {1,4,3}, или от {1,2,3} или от {1,4,2}. Но в такъв случай получаваме едноцветен триъгълник от другия цвят {2,3,4}(фиг.2). Това показва, че при оцветяване на пълен граф със 7 върха в 2 цвята, винаги ще имаме едноцветен триъгълник.

фиг.1 фиг.2

Нека върховете {1,2,7} образуват едноцветен червен триъгълник (фиг.3). Отново поради симетрията и възможността за произволно разполагане на върховете на графа, можем да не разглеждаме други случаи на едноцветни триъгълници съставени от други върхове.

фиг.3 фиг.4 фиг.5

Сега да разгледаме реброто (1,4). Ако то е черно, ребрата (5,6), (3,5), (3,6) и (1,4) образуват граф G₂ в черен цвят. Тогава (1,4) трябва да е червено, но в този случай (2,7), (2,6), (6,7) и (1,4) образуват G₂ в червен цвят.

Така доказахме, че при всяко 2-оцветяване на пълен граф със 7 върха винаги се получава граф G₂ и след като вече показахме, че за графи с 5 и 6 върха не е изпълнено винаги, то 7 е най-малкото число с исканото свойство.

• 
  R(G₂) = 7