Су „Св. Климент Охридски
Изтегляне 278.49 Kb.
|
- Навигация на страницата:
- Доказателство
- Лема 2
- Определение
Доказателство: Доказателството се извършва чрез пълна математически индукция относно p, q и r, предполагайки, че теоремата е вярна за r=1 и произволни  и  , а също така за r и тройките  , където  и тройките  , където  . Ако успеем да докажем индуктивния преход, то ще ни трябва да имаме доказателство за началните стойности, а те са за тройките (p,q,1) при произволни p и q по-големи или равни на единица; (r,q,r) при произволни q по-голямо или равно на r и (p,r,r) при произволни p по-голямо или равно от r.
a) за тройката (p,q,1) лесно се вижда, че n(p,q,1)=p+q-1, т.е. че ако множеството S има N б) да докажем, че n(r,q,r)=q. Действително нека N Ако семейството в) по същия начин се доказва че n(p,r,r)=p. Нека означим  и  . Твърди се, че  .
Нека S е множество, съдържащо N  елемента, чийто r-подмножества са разбити на две семейства  и  . Да изберем произволен елемент  от S и нека  , т.е.  е множеството S, от което е махнат елемента . Да разбием съвкупността от всички (r-1)-подмножества на  на две семейства  и  по следния начин: ще считаме, че едно (r-1)-подмножество принадлежи на семейството , ако то заедно с елемента образува r-подмножество от семейството ; едно (r-1)-подмножество принадлежи към семейството , ако то заедно с елемента образува r-подмножество от семейството . Тъй като има не по-малко от  елемента, то по предположението на индукцията, или съдържа подмножество от  елемента, всички (r-1)-подмножества, на които принадлежат на семейството , или съдържа подмножество от  елемента, всички (r-1)-подмножества на което принадлежат на семейството . Тъй като , то в първия случей, ако множеството от елемента съдържа подмножество от q елемента, всички r-подмножества на което принадлежат на семейството , то тези q елемента удовлетворяват изискването на теоремата.
В противен случей това множество от Аналогично се разсъждава и тогава, когато Тъй като по индукционното предположение 3.Теорема на Ердьош-Секереш Теорема: За всяко цяло, положително число n съществува цяло число N=N(n), такова че всеки N точки в равнината, никои три от които не лежат на една права, съдържат n точки, образуващи изпъкнал n-ъгълник. Доказателство: Преди непосредственото доказателство на теоремата на Ердьош-Секереш трябва да бъдат доказани две леми: Лема 1: Ако в равнината са дадени пет точки, никои три от които не лежат на една права, то има четири от тях, които са върхове на изпъкнал четириъгълник. Доказателство: Ако изпъкналата обвивка на тези четири пет точки е четириъгълник или петоъгълник, то лемата е очевидна. Ако изпъкналата обвивка на тези пет точки е триъгълник ABC, а двете други точки D и Е се намират вътре в него, то продължението на отсечката DE че пресече две от страните на триъгълника ABC и нямата да пресече третата, например BC. Тогава точките B, C, D, E образуват изпъкнал четириъгълник. Лема 2: Ако всички четириъгълници, образувани от n точки, никои три от които не лежат на една права, са изпъкнали, то тези n точки се явяват върхове на изпъкнал n-ъгълник Доказателство: Твърдението очевидно е вярно за n=4 и доказателството ще извършим по индукция по n. Да предположим, че n  5 и че всички четириъгълници, образувани от точките  са изпъкнали. Тогава по индукционното предположение точките  се явяват върхове на изпъкнал (n-1)-ъгълник, който означаваме с  и предполагаме, че върховете му са наредени точно така . Нека най-напред предположим, че точка  лежи вътре в . Тогава трябва да вътре в някой от триъгълниците  ,  ,...,  ,...,  . Ако се намира вътре в триъгълника , то четирите точки  ,  ,  и не образуват изпъкнал четириъгълник, което противоречи на условието на лемата (тъй като никои три точки не лежат на една права, то не може да лежи на страна на някой от триъгълниците). Следователно лежи извън (n-1)-ъгълника . Да съединим с всеки връх . Тъй като лежи извън , то съществуват две прави (например  и  ), които образуват ъгъл, съдържащ в себе си изпъкналия много ъгълник . Ако точките и  не са последователни върхове, то триъгълника  ще съдържа още една точка  вътре в себе си, така че четирите точки , , и няма да образуват изпъкнал четириъгълник – противоречие с условието. Следователно и са последователни върхове и помествайки между тях, получаваме изпъкнал многоъгълник.
Сега да преминем към доказателството на теоремата на Ердьош-Секереш: Да вземем множеството от N точки и разгледаме семейството Т от 4-подмножества на N, т.е. от подмножествата, които съдържат точно по четири точки. Ясно е че семейството Т е еквивалентно на множеството от всички четириъгълници с върхове в N. Да разбием Т на две подсемейства – 4. Линейното програмиране в някои от задачите на Ремзи: Определение: Ще наричаме граф G, (k ,l )-good ако G не съдържа K  подграф и K подгарф. Всеки (k ,l )-good с n върха ще означаваме с (k ,l ,n )-good граф .
През 1965 Калбфлайш [Ka1] установява най-близката долана гарница 25 за R (4,5) като конструира (4,5,24)-good граф. До януари 1991г. най-бликата известна горна граница 28 е откритата през 1971г. от Уокър[Wa2]. Не следаващите няколко страници е описано изследване на в Brendan McKay и Stanislaw Radziszowski, които показват по-добро приближение от 27. За да се намерят нови крайни графи на Ремзи трябва да се избира измежду трвърде много възможности. Стесняването на обсега на търсене става на два етапа. Първо, използват се различни леми от комбинаториката, отнасящи се до свойствата на графите, които да ограничат общността на търсене. Второ, конструират се различни примерни задачина на целочислено линейно програмиране. Тяхното разрешаване носи съществена информация за търсените графи(вкючително и доказателство, че такива не същетсвуват). Накрая се прави търсене с помоща на компютър в така получената(по-малка) област на търсене. 4.1. R (4,5): Нека спрем вниманието си на числото на Ремзи R (4,5). Околността N(x) на върха x от (k ,l ,n )-good граф G = (V,E) вкючва (k- 1,l ,deg  (x ))-good граф и V- N(x ) -{x } включва (k ,l- 1,n- deg (x ) –1)-good граф. За фиксиран граф G тези два пографа ще обозначаване съответно с F и H.
Тъй като познаването на (k- 1,l )-good и (k ,l- 1)-good графите е от голямо значение за изучаването на R (k ,l), то за R (4,5) се нуждаем от(3,5)-good и (4,4)-good графите, които са вече известни [MR2,MZ,RK]. Подробното изброяване на всички (4,5)-good графи е невъзможно поради големия брой възможности. Нека с e (k ,l ,n ) и E (k ,l ,n ) да отбележим минималният и максималният брой ребра в произволен (k ,l ,n )-good граф и нека t (k ,l ,n ) да бъде минималният брой триъгълници кой да е такъв граф. Както бе споменато по-рано, вече са известни e (), E () и t () за всички n, в случаите на (k ,l ) = (4,4) и (k ,l ) = (3,5). Нека още с e(G) и t(G) да означим броя на ребрата и триъгълниците в произвилен граф G. Уокър е доказал [Wa1] следващата теорема 1, както и теореми 2 и 3 по надолу, които също могат да се открият и в [MR2] съответно като леми 3 и 2
(1) 0 ≤ Теорема 2: Ако n  е броя на върховете от степен i в произволен (4,5,n)-good граф G от поне 24 върха, то:
0 ≤ Теорема 3: Ако a е броят на ребрата, които участват в точно i триъгълиника на някой (4,5,n)-good граф G, тогава:
 = 4a - 2a - 2a + 
Предполагаме, че G е (4,5,n )-good граф с e ребра и n върха от степен i. Ще покажем растяща редица на системи от линейни ограничения Lpi, които са в сила за графа G при 0 ≤ i ≤ 4. Границите на променливите бърху неотрицателните цели числа и броя на ребрата e са ограничени.
LP0: За променливите n при max (n- R (4,4),0) ≤ i < min (n , R (3,5)) и константата n имаме:
n =  и 2e = 
LP1. Можем да разширим LP0 с ограничението, дадено ни от Теорема 1 като зададем k = 4 and l =5. LP2. Разширяваме LP1 като дабавяме неравенството от Теорема 2 т.е. LP2 е в сила само за (4,5)-good графи с поне 24 върха. LP3. Разширяваме LP1 по следният начин. Първо, въвеждаме нови променливи g  , с които означаваме върховете x  V (G ) , за които deg (x ) = i и e (F ) = m, и h, с които означаваме върховете x V (G ) такива, че deg (x ) = n- i -1 и e (H) =m. Границите на иднексите i и m може да се определи от n и от изброените (3,5)- и (4,4)-good графи. Общият брой на променливите не е много далече от 100. Имаме очевидното ограничение за всяко i:
n =  = 
и не чак толкова очевидното: (2) 2 Това ограничение е всъщност е еквивалентно на дясната страна на (1) за k = 4 и l =5 и лесно може да бъде изведено от доказателството на Теорема 1. Теорема 3 ни дава допълнителни ограничения. Нека с t и T да означим съответно минималният и максималният брой триъгълници в произволен (4,4,i )-good граф с m ребра. Аналогично, нека с sи S да означим границите на израза 2n(G) - n(G) - n(G) в кой да е (3,5,i )-good граф G с m ребра, където n (G) e броя на върховете от степен j в G. Въвеждаме още две допънителни променливи T и S със следните значения:
T = Като S е единствената променлива, за която се допуска да приема и отрицателни стойности. Така избраните S и T се използват в следните две ограничения:  ≤ T ≤ 
 ≤ S ≤ 
Самата Теорема 3 се използва като последно граничение: 3T = 3S +
Каталог: 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 Писмо мтсп обезщетение Неизползван Отпуск кт Изтегляне 278.49 Kb. Сподели с приятели:
|
n
n
+ 2
= RHS (1).
и S = 4a