Курсът е воден от проф д. м н. Николай Хаджииванов



страница1/4
Дата14.01.2018
Размер1.04 Mb.
  1   2   3   4






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


Курсова работа по Числа на Рамзи
  • Курсът е воден от проф. д.м.н. Николай Хаджииванов


Тема: Графи на Рамзи

2009г.


Съдържание


  1. Въведение


    1. Познати нетривиални стойности и граници за двуцветно оцветявани числа на Рамзи.
  1. Основни дефиниции.


2.1. Дефиниции за подграф.

2.2. Дефиниции за вериги.

2.3. Съединение на графи.

2.4. Оцветяване на върховете на граф.
  1. Хроматично число.


3.1. Неравенства на Нордхауз и Гадум.

3.2. Неравенство на Брукс.
  1. Хроматичен индекс.


4.1. Основни дефиниции за хроматичен индекс. Леми на Шенон.

4.2. Теорема за хроматичния индекс на пълния граф.

4.3. Теорема на Кьониг.

4.4. Теорема на Визинг.
  1. Графи на Рамзи.


    1. Прости свойства на нормалните 2 оцветявания.

    2. Графи на Рамзи с кликово число 5.

    3. Графи на Рамзи с кликово число 4.
  1. Любопитни факти.

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





  1. Въведение

През 1953г. е зададена на ученически конкурс, а по късно побликувана в американското списание Amer. Math Monthly, задачата: Какъв е максималният брой хора в компания, в която няма нито тройки познати, нито тройки непознати? Търсеният брой е 5. Следователно във всяка компания от 6 души има поне една тройка познати или непознати. Още нещо, във всяка такава компания има поне две тройки от познати или непознати(без да се изисква и двете тройки да са познати или непознати – може едната да е от познати, а другата от непознати). Съществуват 6 членни компании съставени от само 2 тройки познати или непознати.

Ако разгледаме задачата за 6-членната компания в теорията на графите тя изглежда така: ако всяко от ребрата на пълния граф с шест върха оцветим в един от два предварително дадени цвята, ще получим поне един едноцветен триъгълник. Ако един граф, подобно на пълния граф с 6 върха, има свойството при произволно оцветяване в два цвята, да се получава едноцветен триъгълник, страните на който са ребра на графа, тогава този граф се нарича граф на Рамзи.

През 1930г., английският математик Ф.П. Рамзи доказва, че за произволно естествено

p може да се намери такова естествено число n (което зависи от p), че във всяка n-членна компания сигурно има една p-орка от познати или непознати. Следователно, ако зададем произволно наредената двойка от естествени числа (p,q), то сигурно съществува такова естествено число n, зависещо от p и q, че във всяка n-членна компания непременно може да се намери p-орка познати или q-орка непознати. Най-малкото n с това свойство се означава с R(p,q). При p≥3 и q≥3 са известни само 6 от тези числа: R(3,3)=6, R(3,4)=9, R(3,5)=14, R(4,4)=18, R(3,6)=18 и R(3,7)=23. За първото число казахме в началото, а следващите 3 са открити от Грийнууд и Глисън през 1954г. Предпоследното е намерено от унгарският математик Кери през 1964г., а последното от американските математици Грейвър и Якел през 1968г.

Формулировката на самия Рамзи гласи: за всяка редица от естествени числа r, p1,p2,,ph, където pir , i=1,2,,h, може да се намери такова естествено число n, че ако едно множество K има поне n елемента, то както и да разпределим r-елементните му подмножества в h на брой взаимно чужди класове α1,α2,...,αh, поне за един клас αi съществува pi-елементно подмножество M на K всички r-елементни подмножества на което са елементи на класа αi. Най-малкото n с това свойство се означава с Rr(p1,p2,…,ph) и се нарича число на Рамзи. Очевидно R2(p,q)=R(p,q). Ясно е, че числото Rr(p1,p2,…,ph) не зависи от реда на числата p1,p2,…,ph. Освен споменатите по-горе числа на Рамзи е известно и числото R2(3,3,3)=17 открито от Грийнууд и Глисън през 1954г.

1.1. Познати нетривиални стойности и граници за двуцветно оцветявани числа на Рамзи.
q

p3456789101112131415369141823283640

4346

5152


5959

6966


7873

884182535

4149

6156


8469

11592


14997

191128


238133

291141


349153

417543


4958

8780


143101

216121


316141

4421571812052332616102

165111

298127


495169

780178


11712532623174017205

540216


1031232

171328264054165118282

1870317

358360908178619565



6588580

1267710798

235561265



  1. Основни дефиниции

През 1953 година широка популярност набират задачите свързани с познанства на хора в компании. Един от удобните начини за представянето на познанствата между хората е чрез графи. Така се улеснява решаването на много логически проблеми.

Под граф разбираме схемата на познанства на някаква компания. На всяка компания можем да съпоставим граф който да я определя напълно. Членовете на компанията са върхове на графа, а линиите свързващи върховете на графа (които всъщност представляват схемата на познанства) се наричат ребра.



Дефиниция: Два върха се наричат съседни, ако образуват двойка от множеството на наредените двойки върхове. В такъв случай, казваме че реброто свързва двата върха.

Дефиниция: Две ребра наричаме съседни, ако имат общ връх.

Дефиниция: Степен на връх - броя на ребрата свързващи се в един връх. Ще означаваме степента на връх с . Степен на графа наричаме най-голямата от степените на върховете и се означава с .

Дефениция: Ако от някой връх не излизат никакви ребра(т.е. =0), върхът се нарича изолиран.

Дефиниция: Множеството от върховете на графа G, всеки два от които са съседни, ще наричаме клика. Ако броя на върховете от кликата е k, то ще я наричаме k-клика.

Така 2-кликите са ребрата, 3-кликите са триъгълници(ребрата на които наричаме странии на триъгълника), а пнякога 4-кликите се наричат тетраедри. Ето и схема:



Дефиниция: Ако в има клика, но няма клика, то ще казваме, че има кликово число Последното го записваме така

Дефиниция: Множеството от върхове на никои два от които не са съседни, ще наричаме независимо множество.Ако в има независимо множество с върха, но няма такова с върха, ще казваме, че има число на независимост Записваме го така

Дефиниция: Множеството F от ребра на графа G, никои две от които не са съседни се нарича независимо множество от ребра на графа G. Ако в има независимо множество с ребра, но няма такова с ребра, ще казваме, че има число на реброва независимост Записваме го така .

Дефиниция: Граф в който множеството от всички върхове е клика, се нарича пълен.

Пълния граф с върха ще означаваме с .



Дефиниция: Граф, в който множеството от всички върхове е независимо, се нарича дискретен и се означава с , ако n е броят на върховете му. Дискретният граф няма ребра.

Дефиниция: Наричаме два графа равни, ако и двата са схеми на една и съща компания.



    1. Дефиниции за подграф.


Дефиниция: Нека G и H са два графа. Ще казваме, че G е подграф на H ако всеки връх на G е връх и на H и всяко ребро на G е ребро на H. В такъв случай ще казваме, че H съдържа G.

Дефиниция: Ще казваме, че G е породен подграф на H, ако G е подграф на H и всеки два върха на G, които са съседни в H, са съседни и в G.

Ако H има върхове и множеството не е независимо, тогава сигурно има повече от един подграф на H с върхове . Тъй като породеният подграф на H с върхове винаги е единствен ще го означаваме с <>.



е подграфът породен от всички върхове на H с изключение на .

е подграфът породен от всички въхове и ребра на H без реброто .

Ако имаме даден граф G, допълнителен граф () наричаме графа със същите върхове като в G, но в който два върха са съседни само ако не са съседни в G. Графите G и са подграфи на, ако n е броят на въховете на G.

Дискретният граф е допълнителен на пълния граф .


    1. Дефиниции за вериги

Нека е редица от върхове на графа G.Да приемем, че са свързани с ребро за Тогава редицата от върхове на G ще наричаме верига в G с дължина s-1.
Веригата се нарича затворена, ако .
Проста верига- ако всички върхове участаващи във веригата са различни, евентуално с изключение на .
Дефиниция: Проста затворена верига ще наричаме цикъл или многоъгълник.Цикъл с дължина ще означаваме с

Проста незатворена верига с дължина s ще означаваме с .


Дефиниция: Дължината на най-късата проста верига съединяваща два върха(ако съществува) се нарича разстояние между двата върха.
Дефиниция: Един граф наричаме свързан, ако всеки два негови върха са съединени с верига.


    1. Съединение на графи.

Дефиниция: Ако и са графи без общи върхове графът образуван от всички върхове на и , а ребрата му от всички ребра на и и всички отсечки свързващи и и се нарича съединение на и и се озна4ава с .

Графите и са породени подграфи на .

От начина на построение на , виждаме че е вярно и = .

Дефинираме съединяване на 3 графа като: +=()+. Аналогично се дефинира и съединение на произволно количество графи.

Ще док., че .



Док. се състои от всички върхове, ребра и отсечки свързващи . Следователно всеки два съседни върха си остават съседни в новия граф. Следователно .


    1. Оцветяване на върховете на граф




Дефиниция: Ако всеки от върховете на граф G може да се оцвети в h на брой предварително дадени цвята така, че съседните върхове да са разноцветни, казваме, че G е върхово h-оцветим.

Дефиниция: Ако в G е зададено h-оцветяване, тогава множеството на всички върхове, оцветени в i-ия цвят, се нарича i-ти едноцветен клас. Всеки едноцветен клас е независимо множество.

Очевидно графът G е върхово h-оцветим тогава и само тогава, когато е подграф от вида , където всеки от графите е дискретен.



Дефиниция: Минималното h, за което графът G е върхово h-оцветим, се нарича хроматично число на графа G и се означава с .

Ако H е подграф на G, тогава очевидно .



Ще докажем, че.

Док. Очевидно цветовете във всяко и са различни следователно е изпълнено неравенството . Сега ще докажем обратната посока, т.е. когато напавим съединението можем да оцветим новите ребра така, че нито 2 съседни върха да са в един цвят, т.е. нито 2 върха от и да не са в един и същ цвят, но това е така по условие. Следователно при съединението не се добавят нови цветове . Следователно равенството е изпълнено.

Очевидно е, че за цикъла имаме

Следователно, ако G съдържа цикъл с нечетна дължина, тогава . Обратното също е вярно.

Теорема(Кьониг): тогава и само тогава, когато G съдържа цикъл с нечетна дължина.

Док. Видяхме, че ако G съдържа цикъл с нечетна дължина, тогава .



Сега ще докажем, че ако G не съдържа цикли с нечетна дължина, тогава . Считаме графът за свързан. Нека е връх на G. С B ще означим множеството на всички върхове, които са на нечетно разстояние от , а с A – множеството на останалите върхове на G. Ще оцветим върховет на A в цвят , а на B - в цвят . Като се използва, че G не съдържа цикли с нечетна дължина, лесно е да се докаже, че никои два едноцветни върха не са съседни.



  1. Хроматични числа




    1. Неравенства на Нордхауз и Гадум за сумата и произведението на хроматичните числа на един граф G и неговия допълнителен граф

Нека v е връх на графа G. Ако G е върхово h-оцветим, тогава очевидно и подграфа G-v е върхово h-оцветим. Обратно, ако G-v е върхово h’-оцветим, то тогава не можем да твърдим, че и G е върхово h’-оцветим, но е очевидно, G е върхово (h’+1)-оцветим. Впрочем последното твърдение може да се замени по-точно, ако разполагаме с повече информация за върха v. В частност е вярно следното предложение:

Каталог: files -> files
files -> Р е п у б л и к а б ъ л г а р и я
files -> Дебелината на армираната изравнителна циментова замазка /позиция 3/ е 4 см
files -> „Европейско законодателство и практики в помощ на добри управленски решения, която се състоя на 24 септември 2009 г в София
files -> В сила oт 16. 03. 2011 Разяснение на нап здравни Вноски при Неплатен Отпуск ззо
files -> В сила oт 23. 05. 2008 Указание нои прилагане на ксо и нпос ксо
files -> 1. По пътя към паметник „1300 години България
files -> Георги Димитров – Kreston BulMar
files -> В сила oт 13. 05. 2005 Писмо мтсп обезщетение Неизползван Отпуск кт


Поделитесь с Вашими друзьями:
  1   2   3   4




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

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