Курсът е воден от проф д. м н. Николай Хаджииванов
Изтегляне 1.04 Mb.
|
- Навигация на страницата:
- Курсът е воден от проф. д.м.н. Николай Хаджииванов
- Основни дефиниции.
- Хроматично число.
- Графи на Рамзи.
- Любопитни факти.
Софийски Университет „Св. Климент Охридски” Курсова работа по Числа на Рамзи
Тема: Графи на Рамзи 2009г.
Съдържание
2.1. Дефиниции за подграф. 2.2. Дефиниции за вериги. 2.3. Съединение на графи. 2.4. Оцветяване на върховете на граф.
3.1. Неравенства на Нордхауз и Гадум. 3.2. Неравенство на Брукс.
4.1. Основни дефиниции за хроматичен индекс. Леми на Шенон. 4.2. Теорема за хроматичния индекс на пълния граф. 4.3. Теорема на Кьониг. 4.4. Теорема на Визинг.
През 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, където pi≥r , 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г.
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
През 1953 година широка популярност набират задачите свързани с познанства на хора в компании. Един от удобните начини за представянето на познанствата между хората е чрез графи. Така се улеснява решаването на много логически проблеми. Под граф разбираме схемата на познанства на някаква компания. На всяка компания можем да съпоставим граф който да я определя напълно. Членовете на компанията са върхове на графа, а линиите свързващи върховете на графа (които всъщност представляват схемата на познанства) се наричат ребра. Дефиниция: Два върха се наричат съседни, ако образуват двойка от множеството на наредените двойки върхове. В такъв случай, казваме че реброто свързва двата върха. Дефиниция: Две ребра наричаме съседни, ако имат общ връх. Дефиниция: Степен на връх - броя на ребрата свързващи се в един връх. Ще означаваме степента на връх с  . Степен на графа наричаме най-голямата от степените на върховете и се означава с .
Дефениция: Ако от някой връх не излизат никакви ребра(т.е. =0), върхът се нарича изолиран.
Дефиниция: Множеството от върховете на графа G, всеки два от които са съседни, ще наричаме клика. Ако броя на върховете от кликата е k, то ще я наричаме k-клика.
Така 2-кликите са ребрата, 3-кликите са триъгълници(ребрата на които наричаме странии на триъгълника), а пнякога 4-кликите се наричат тетраедри. Ето и схема: Дефиниция: Ако в  има  клика, но няма  клика, то ще казваме, че има кликово число  Последното го записваме така 
Дефиниция: Множеството  от върхове на  никои два от които не са съседни, ще наричаме независимо множество.Ако в има независимо множество с  върха, но няма такова с  върха, ще казваме, че има число на независимост Записваме го така 
Дефиниция: Множеството F от ребра на графа G, никои две от които не са съседни се нарича независимо множество от ребра на графа G. Ако в има независимо множество с ребра, но няма такова с ребра, ще казваме, че има число на реброва независимост Записваме го така  .
Дефиниция: Граф в който множеството от всички върхове е клика, се нарича пълен. Пълния граф с Дефиниция: Граф, в който множеството от всички върхове е независимо, се нарича дискретен и се означава с  , ако n е броят на върховете му. Дискретният граф няма ребра.
Дефиниция: Наричаме два графа равни, ако и двата са схеми на една и съща компания.
Дефиниция: Нека G и H са два графа. Ще казваме, че G е подграф на H ако всеки връх на G е връх и на H и всяко ребро на G е ребро на H. В такъв случай ще казваме, че H съдържа G. Дефиниция: Ще казваме, че G е породен подграф на H, ако G е подграф на H и всеки два върха на G, които са съседни в H, са съседни и в G. Ако H има върхове е подграфът породен от всички върхове на H с изключение на .
е подграфът породен от всички въхове и ребра на H без реброто .
Ако имаме даден граф G, допълнителен граф ( Дискретният граф
Нека  е редица от върхове на графа G.Да приемем, че са свързани с ребро за Тогава редицата от върхове на G ще наричаме верига в G с дължина s-1.
Веригата се нарича затворена, ако .
Проста верига- ако всички върхове участаващи във веригата са различни, евентуално с изключение на .
Дефиниция: Проста затворена верига ще наричаме цикъл или многоъгълник.Цикъл с дължина ще означаваме с 
Проста незатворена верига с дължина s ще означаваме с Дефиниция: Дължината на най-късата проста верига съединяваща два върха(ако съществува) се нарича разстояние между двата върха. Дефиниция: Един граф наричаме свързан, ако всеки два негови върха са съединени с верига.
Дефиниция: Ако  и са графи без общи върхове графът образуван от всички върхове на и , а ребрата му от всички ребра на и и всички отсечки свързващи и и се нарича съединение на и и се озна4ава с .
Графите  и са породени подграфи на .
От начина на построение на Дефинираме съединяване на 3 графа като: Ще док., че Док. се състои от всички върхове, ребра и отсечки свързващи . Следователно всеки два съседни върха си остават съседни в новия граф. Следователно .
Дефиниция: Ако всеки от върховете на граф G може да се оцвети в h на брой предварително дадени цвята така, че съседните върхове да са разноцветни, казваме, че G е върхово h-оцветим. Дефиниция: Ако в G е зададено h-оцветяване, тогава множеството на всички върхове, оцветени в i-ия цвят, се нарича i-ти едноцветен клас. Всеки едноцветен клас е независимо множество. Очевидно графът G е върхово h-оцветим тогава и само тогава, когато е подграф от вида Дефиниция: Минималното h, за което графът G е върхово h-оцветим, се нарича хроматично число на графа G и се означава с .
Ако H е подграф на G, тогава очевидно Ще докажем, че .
Док. Очевидно цветовете във всяко и са различни следователно е изпълнено неравенството . Сега ще докажем обратната посока, т.е. когато напавим съединението можем да оцветим новите ребра така, че нито 2 съседни върха да са в един цвят, т.е. нито 2 върха от и да не са в един и същ цвят, но това е така по условие. Следователно при съединението не се добавят нови цветове . Следователно равенството е изпълнено.
Очевидно е, че за цикъла Следователно, ако G съдържа цикъл с нечетна дължина, тогава Док. Видяхме, че ако G съдържа цикъл с нечетна дължина, тогава Сега ще докажем, че ако G не съдържа цикли с нечетна дължина, тогава . Считаме графът за свързан. Нека е връх на G. С B ще означим множеството на всички върхове, които са на нечетно разстояние от , а с A – множеството на останалите върхове на G. Ще оцветим върховет на A в цвят , а на B - в цвят . Като се използва, че 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.04 Mb. Сподели с приятели:
|